c++ - 存储 2D 点以便快速检索矩形内的点

Question

我有大量的 2D 点，我想快速获取位于某个矩形内的点。让我们说一个'。是任意点，“X”是我想在矩形内找到的点，矩形内的“T”为 TopLeft，“B”为 BottomRight 点:

. . . . . .
. T-----+ .
. | X X | .
. +-----B .
. . . . . .

我尝试了一个带有排序仿函数的 std::set ，它对集合开头的 TopLeft 点和集合结尾的 BottomRight 点进行排序。当首先按 X 值排序时，这将导致找到以下点。

. . . . . .
. T-----+ .
X | X X | X
. +-----B .
. . . . . .

这意味着我必须检查每个找到的点，是否真的在矩形内。不太好。

执行此操作的更好方法是什么？

我的语言是 C++ (Windows)，我有 STL 和可用的 boost。

更新

到目前为止阅读答案后，我注意到我没有考虑问题的所有参数:没有一个固定的矩形。矩形可以由用户在运行时设置。这意味着对点集进行排序有望比 Artelius 在此更新之前建议的对所有点进行线性搜索更有效。不过，我仍然会尝试一下!我不希望用户非常频繁地设置矩形。因此，关于实现工作，它可能对我来说是一个很好的解决方案。

Answer 1

您可以使用四叉树或 r 树将点存储在空间索引中。然后给定矩形，您可以找到与它重叠的树的所有节点，然后您必须比较该子集中的每个点，看它是否落在矩形内。

本质上，空间树可以帮助您修剪搜索空间。

您可以使用更简单的解决方案，例如在范围内划分点。假设 x 从 0,10 作为一个范围，从 11,20 作为另一个范围。任何可以让您修剪搜索空间的解决方案都会有所帮助。