Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Distance from a point to a polygon

I am trying to determine the distance from a point to a polygon in 2D space. The point can be inside or outside the polygon; The polygon can be convex or concave.

If the point is within the polygon or outside the polygon with a distance smaller than a user-defined constant d, the procedure should return True; False otherwise.

I have found a similar question: Distance from a point to a polyhedron or to a polygon. However, the space is 2D in my case and the polygon can be concave, so it's somehow different from that one.

I suppose there should be a method simpler than offsetting the polygon by d and determining it's inside or outside the polygon.

Any algorithm, code, or hints for me to google around would be appreciated.

like image 439
clwen Avatar asked Jun 11 '12 16:06

clwen


People also ask

How do you find the distance from a point to a polygon?

Because a polygon is an area enclosed by an ordered collection of line segments, calculating the distance from a point to a polygon involves identifying the closest line segment to the point, and then Rule 2 is applied to get the distance.

What is the distance of a polygon?

The total distance of the outer sides of a closed figure is known as the perimeter. It is the total length of all sides of a polygon. The unit of the perimeter of any polygon will remain the same as the unit of its respective sides.

How do you calculate spatial distance?

Distance is relative to the observer. You probably want the distance as measured by static observers (particularly r=const, θ=π/2, ϕ=0), then it is ∫(1−2M/r)−1/2dr.


2 Answers

Your best bet is to iterate over all the lines and find the minimum distance from a point to a line segment.

To find the distance from a point to a line segment, you first find the distance from a point to a line by picking arbitrary points P1 and P2 on the line (it might be wise to use your endpoints). Then take the vector from P1 to your point P0 and find (P2-P1) . (P0 - P1) where . is the dot product. Divide this value by ||P2-P1||^2 and get a value r.

Now if you picked P1 and P2 as your points, you can simply check if r is between 0 and 1. If r is greater than 1, then P2 is the closest point, so your distance is ||P0-P2||. If r is less than 0, then P1 is the closest point, so your distance is ||P0-P1||.

If 0<r<1, then your distance is sqrt(||P0-P1||^2 - (r * ||P2-P1||)^2)

The pseudocode is as follows:

for p1, p2 in vertices:    var r = dotProduct(vector(p2 - p1), vector(x - p1))   //x is the point you're looking for    r /= (magnitude(vector(p2 - p1)) ** 2)    if r < 0:     var dist = magnitude(vector(x - p1))   else if r > 1:     dist = magnitude(vector(p2 - x))   else:     dist = sqrt(magnitude(vector(x - p1)) ^ 2 - (r * magnitude(vector(p2-p1))) ^ 2)    minDist = min(dist,minDist) 
like image 92
Hans Z Avatar answered Sep 23 '22 12:09

Hans Z


If you have a working point to line segment distance function, you can use it to calculate the distance from the point to each of the edges of the polygon. Of course, you have to check if the point is inside the polygon first.

like image 26
ffao Avatar answered Sep 21 '22 12:09

ffao