CODEWITHSUNDEEP
algorithmgeometry
clwen
clwen

Reputation: 20909

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.

Upvotes: 35

Views: 56640

Answers (6)

jrjbertram
jrjbertram

Reputation: 460

In the event that this helps someone else, I reverse engineered doverbin's answer to understand why it worked showing graphically what the three cases are computing. (doverbin, feel free to incorporate this into your answer if you wish.)

Graphical depiction of doverbin's answer

Upvotes: 13

Hans Z
Hans Z

Reputation: 4744

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)

Upvotes: 38

JLD
JLD

Reputation: 89

I do not know about the difference in performance with respect to the rest of answers, but in boost C++ libraries there is an generic implementation called distance. It has information about complexity in every case and in your problem case it is linear.

I was also looking for solutions to this problem some days ago and I want to share this finding. Hope it helps to someone.

Upvotes: 0

Alen
Alen

Reputation: 1075

I can help you with this pointers:

and some remarks:

  • you should check only the nearest points, as Martin Beckett´s answer point outs, since another segment can "proyected" very near, but in reality don´t be close as need.

Upvotes: 1

Martin Beckett
Martin Beckett

Reputation: 96109

Do you need fast or simple?
Does it have to be always absolutely correct in edge cases or will good enough most of the time be OK?

Typical solution are to find the distance to each vertex and find the pair with the smallest values ( note that for a point outside a convex polygon these might not be adjacent) and then check point to line intersections for each segment.

For large complex shapes you can also store approx polygon bounding boxes (either rectangular or hexagons) and find the closest side before checking more detail.

You may also need code to handle the special case of exactly on a line.

Upvotes: 2

ffao
ffao

Reputation: 876

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.

Upvotes: 3

Related Questions