logo标签列表

如何快速找到两个多边形之间的最短笛卡尔距离？

c#algorithmgispolygondistance
21

我有1个红色多边形和50个随机放置的蓝色多边形 - 它们位于地理的2D空间中。什么是最快/最快的算法来查找红色多边形与其最近的蓝色多边形之间的最短距离?

请注意，这不是简单地将构成多边形顶点的点作为要测试距离的值，因为它们可能不一定是最近的点。

因此，最终答案应该返回最接近的蓝色多边形到单个红色多边形。

这比听起来要难!

请澄清：您是指穿过空旷空间的最短路径，还是只计算笛卡尔距离？ - Frank Krueger
"地理空间"是什么？3D？2D？ - moswald
1
一条边上的某个点可能比任何一个顶点都更接近。 - Bill the Lizard
你想要最接近的单个蓝色多边形，还是红色多边形和所有蓝色多边形之间最接近的一组对？ - Bill the Lizard
@Bill - 根据您的要求，已经修改了问题。 - Vidar
显示剩余7条评论
13个回答
13

我认为没有比计算红色多边形与每个蓝色多边形之间的距离并按长度排序更好的解决方案。

关于排序，通常情况下，在性能方面很难超越快速排序（优化后，如果大小小于7个项，则切断递归并切换到类似插入排序的算法，例如希尔排序）。

因此，我认为问题是如何快速计算两个多边形之间的距离，毕竟您需要进行50次此类计算。

以下方法也适用于3D，但可能不是最快的：

2D空间中的最小多边形距离

问题是，您是否愿意为速度而牺牲准确性？例如，您可以将所有多边形打包到包围盒中，其中盒子的边与坐标系轴平行。 3D游戏经常使用这种方法。因此，需要找到每个坐标（x、y、z）的最大和最小值来构建虚拟包围盒。然后计算这些包围盒之间的距离就是一个相当简单的任务。

以下是更高级的包围盒的示例图像，它们不与坐标系轴平行：

定向包围盒 - OBB

但是，这使得距离计算变得更加复杂。它用于碰撞检测，因为您不需要知道距离，只需要知道一个包围盒的边是否位于另一个包围盒内。

以下图像显示了轴对齐包围盒：

轴对齐包围盒 - AABB

OBB更精确，AABB更快。也许您想阅读这篇文章：

先进的碰撞检测技术

这总是假设你愿意为了速度而牺牲精度。如果精度比速度更重要，你可能需要使用更高级的技术。

1
Shamos的旋转卡尺技术（“2D空间中的最小多边形距离”）仅适用于凸多边形。 - danio
这是一个至关重要的观点@danio - 对于一个完整准确的算法来说，它应该考虑到凸多边形和凹多边形。 - Vidar
5

您可以先尝试减少问题规模，然后对小规模数据进行深入搜索。

首先处理每个多边形，找到以下内容：

  • 多边形的中心
  • 多边形的最大半径（即，从定义的中心点到多边形边缘/表面/顶点最远的点）

现在您可以收集与红色多边形最近的5-10个多边形（找到中心点之间的距离，减去半径，排序并选择前5个），然后执行更加详尽的例程。

我想象中有一个奇怪形状的多边形，它的中心可能很远，但顶点比最近的5或10个多边形更接近。根据您的约束条件，这可能是一种可接受的优化方案。 - Mike Tunnicliffe
这个问题需要解决 - 从中心到任何给定顶点的最大距离成为多边形的半径，并且用于确定接近度，而不是中心。 - Adam Davis
边界圆将建立红色与任何蓝色之间的最小距离。从最近的一对开始，使用旋转卡尺或其他方法确定它们的精确距离。以此种子距离，您只需要检查其他多边形对，其边界圆之间的距离小于该距离即可。 - Alan
4

对于具有合理数量边界点的多边形形状，例如在GIS或游戏应用中，可能更快更容易地进行一系列测试。

对于红色多边形中的每个顶点，计算到蓝色多边形中每个顶点的距离，并找到最近的（提示：比较distance^2，因此您不需要sqrt()）。 找到最近的点后，检查找到的红色和蓝色顶点两侧的顶点，以决定哪些线段最接近，然后找到两条线段之间的最接近点。

请参见http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline3d/（它易于简化为2d情况）。

嗨 - 我已经做了与您所说的类似的事情 - 但需要一段时间，尤其是对于大型多边形。但还是谢谢。 - Vidar
如果你所说的“point”是指“顶点”，那么这也不会给出正确的结果。 - erickson
3
也许Frechet距离是您正在寻找的内容？
计算两个多边形曲线之间的Frechet距离 链接 计算简单多边形之间的Frechet距离 链接
只包含链接的答案被认为是不好的做法。请在此总结内容（不要复制/粘贴），以便答案可以独立存在。如果您不这样做，您的答案可能会被删除，特别是如果链接失效（再次）。 - Martijn Pieters
3
这种筛选技术旨在在不影响结果准确性的情况下，减少平均情况下需要执行的距离计算次数。它适用于凸多边形和凹多边形。
找到每对顶点之间的最小距离，使其中一个是红色顶点，另一个是蓝色顶点。称其为r。多边形之间的距离最多为r。从红色多边形构造一个新区域，在该区域中，每条线段向外移动r并通过半径为r的弧连接到其相邻的线段。查找位于此区域内的每个顶点到与此区域相交的反色线段的距离。
当然，您可以添加一个近似方法，例如包围盒，以快速确定哪些蓝色多边形不可能与红色区域相交。
2
我会首先用一个包围圆来约束所有的多边形，然后找到最小距离的上限。接着，我会简单地对比所有蓝色多边形的边界，如果它们的下限距离低于最小距离的上限，则与红色多边形的所有边界对比。 
最小距离的上限 = min {distance(red的中心, 当前蓝色的中心) + 当前蓝色的半径}
对于每个蓝色多边形，其中 distance(red的中心, 当前蓝色的中心) - 当前蓝色的半径 < 最小距离的上限
    检查边缘和顶点的距离
但这一切都取决于您的数据。如果相较于它们之间和红色多边形之间的距离，蓝色多边形相对较小，那么这种方法应该能够很好地工作，但是如果它们非常接近，您将无法节省任何东西（许多多边形将足够接近）。另外一件事情是，如果这些多边形没有许多顶点（就像大多数都是三角形），那么仅检查每个红色边界与每个蓝色边界的距离可能几乎一样快。
希望这能有所帮助。
2
如其他人所提到的，使用边界区域（矩形、圆形）可能会让你丢弃一些多边形之间的交互。有几种策略可供选择，例如：
  1. 选取任意一个蓝色多边形并找出它与红色多边形之间的距离。接下来选取另一个多边形。如果边界区域之间的最小距离大于已经找到的距离，则可以忽略此多边形。继续处理所有多边形。
  2. 找出红色多边形和所有蓝色多边形之间的最小距离/质心距离。对这些距离进行排序，并首先考虑最小的距离。计算实际的最小距离，并按排序列表中的顺序继续，直到多边形之间的最大距离大于目前为止找到的最小距离为止。
在算法的性能方面，你选择使用圆形/轴对齐矩形或者方向矩形可能会产生很大的影响，这取决于输入多边形的实际布局。
对于实际的最小距离计算，你可以使用Yang等人的 "基于Voronoi图的计算两个不相交凸多边形之间距离的新快速算法"，该算法的时间复杂度为O（log n + log m）。
2

我马上要去参加葬礼了，但是如果你将多边形分解为凸子多边形，就可以进行一些优化。你可以对每个多边形进行二分搜索，找到最近的顶点，然后我相信最近的点应该是那个顶点或相邻边上的点。这意味着你应该能够在log(log m * n)的时间内完成，其中m是多边形上平均顶点数，n是多边形数。这有点匆忙，所以可能不正确。如果需要，稍后会提供更多详细信息。

2

我知道你说的是“最短距离”，但你真正想要的是最优解或者“好的/非常好的”解决方案，对吗？

因为如果你需要找到最优解，你必须计算所有源和目标多边形边界之间的距离（不仅仅是顶点）。如果你处在三维空间中，那么每个边界都是一个平面。这可能是一个大问题（O(n^2)），取决于你有多少个顶点。

所以，如果你的顶点数量使得计算结果很大，并且“好的/非常好的”解决方案对你来说足够了，那么可以使用启发式方法或近似方法。

2
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接