在一个不规则多边形中，如何最有效地选择距离给定点最近的边？

Question

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

我可能需要对多边形内的大量点进行此计算（例如50-200个点）。

- Nathan Ridley

---

仅有大约100个点，这不是一个大的点集，除非你要进行无数次操作，或者多边形本身具有无数条边。在某一点上，四叉树分解可能会有所帮助。在达到该点之前，如果您的语言允许此类计算，甚至可以轻松求解从点到线段的距离，即使以向量化的形式进行。 - user85109

Answer 1

1. 计算与多边形每条边相切的直线上最近点。
2. 计算到给定点最近的每条线段（多边形的边）上的最近点。
3. 计算到给定点最近的每条线段上的最近点到该点的距离。
4. 找到最小距离。 最小距离对应的多边形边是答案。

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

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

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

• 让多边形的一条边的一个端点为p1 = {x1，y1}。
• 让多边形的另一条边的另一个端点为 p2 = {x2，y2}。
• 让您正在分析的多边形中的点为 p3 = {x3，y3}。
• 让u是需要查找沿由 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}

对于每个多边形的边缘，重复上述计算（即用新的p1和p2替换）

计算每条线段（多边形的边缘）到待求点的最近点。

当0<=u<=1时，点pu只是线段上最近的点。否则，线段的适当端点是离待求点最近的点。因此，针对上一步中计算出的每个pu、p1、p2 和 u，执行以下操作:

• 让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重复此计算

寻找最小距离。 相应的多边形边缘就是答案。

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

以下是一个图示，以帮助您了解本帖中的点和术语：

....

- Jason Moore

---

我认为# ELSE IF u>0 THEN pc = p2有一个笔误了... 应该是u>1吧？ - Dr. belisarius

谢谢！如果可以的话，我会给你的答案加2分的 :) - Nathan Ridley

我非常喜欢这个答案，但我注意到一个问题。在u的公式中有一个“拼写错误”。(x3 - x1)(x2 - x1)+(y3 - y1)(y2 - y1)的结果必须除以(x2 - x1)^2 + (y2 - y1)^2，因此需要适当分组。 - mhcuervo

Answer 2

正确答案取决于问题的整体结构：当考虑到多个查询时会发生什么？我假设每个查询将涉及不同的点。但是这个多边形呢？你是否期望收到多个关于同一多边形的查询？还是每次多边形都不同？

如果每个查询都应用于不同的、不可预测的多边形，那么你唯一的解决方案就是基本上要检查所有多边形边缘，并对每个边缘进行点到线段距离测试。它可以通过各种[启发式]方式进行优化（提前丢弃无用的测试），但在最坏的情况下，没有绕过全面测试的方法。

然而，如果你期望在问题的多边形方面有某种可预测性和稳定性（足够多的点对同一多边形或一组固定多边形的查询），那么情况就会发生戏剧性变化。在这种情况下，最好的方法是预先构建多边形内的基于边缘的Voronoi图。然后，你可以解决点位置问题（已知有效算法）以确定查询点落入哪个Voronoi区域。这将立即告诉你最接近的边缘是哪一个。

当你需要处理许多对同一多边形的点查询时，后者效率无与伦比，但需要相当大的努力来实现。因此，这完全取决于您需要什么样的解决方案。

P.S. 我看到你在问题中说你要为单个多边形运行大量点集。这立即使基于 Voronoi 图的解决方案成为首选。算法的额外细节可能取决于那个大点集是完全预先知道的还是以不可预测的方式逐点到达。

- AnT stands with Russia

---

我已经在这方面做了一些工作。为什么C#中没有支持不规则边界多边形的好的轻量级Voronoi库呢？我想写自己的库，但到目前为止我发现的唯一信息充斥着数学符号和构造，而我对此并不熟悉。因此，我想出了一种快速简单的方法（也许不是最有效的方法）来计算Voronoi图，即首先执行Delaunay三角化，使用质心作为Voronoi顶点，然后对于未被平分的Delaunay边缘，在边缘上运行新的平分线以达到边界多边形的效果。 - Nathan Ridley

对于每个质心，运行从外部质心到最近边界多边形边缘的线将为我提供所需的所有外部多边形，以生成 Voronoi 图。如果我有一个干净、高效、轻量级的 Voronoi 库，支持不规则多边形，我甚至不需要问这个问题。 - Nathan Ridley

Answer 3

参考这篇 Stack Overflow 的帖子获取灵感：点到多边形边缘的距离 或者这篇 点到线段的最短距离

- Fredrik Pihl