什么是找两个多边形之间的最短距离笛卡尔的最快方法
我的 1红多边形说和 50随机放置蓝色多边形 - 它们都位于地理 2D空间。什么是最快/最快algorithim找到一个红色的多边形和它最接近的蓝色面之间的最短距离？
I have 1 red polygon say and 50 randomly placed blue polygons - they are situated in geographical 2D space. What is the quickest/speediest algorithim to find the the shortest distance between a red polygon and its nearest blue polygon?
记住，这是不采取构成多边形作为值的顶点的点来测试距离，因为它们可能不一定是最接近的点的简单情况。
Bear in mind that it is not a simple case of taking the points that make up the vertices of the polygon as values to test for distance as they may not necessarily be the closest points.
那么，到底 - 答案应该还给最接近蓝色多边形奇异红色
So in the end - the answer should give back the closest blue polygon to the singular red one.
这是难度比它的声音！
我怀疑是不是计算红色的，每个蓝色的之间的距离和长度整理这些更好的解决方案。
I doubt there is better solution than calculating the distance between the red one and every blue one and sorting these by length.
对于分选，通常快速排序很难在性能上击败（优化的一个，那切断，如果规模低于7项递归并切换到像InsertionSort，也许希尔）。
Regarding sorting, usually QuickSort is hard to beat in performance (an optimized one, that cuts off recursion if size goes below 7 items and switches to something like InsertionSort, maybe ShellSort).
所以我猜问题是如何快速计算出距离的两个面之间，毕竟你需要做这个计算50次。
Thus I guess the question is how to quickly calculate the distance between two polygons, after all you need to make this computation 50 times.
下面的方法将进行3D工作为好，但很可能不是最快的国家之一：
The following approach will work for 3D as well, but is probably not the fastest one:
现在的问题是，你是否愿意速度贸易准确性？例如。你可以打包所有多边形到边界框，在这里的箱子边平行于坐标系坐标轴。 3D游戏使用这种方法pretty的频繁。为此需要找到最大和最小值为每个坐标（x，Y，Z）来构造虚拟边界框。计算这些包围盒的距离是那么pretty的简单的任务。
The question is, are you willing to trade accuracy for speed? E.g. you can pack all polygons into bounding boxes, where the sides of the boxes are parallel to the coordinate system axes. 3D games use this approach pretty often. Therefor you need to find the maximum and minimum values for every coordinate (x, y, z) to construct the virtual bounding box. Calculating the distances of these bounding boxes is then a pretty trivial task.
下面是更先进的包围盒的实例图像，不平行于坐标系轴：
Here's an example image of more advanced bounding boxes, that are not parallel to the coordinate system axes:
不过，这使得距离计算就更不值一提。它是用于碰撞检测，因为你不需要知道的是，距离，你只需要知道，如果一个边界框的一个边缘中的另一个边界框之所在。
However, this makes the distance calculation less trivial. It is used for collision detection, as you don't need to know the distance for that, you only need to know if one edge of one bounding box lies within another bounding box.
下图显示了一个轴对齐包围盒：
The following image shows an axes aligned bounding box:
OOBs更准确，是的AABB更快。也许你想看看这篇文章：
OOBs are more accurate, AABBs are faster. Maybe you'd like to read this article:
这总是假定，你是愿意交易precision速度。如果precision比速度更重要的是，你可能需要一个更先进的技术。
This is always assuming, that you are willing to trade precision for speed. If precision is more important than speed, you may need a more advanced technique.