20

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

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

所以最后 - 答案应该将最接近的蓝色多边形归还给奇异的红色多边形。

这比听起来更难！

4

13 回答 13

13

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

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

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

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

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

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

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

定向边界框 - OBB

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

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

轴对齐边界框 - AABB

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

先进的碰撞检测技术

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

于 2008-09-17T15:13:56.010 回答
5

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

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

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

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

于 2008-09-17T15:19:17.230 回答
4

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

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

请参阅http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline3d/ （对于 2d 案例很容易）

于 2008-09-17T15:07:53.963 回答
3

也许 Frechet 距离是您想要的？

计算两条多边形曲线之间
的 Fréchet 距离 计算简单多边形之间的 Fréchet 距离

于 2008-09-17T14:57:08.483 回答
3

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

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

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

于 2008-09-17T19:28:14.977 回答
2

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

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

因此，如果您的顶点数使该平方与一个可怕的数字相匹配，并且“好/非常好”的解决方案对您来说很好，请选择启发式解决方案或近似值。

于 2008-09-17T15:44:29.463 回答
2

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

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

于 2008-09-19T00:12:53.490 回答
2

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

最小距离的上限 = min {距离（红色的中心，当前蓝色的中心）+ 当前蓝色的半径}

对于距离（红色的中心，当前蓝色的中心）-当前蓝色的半径 < 最小距离上限的每个蓝色多边形
    检查边和顶点的距离

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

希望能帮助到你

于 2009-07-13T14:17:53.610 回答
2

正如其他人提到的那样，使用边界区域（框、圆）可能允许您丢弃一些多边形-多边形交互。为此有几种策略，例如

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

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

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

于 2009-07-13T15:06:23.343 回答
2

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

于 2009-07-13T15:11:57.110 回答
1

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

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

于 2008-09-17T15:24:20.180 回答
0

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

于 2010-09-16T15:36:11.487 回答
-1

天真的方法是找出红色和 50 个蓝色对象之间的距离——因此您正在查看 50 个 3d 毕达哥拉斯计算 + 排序来找到答案。不过，这只适用于找到中心点之间的距离。

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

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

于 2008-09-17T15:06:34.060 回答