For a point in an irregular polygon, what is the m

问题:

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).

回答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:

....

回答2:

The right answer depends on the bigger-picture structure of the problem: what happens when you take into account multiple queries? I assume that each query will deal with a different point. But what about the polygon? Do you expect to receive multiple queries for the same polygon? Or each time the polygon is different?

If each query is applied to a different, unpredictable polygon, then the only solution you have is essentially the total inspection of all polygon edges with point-to-segment distance testing for each one. It can be optimized in various [heuristic] ways (to discard the unnecessary tests early), but in the worst case there's no way around the full test.

However, if you expect some kind of predictability and stability on the polygon side of the problem (sufficiently many point-queries to the same polygon or to a fixed set of polygons), then the situation changes dramatically. The best approach in this case would be to pre-build the edge-based Voronoi diagram inside the polygon(s). Then you can solve the point-location problem (for which there are known efficient algorithms) in order to determine which Voronoi region the query point falls into. That will immediately tell you which edge is the closest.

The latter is incomparably more efficient when you need to handle many point-queries to the same polygon(s), but requires quite an effort to implement. So, it all depends on what kind of solution you need.

P.S. I see that you state in your question that your are going to run it for a large set of points for a single polygon. This immediately makes the Voronoi-diagram-based solution the way to go. Extra nuances of the algorithm might depend on whether that large set of points is entirely known in advance or arrives point-by-point in unpredictable way.

回答3:

Se this post on SO for inspiration distance from point within a polygon to polygon edge or this one Shortest distance between a point and a line segment