找到两个多边形之间最短笛卡尔距离的最快方法是什么

StackOverflow https://stackoverflow.com/questions/84034

题

我有 1 个红色多边形 说和 50 个随机放置的蓝色多边形 - 它们位于地理 二维空间. 。找到红色多边形与其最近的蓝色多边形之间的最短距离的最快/最快的算法是什么？

请记住，这并不是将构成多边形顶点的点作为值来测试距离的简单情况，因为它们不一定是最近的点。

所以最后 - 答案应该返回最接近单个红色多边形的蓝色多边形。

这比听起来更难！

有帮助吗？

解决方案

我怀疑是否有比计算红色和每个蓝色之间的距离并按长度排序更好的解决方案。

关于排序，通常 QuickSort 在性能上很难被打败（一种优化的排序，如果大小低于 7 个项目，它会切断递归，并切换到像 InsertionSort 之类的东西，也许是 ShellSort）。

因此我想问题是如何快速计算两个多边形之间的距离，毕竟你需要计算 50 次。

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

二维空间中的最小多边形距离

问题是，你愿意牺牲准确性来换取速度吗？例如。您可以将所有多边形打包到边界框中，其中框的侧面与坐标系轴平行。3D 游戏经常使用这种方法。因此，您需要找到每个坐标（x，y，z）的最大值和最小值来构造虚​​拟边界框。计算这些边界框的距离是一项非常简单的任务。

下面是更高级边界框的示例图像，它们不平行于坐标系轴：

定向边界框 - OBB

然而，这使得距离计算不再那么简单。它用于碰撞检测，因为您不需要知道距离，您只需要知道一个边界框的一个边缘是否位于另一个边界框内。

下图显示了轴对齐的边界框：

轴对齐边界框 - AABB

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

先进的碰撞检测技术

这始终假设您愿意牺牲精度来换取速度。如果精度比速度更重要，您可能需要更先进的技术。

其他提示

您也许可以减少问题，然后对一小部分进行深入搜索。

首先通过查找来处理每个多边形：

  • 多边形中心
  • 多边形的最大半径（即多边形的边/表面/顶点上距定义中心最远的点）

现在，您可以收集距离红色多边形最近的 5-10 个多边形（找到中心到中心的距离，减去半径，对列表进行排序并取前 5 个），然后执行更详尽的例程。

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

对于红色多边形中的每个顶点，计算到蓝色多边形中每个顶点的距离，然后找到最接近的（提示，比较距离^2），因此您不需要sqrt（））找到最接近的距离，然后检查每一侧的顶点在发现的红色和蓝色顶点中，可以决定哪个线段最接近，然后在两个线段之间找到最接近的方法。

看 http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline3d/ （对于2d的情况很容易简单）

这种筛选技术旨在减少平均情况下需要执行的距离计算次数，而不影响结果的准确性。它适用于凸多边形和凹多边形。

找到每对顶点之间的最小距离，其中一个是红色顶点，一个是蓝色顶点。叫它 r. 。多边形之间的距离最多为 r. 。从红色多边形构造一个新区域，其中每条线段向外移动 r 并通过半径圆弧与其邻居相连 r 以顶点为中心。求该区域内每个顶点到与该区域相交的每条相反颜色线段的距离。

当然，您可以添加近似方法（例如边界框）来快速确定哪个蓝色多边形不可能与红色区域相交。

我知道您说“最短距离”，但您的真正意思是最佳解决方案或“好/非常好”解决方案适合您的问题吗？

因为如果您需要找到最佳解决方案，则必须计算所有源和目标 poligon 边界（而不仅仅是顶点）之间的距离。如果您处于 3D 空间中，则每个边界都是一个平面。这可能是一个大问题 (O(n^2))，具体取决于您有多少个顶点。

因此，如果您的顶点数使其平方为一个可怕的数字，并且“好/非常好”的解决方案适合您，请选择启发式解决方案或近似值。

您可能想看看 Voronoi Culling。论文和视频在这里：

http://www.cs.unc.edu/~geom/DVD/

我将首先用边界圆限制所有多边形，然后找到最小距离的上限。然后我将简单地检查所有蓝色多边形的边缘，其距离下限低于红色多边形所有边缘的最小距离上限。

upper bound of min distance = min {distance(red's center, current blue's center) + current blue's radius}

for every blue polygon where distance(red's center, current blue's center) - current blue's radius < upper bound of min distance
    check distance of edges and vertices

但这一切都取决于您的数据。如果蓝色多边形与它们和红色多边形之间的距离相比相对较小，那么这种方法应该可以很好地工作，但如果它们非常接近，您将不会保存任何内容（其中许多都足够接近）。另一件事 - 如果这些多边形没有很多顶点（就像大多数都是三角形一样），那么仅检查每个红色边与每个蓝色边可能几乎一样快。

希望能帮助到你

正如其他人提到的，使用边界区域（框、圆）可能会让您放弃一些多边形与多边形的相互作用。为此有几种策略，例如

  1. 选取任意蓝色多边形并找出与红色多边形的距离。现在选择任何其他多边形。如果边界区域之间的最小距离大于已找到的距离，则可以忽略此多边形。继续处理所有多边形。
  2. 找到红色多边形和所有蓝色多边形之间的最小距离/质心距离。对距离进行排序并首先考虑最小距离。计算实际的最小距离并继续遍历排序列表，直到多边形之间的最大距离大于迄今为止找到的最小距离。

您选择的圆/轴向对齐框或定向框可能会对算法的性能产生很大影响，具体取决于输入多边形的实际布局。

对于实际的最小距离计算，您可以使用 Yang 等人的'基于Voronoi图的计算两个不相交凸多边形之间距离的快速算法' 这是 O(log n + log m)。

一会儿就要去参加葬礼了，但是如果你把多边形分解成凸子多边形，你可以做一些优化。您可以对每个多边形进行二分搜索以找到最近的顶点，然后我 相信 最近的点应该是该顶点或相邻的边。这意味着您应该能够在 log(log m * n) 其中 m 是多边形上的平均顶点数，n 是多边形的数量。这有点仓促，所以可能是错误的。如果需要的话，稍后会提供更多详细信息。

您可以从比较边界框之间的距离开始。测试矩形之间的距离比测试多边形之间的距离更容易，并且您可以立即消除任何距离超过最近的矩形+其对角线的多边形（也许您可以进一步细化）。然后，您可以测试剩余的多边形以找到最接近的多边形。

有一些算法可以找到多边形的邻近度 - 我确信维基百科对它们有很好的评论。如果我没记错的话，那些只允许凸多边形的速度要快得多。

我相信您正在寻找的是 A* 算法，它用于寻路。

最简单的方法是找到红色和 50 个蓝色物体之间的距离 - 因此您需要通过 50 个 3d 毕达哥拉斯计算 + 排序来找到答案。但这仅适用于找到中心点之间的距离。

如果您想要任意多边形，也许您最好的选择是光线跟踪解决方案，该解决方案从相对于法线的红色多边形表面发射光线，并报告何时击中另一个多边形。

混合可能会起作用 - 我们可以找到距中心点的距离，假设我们对蓝色多边形的相对大小有一些概念，我们可以将结果集剔除为其中最接近的，然后使用光线追踪来缩小真正的范围最接近的多边形。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top