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

Question

给定二维空间中的一组不同点和一个矩形(所有四个点的坐标，与 xy 轴平行的边)我如何快速找到矩形内的点？

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

我不在乎我在预处理步骤上花费了多少时间。我关心的是，在我处理完数据后，我获得了一个有用的结构，它让我可以快速查询每个矩形。

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

Answer 1

经典答案是 kD 树(在本例中为 2D 树)。

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

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

大小的选择很重要:太大会导致无论如何都需要测试太多点；太小会导致空单元格过多。