我有一个不必与轴平行的矩形列表。我还有一个与轴平行的主矩形。
我需要一种算法来判断哪个矩形是最接近的点(该点必须位于主矩形中)。矩形列表和主矩形在算法过程中不会改变，并且会被很多点调用，因此应该创建一些数据结构以使查找更快。
需要明确的是:矩形到点的距离是矩形中最近的点到该点的距离。
可以使用什么算法/数据结构来实现此目的？内存对此具有更高的优先级，n log n 可以，但 n^2 不行。
最佳答案
您应该能够使用 Voronoi 图来完成此操作，其中预处理时间为 O(n log n)，查询时间为 O(log n)。由于对象是矩形而不是点，因此单元格可能是弯曲的。尽管如此，Voronoi 图应该可以很好地满足您的目的。 (参见http://en.wikipedia.org/wiki/Voronoi_diagram)
对于一个快速而肮脏的解决方案，您实际上可以在一天内开始工作，您可以做一些受局部敏感哈希启发的事情。例如，如果矩形间隔较好，您可以将它们散列到具有几个不同偏移量的方形存储桶中，然后对于每个查询，检查属于包含查询点的少数存储桶之一的每个矩形。
关于algorithm - 到矩形缓存的最短距离，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6171553/