geometry - For a point in an irregular polygon, what is the most efficient way to select the edge closest to the point?

Question

Given an irregular polygon and a point within that polygon, how do I determine which edge in the polygon is closest to the point?

I will likely have to run this calculation for a large set of points within the polygon (e.g. 50-200 points).

Answer 1

1. Calculate closest point on the line that is tangent to each edge of the polygon.
2. Calculate closest point on each line segment (edge of the polygon) to the point in question.
3. Calculate the distance from the closest point on each line segment to the point in question.
4. Find the minimum distance. The corresponding polygonedge with the minimum distance is the answer.

Each step of this algorithm is linear time (O(n)).

Here are the basic formulas for each of the steps:

Calculate closest point on the line that is tangent to each edge of the polygon.

• Let the one endpoint of an edge of a polygon be p1 = {x1, y1}.
• Let the other endpoint of an edge of a polygon be p2 = {x2, y2}.
• Let the point in the polygon you are analyzing be p3 = {x3,y3}.
• Let u be the percentage of the distance between p1 and p2, that is needed to find the point on the line formed by p1 and p2, such that p1+u(p2-p1) = the point on the line that is closest to p3 (the line segment between this point and p3 also happens to be perpendicular to the line going through p1 and p2).
• u = ((x3 - x1)(x2 - x1)+(y3 - y1)(y2 - y1)) / ((x2 - x1)^2 + (y2 - y1)^2)
• Let the point closest to p3 on the line formed by p1 and p2 be known as pu = {xu, yu}
• xu = x1 + u (x2 - x1)
• yu = y1 + u (y2- y1)
• And like we said before pu = {xu, yu}
• Repeat these calculations for every polygon edge (i.e. substitute in new p1s and p2s)

Calculate closest point on each line segment (edge of the polygon) to the point in question.

The point pu is only the closest point on the line segment when 0 <= u <= 1. Otherwise the appropriate endpoint of the line segment is the closest point to the point in question. Thus for each pu, p1, p2, and u calculated in the above step do the following:

• Let pc = {xc, yc} be denoted as the closest point on the line segment of the polygon edge to the point in question.
• IF u<0 THEN pc = p1
• ELSE IF u>1 THEN pc = p2
• ELSE pc = pu

Calculate the distance from the closest point on each line segment to the point in question.

• Distance between p3 and pc = `sqrt((x3 - xc)^2 + (y3 - yc)^2)
• Repeat this calculation for all pc's

Find the minimum distance. The corresponding polygonedge with the minimum distance is the answer.

• Iterate through all of the distances until you find the smallest one. The corresponding polygon edge is the answer.

Here is a diagram to help you understand what the points and terminology in this post represent:

....