geometry - 对于不规则多边形中的一个点，选择最靠近该点的边的最有效方法是什么？

Question

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



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

Answer 1

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

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

计算每条线段上最近点到相关点的距离。

找出最小距离。具有最小距离的相应多边形边就是答案。

该算法的每一步都是线性时间(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)

对所有 pc 的

重复此计算

找出最小距离。具有最小距离的相应多边形边就是答案。

遍历所有距离，直到找到最小的距离。相应的多边形边就是答案。

这是一张图表，可帮助您了解本文中的要点和术语代表的含义:



....