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

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

请记住,将构成多边形顶点的点作为测试距离的值并不是一个简单的例子,因为它们可能不一定是最接近的点.

所以最后 - 答案应该将最接近的蓝色多边形返回到单一的红色多边形.

这比听起来更难!

我怀疑有更好的解决方案,而不是计算红色和蓝色之间的距离,并按长度排序.

关于排序,通常QuickSort在性能方面很难被击败(一个优化的,如果大小低于7项并且切换到类似InsertionSort,可能是ShellSort,则会切断递归).

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

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

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

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

以下是更高级边界框的示例图像,它与坐标系轴不平行:

定向边界框 - OBB

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

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

Axes Aligned Bounding Box - AABB

OOB更准确,AABB更快.也许你想阅读这篇文章:

高级碰撞检测技术

这总是假设,您愿意以精确度换取速度.如果精度比速度更重要,您可能需要更先进的技术.

您可以减少问题,然后在小集上进行密集搜索.

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

多边形的中心

多边形的最大半径(即,距离定义的中心最远的多边形的边缘/表面/顶点上的点)

现在你可以收集5-10个最近的多边形到红色的多边形(找到距离中心到中心,减去半径,对列表进行排序并占据前5个),然后做一个更详尽的例行程序.