到矩形缓存的最短距离

Question

我有一个矩形列表，它们不必与轴平行。我也有一个与轴平行的母版矩形。

我需要一个算法，可以告诉哪个矩形是最接近的点(该点必须在主矩形中)。矩形和母版矩形的列表在算法过程中不会改变，并且会被许多点调用，因此应该创建一些数据结构来加快查找速度。

需要说明的是:矩形到点的距离是矩形中最近的点到点的距离。

什么算法/数据结构可以用于此？内存在这方面具有更高的优先级，n log n是可以的，但n^2不是。

Answer 1

您应该能够使用具有O( n )预处理时间和O(log )时间查询的Voronoi图来做到这一点。因为对象是矩形，而不是点，所以单元格可能是弯曲的。然而，Voronoi图应该可以很好地满足您的需求。(参见http://en.wikipedia.org/wiki/Voronoi_diagram)

对于一个可以在一天内真正开始工作的又快又脏的解决方案，您可以做一些受位置敏感散列启发的事情。例如，如果矩形间隔得很好，您可以将它们散列到具有几个不同偏移量的正方形存储桶中，然后对于每个查询，检查落入包含查询点的少数几个存储桶之一的每个矩形。

Answer 2

你应该能够在O(n)时间和O(n)内存中做到这一点。

1. 计算每个矩形每条边上与相关点最近的点。要执行此操作，请参阅this question中的详细答案。即使问题必须与多边形内部(而不是多边形外部)的点有关，算法仍然可以应用于边上这些最近点之间的距离，并在整个矩形(对于每个矩形)上找到与所讨论的点最近的点。( here.
2. Calculate )有关更多详细信息，请参阅上面的链接。
3. 找到所有矩形之间的最小距离。与您的最小距离对应的矩形为获胜者。

Answer 3

如果内存比速度更有价值，可以使用暴力:对于给定的点S，计算从S到每条边的距离。选择距离最短的矩形。

这种解决方案不需要额外的内存，而执行时间为O(n)。

根据您的具体问题说明，如果允许矩形与主矩形重叠，则可能需要调整此解决方案。