Distance from a point to a polygon

by

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)

More Related Contents:

  1. How to determine if a point is in a 2D triangle? [closed]
  2. Equation for testing if a point is inside a circle
  3. Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping
  4. An algorithm for inflating/deflating (offsetting, buffering) polygons
  5. Algorithm to detect intersection of two rectangles?
  6. How to calculate an angle from three points? [closed]
  7. How to find the intersection point between a line and a rectangle?
  8. How do I efficiently determine if a polygon is convex, non-convex or complex?
  9. What is the fastest algorithm to calculate the minimum distance between two sets of points?
  10. Is there an efficient algorithm to generate a 2D concave hull?
  11. Puzzle: Find largest rectangle (maximal rectangle problem)
  12. Combined area of overlapping circles
  13. Circle-circle intersection points
  14. How to find two most distant points?
  15. Find the set of largest contiguous rectangles to cover multiple areas [duplicate]
  16. Polygon enclosing a set of points
  17. What is the most efficient algorithm to find a straight line that goes through most points?
  18. Collision detection of huge number of circles
  19. Create non-intersecting polygon passing through all given points
  20. Determining if two line segments intersect? [duplicate]
  21. How can I create an internal spiral for a polygon?
  22. Calculating the position of points in a circle
  23. Mesh generation from points with x, y and z coordinates
  24. How do you find a point at a given perpendicular distance from a line?
  25. Find if a point is inside a convex hull for a set of points without computing the hull itself
  26. Best way to find a point on a circle closest to a given point
  27. Algorithm for reflecting a point across a line
  28. determine if a point sits inside an arbitrary shape?
  29. How can I perform Collision Detection on rotated rectangles? [closed]
  30. Location of highest density on a sphere

Leave a Comment