快速算法查找矩形内的所有点

给定2D空间中的一组不同点,以及矩形(所有四个点的坐标,与xy轴平行的边),如何快速找到矩形内的哪些点？

我对通过所有点并看到哪个点位于矩形内的基本解决方案不感兴趣.我正在寻找的是一种算法,它可以为每个矩形提供快速的查询时间.

我不在乎我在预处理步骤中花了多少时间.我所关心的是,在处理完数据之后,我获得了一个有用的结构,它为每个矩形提供了快速的查询时间.

我知道例如我可以计算O(logN)中矩形内有多少个点.这是有效的,因为我在开始时做了很多繁重的处理,然后每次用新的矩形查询处理过的数据,并在logN时间内得到一个新的计数.我正在寻找一种类似的算法,用于找到实际的点,而不仅仅是它们的数量.

经典答案是kD树(在这种情况下是2D树).

对于一个简单的替代方案,如果您的点分布足够均匀,您可以尝试网格化.

为方形网格选择单元格大小(如果问题是各向异性的,请使用矩形网格).将每个点分配给包含它的网格单元,存储在链表中.执行查询时,查找与矩形重叠的所有单元格并扫描它们以遍历其列表.对于部分覆盖的单元格,您需要执行矩形点测试.

尺寸的选择很重要:太大可能导致需要测试太多的点; 太小会导致太多空单元格.