Let's assume that the N-sided polygon has vertices (xi,yi) in clockwise or counterclockwise order, i=1…N, with (x0,y0)=(xN,yN), and we wish to find the distance from point (xp,yp) to the perimeter of the polygon
, the simple (but perhaps not optimal) method is to find the minimum distance between the point and each edge line segment.
The distance between the line segment (xA,yA)−(xB,yB) and point (xp,yp), is parametrise the line segment with 0≤t≤1,
The line segment corresponds to 0≤t≤1, so if t≤0, the closest point to (xp,yp) is (xA,yA)
; if t≥1 the closest point to (xp,yp) is (xB,yB) ; otherwise, the closest point to (xp,yp) is (x(t),y(t))
.
There are many ways to find t that corresponds to the minimum distance between (xp,yp)
and the line extending the edge line segment. Suffice it to say, they all yield a single solution,
(If you precalculate
for each edge i, you can calculate ti=(p⃗ −v⃗ i)⋅m⃗ i very efficiently, with just two scalar multiplications, two scalar subtractions, and one scalar addition per edge. To calculate the point when 0<ti<1, additional four scalar multiplications, two additions, and two subtractions are needed. The distance squared is another two scalar multiplications and an addition. Therefore, this way the worst case cost per edge is eight scalar multiplications and nine additions or multiplications – and that is quite acceptable and efficient, in computer geometry terms.)
Because the distance squared is a monotonic function of the distance, we don't need the square root for each edge line segment; we can find the minimum squared distance instead. This minimum distance d2i for the edge line segment ending at vertex i is
Ericsson
The squared distance between a point C and a segment AB can be directly computed
without explicitly computing the point D on AB closest to C. As in the preceding
section, there are three cases to consider. When AC · AB ≤ 0, A is closest to C and
the squared distance is given by AC · AC. When AC · AB ≥ AB · AB, B is closest to C
and the squared distance is BC · BC. In the remaining case, 0 < AC · AB < AB · AB,
the squared distance is given by CD · CD, where
However, because the expression CD · CD simplifies to
(has this got anything to do with pythagoras theorem?)
Comments