存储2D点以快速检索矩形内的那些点

我有大量的2D点,我想快速得到那些位于某个矩形的点.让我们说一个'.' 是任何一点,'X'是我想要在一个矩形内找到的一个点,其中'T'为TopLeft,'B'为BottomRight点:

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

我尝试了一个带有排序函数的std :: set,它将开头的TopLeft点和集合末尾的BottomRight排序.首先按X值排序时,这将导致找到以下几点.

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

这意味着我必须检查每个找到的点,它是否真的在矩形内.不是很好.

什么是更好的方法来做到这一点？

我的语言是C++(Windows),我有STL以及可用的提升.

更新

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

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

从本质上讲,空间树可以帮助您修剪搜索空间.

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