对于不规则多边形中的点,选择最接近该点的边的最有效方法是什么？

Question

给定不规则多边形和该多边形内的点,如何确定多边形中哪条边最接近该点？

我可能必须对多边形内的一大组点(例如50-200点)运行此计算.

Answer 1

1. 计算与多边形的每条边相切的直线上的最近点.
2. 计算每个线段(多边形的边缘)上的最近点到相关点.
3. 计算从每个线段上的最近点到相关点的距离.
4. 找到最小距离.具有最小距离的相应多边形是答案.

该算法的每个步骤都是线性时间(O(n)).

以下是每个步骤的基本公式:

计算与多边形的每条边相切的直线上的最近点.

• 设多边形边的一个端点p1 = {x1, y1}.
• 设多边形边的另一个端点p2 = {x2, y2}.
• 让你正在分析的多边形中的点是p3 = {x3,y3}.
• 让u是p1和p2之间的距离的百分比,即需要找到在由P1和P2,形成的线的点,使得p1+u(p2-p1)=线路上的点(最靠近P3这点和P3之间的线段也恰好垂直于通过p1和p2的直线).
• u = ((x3 - x1)(x2 - x1)+(y3 - y1)(y2 - y1)) / ((x2 - x1)^2 + (y2 - y1)^2)
• 将由p1和p2形成的线上最接近p3的点称为 pu = {xu, yu}
• xu = x1 + u (x2 - x1)
• yu = y1 + u (y2- y1)
• 就像我们之前说过的那样 pu = {xu, yu}
• 对每个多边形边重复这些计算(即替换为新的p1s和p2s)

计算每个线段(多边形的边缘)上的最近点到相关点.

该点pu只是线段上最近的点0 <= u <= 1.否则,线段的适当端点是与该点最近的点.因此,对于pu, p1, p2, and u在上述步骤中计算的每个步骤,请执

• Let pc = {xc, yc} 被表示为多边形边缘的线段上与所讨论的点的最近点.
• IF u<0 THEN pc = p1
• ELSE IF u>1 THEN pc = p2
• ELSE pc = pu

计算从每个线段上的最近点到相关点的距离.

• p3和之间的距离pc=`sqrt((x3 - xc)^ 2 +(y3 - yc)^ 2)
• 对所有电脑重复此计算

找到最小距离.具有最小距离的相应多边形是答案.

• 迭代所有距离,直到找到最小的距离.相应的多边形边缘就是答案.

这是一个图表,可以帮助您了解此帖中的要点和术语:

....