找到两个多边形之间最短笛卡尔距离的最快方法是什么
我说有1个红色多边形，有50个随机放置的蓝色多边形，它们位于2D地理空间中。找到红色多边形与其最近的蓝色多边形之间最短距离的最快/最快算法是什么？
请记住，将构成多边形顶点的点作为值来测试距离并不是一个简单的情况，因为它们不一定是最接近的点。
因此，最后的答案应该是将最接近的蓝色多边形归还给单个红色多边形。
这比听起来难！
解决方案
回答
也许Frechet距离是我们想要的？
计算两条多边形曲线之间的Frchet距离
计算简单多边形之间的摩擦距离
回答
天真的方法是找到红色和50个蓝色物体之间的距离-因此，我们正在查看50个3d勾股数计算+排序以找到答案。不过，那只会真正找到中心点之间的距离。
如果要使用任意多边形，也许最好的选择是光线跟踪解决方案，该解决方案从红色多边形的表面相对于法线发出光线，并在命中另一个多边形时报告。
混合可能会起作用-我们可以找到距中心点的距离，假设我们对蓝色多边形的相对大小有一定的了解，我们可以将结果集剔除为最接近的那些，然后使用光线跟踪来缩小真正最接近的范围多边形。
回答
对于具有合理数量边界点的多边形形状(例如在GIS或者游戏应用程序中)，进行一系列测试可能会更容易一些。
对于红色多边形中的每个顶点，计算到蓝色多边形中每个顶点的距离，并找到最接近的顶点(提示，比较距离^ 2，因此不需要sqrt())
找到最接近的线，然后检查找到的红色和蓝色顶点的每一侧的顶点，以确定哪些线段最接近，然后找到两个线段之间的最接近方法。
参见http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline3d/(对于2d情况很简单)
回答
我怀疑有更好的解决方案，而不是计算红色和蓝色之间的距离并按长度对它们进行排序。
关于排序，通常QuickSort的性能很难被超越(一种优化的方法，如果大小低于7个项目并切换到类似InsertionSort(也许是ShellSort)，它将切断递归)。
因此，我想问题是，如何快速计算两个多边形之间的距离，毕竟我们需要进行50次计算。
以下方法也适用于3D，但可能不是最快的方法：
二维空间中的最小多边形距离
问题是，我们是否愿意为了速度而牺牲准确性？例如。我们可以将所有多边形打包到边界框内，边界框的边与坐标系轴平行。 3D游戏经常使用这种方法。因此，我们需要找到每个坐标(x，y，z)的最大值和最小值，以构造虚拟边界框。计算这些边界框的距离是一件很简单的任务。
这是更高级的边界框的示例图像，这些边界框不平行于坐标系轴：
定向包围盒OBB
然而，这使得距离计算变得不那么琐碎。它用于碰撞检测，因为我们不需要知道距离，因此只需要知道一个边界框的一个边缘是否位于另一个边界框内即可。
下图显示了轴对齐的边界框：
轴对齐边界框AABB
OOB更准确，AABB更快。也许我们想阅读这篇文章：
先进的碰撞检测技术
这始终是假设，我们愿意为了速度而牺牲精度。如果精度比速度更重要，则可能需要更先进的技术。
回答
我们也许可以减少问题，然后对一小部分进行深入的搜索。
首先通过找到以下内容处理每个多边形：
- 多边形中心
- 多边形的最大半径(即距定义中心最远的多边形的边/表面/顶点上的点)
现在，我们可以收集到例如距离红色最近的5-10个多边形(找到距离中心至中心，减去半径，对列表进行排序，然后取前5个多边形)，然后执行更为详尽的例程。
回答
我们可以先比较边界框之间的距离。测试矩形之间的距离比测试多边形之间的距离更容易，并且我们可以立即消除距离Nearest_rect + its_diagonal更大的任何多边形(可能可以进一步优化)。然后，我们可以测试其余的多边形以找到最接近的多边形。
有确定多边形接近度的算法，我相信维基百科对此有很好的评价。如果我没记错的话，那些只允许凸多边形的对象要快得多。
回答
我知道我们说的是"最短距离"，但我们实际上是说，最佳解决方案还是"好/非常好"解决方案适合问题？
因为如果我们需要找到最佳解决方案，则必须计算所有源和目标poligon边界(不仅是顶点)之间的距离。如果我们在3D空间中，则每个边界都是一个平面。这可能是一个大问题(O(n ^ 2))，具体取决于我们拥有多少个顶点。
因此，如果我们拥有的顶点数使该平方成为一个令人恐惧的数字，并且"好/非常好"的解决方案对我们来说很好，那么请寻求启发式解决方案或者近似值。
回答
这种筛选技术旨在减少平均情况下需要执行的距离计算的数量，而不会影响结果的准确性。它适用于凸面和凹面多边形。
找到每对顶点之间的最小距离，以使一个顶点为红色顶点，而一个顶点为蓝色。称它为r。多边形之间的距离最大为r。从红色多边形构造一个新区域，在该区域中，每个线段均以r向外移动，并通过半径为r的圆弧(以顶点为中心)与其相邻线段相连。找到从该区域内的每个顶点到与该区域相交的相反颜色的每个线段的距离。
当然，我们可以添加一种近似方法(例如边界框)来快速确定哪些蓝色多边形不可能与红色区域相交。
回答
我们可能想看看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
但这全取决于数据。如果蓝色多边形与红色多边形之间的距离相比较小，则此方法应能很好地工作，但是如果它们非常接近，则我们将不会保存任何内容(其中许多会足够接近)。还有一件事-如果这些多边形没有很多顶点(例如，如果它们中的大多数是三角形)，那么将每个红色边缘与每个蓝色边缘进行检查可能几乎一样快。
希望能帮助到你
回答
正如其他人提到的那样，使用边界区域(框，圆)可以使我们放弃某些多边形-多边形交互。为此有几种策略。
- 选择任何一个蓝色多边形，并找出与红色多边形的距离。现在选择任何其他多边形。如果边界区域之间的最小距离大于已经找到的距离，则可以忽略此多边形。继续所有多边形。
- 找到红色多边形和所有蓝色多边形之间的最小距离/质心距离。排序距离并首先考虑最小距离。计算实际的最小距离，然后继续进行排序，直到多边形之间的最大距离大于到目前为止找到的最小距离。
根据输入多边形的实际布局，选择的圆形/轴向对齐的框或者定向的框可能会对算法的性能产生很大影响。
对于实际的最小距离计算，我们可以使用Yang等人的"一种新的快速算法，该算法基于Voronoi图计算两个不相交的凸多边形之间的距离"为O(log n + log m)。
回答
可以在几秒钟内完成葬礼，但是如果将多边形分解为凸子策略，则可以进行一些优化。我们可以在每个多边形上进行二进制搜索以找到最接近的顶点，然后我相信最接近的点应该是该顶点或者相邻的边。这意味着我们应该能够在log(log m * n)中进行操作，其中m是多边形上顶点的平均数量，n是多边形的数量。这有点仓促，所以可能是错误的。如果需要，稍后将提供更多详细信息。
回答
我相信我们正在寻找的是A *算法，它在寻路中使用。
