我有1个红色多边形和50个随机放置的蓝色多边形 - 它们位于地理的2D空间中。什么是最快/最快的算法来查找红色多边形与其最近的蓝色多边形之间的最短距离?
请注意，这不是简单地将构成多边形顶点的点作为要测试距离的值，因为它们可能不一定是最近的点。
因此，最终答案应该返回最接近的蓝色多边形到单个红色多边形。
这比听起来要难!
13个回答
1
你可以先比较包围框之间的距离。测试矩形之间的距离比测试多边形之间的距离更容易，并且您可以立即消除任何距离 nearest_rect + its_diagonal 以上的多边形（可能您甚至可以进一步细化）。然后，您可以测试剩余的多边形以找到最近的多边形。
有一些算法用于寻找多边形的接近度-我相信维基百科有一个很好的评论。如果我记得正确，那些仅允许凸多边形的算法速度要快得多。
- Arachnid
0
我相信你正在寻找的是A*算法，它在寻路中被使用。
- Woot4Moo
-1
天真的方法是找到红色和50个蓝色物体之间的距离——因此您需要进行50个3D勾股计算+排序才能找到答案。但这只适用于查找中心点之间的距离。
如果您想要任意多边形，也许最好的方法是使用射线跟踪解决方案，从红色多边形表面发射射线，并在撞击另一个多边形时报告。
混合方法可能有效——我们可以找到中心点之间的距离，假设我们有一些关于蓝色多边形相对大小的概念，我们可以将结果集削减到其中最接近的，然后使用射线跟踪来缩小真正最接近的多边形。
- Pete Michaud
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接