Distance from a point to a polygon
algorithm, geometry
Solution
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)
Problem
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.