存储 2D 点以便快速检索矩形内的点
我有大量的 2D 点，我想快速获取位于某个矩形内的那些点。 让我们说一个“.” 是任何点，“X”是我想在一个矩形内找到的点，该矩形的“T”作为左上点，“B”作为右下点：
. . . . . .
. T-----+ .
. | X X | .
. +-----B .
. . . . . .
我尝试了一个带有排序函子的 std::set ，该函数对左上点进行排序该组的开头和结尾处的 BottomRight。 当首先按X值排序时，这将导致找到以下点。
. . . . . .
. T-----+ .
X | X X | X
. +-----B .
. . . . . .
这意味着我必须检查每个找到的点，它是否真的在矩形内。 不太好。
更好的方法是什么？
我的语言是 C++ (Windows)，我有 STL 和 boost 可用。
更新
到目前为止，阅读完答案后，我注意到我没有考虑问题的所有参数：没有一个固定的矩形。 用户可以在运行时设置矩形。 这意味着对点集进行排序有望比 Artelius 在此更新之前建议的对所有点进行线性搜索更有效。 不过我还是会尝试一下！ 我不希望用户非常频繁地设置矩形。 因此，就实施工作而言，它对我来说可能是一个很好的解决方案。
I have a large number of 2D points and I want to quickly get those that lie in a certain rectangle.
Let's say a '.' is any point and 'X' is a point I want to find inside a rectangle which has 'T' as TopLeft and 'B' as BottomRight points:
. . . . . .
. T-----+ .
. | X X | .
. +-----B .
. . . . . .
I have tried a std::set with a sort functor which sorts the TopLeft point at the beginning and the BottomRight at the end of the set. When sorting by X value first, this would result in the following points being found.
. . . . . .
. T-----+ .
X | X X | X
. +-----B .
. . . . . .
This means I would have to check each found point, whether it really is inside the rectangle. Not really good.
What would be a better way to do this?
My language is C++ (Windows) and I have the STL as well as boost available.
Update
Having read the answers so far, I noticed that I haven't accounted for all parameters of my problem: There is not one fixed rectangle.
Rectangles can be set by the user at runtime. This means sorting the set of points promises to be more efficient than a linear search through all points as suggested by Artelius before this update.
I will still give it a try, though! I don't expect the user to set a rectangle very frequent. So regarding the implementation effort it might show up to be a good solution for me.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
您可以使用四叉树或 r 树将点存储在空间索引中。 然后，给定矩形，您可以找到与它重叠的树的所有节点，然后您必须比较该子集中的每个点，看看它是否落在矩形内。
本质上，空间树可以帮助您修剪搜索空间。
您也许可以使用更简单的解决方案，例如对范围内的点进行分区。 假设 x 是从 0,10 作为一个范围，11,20 作为另一个范围。 任何可以让您修剪搜索空间的解决方案都会有所帮助。
You could store the points in a spatial index using quad or r-trees. Then given the rectangle you could find all the nodes of the tree that overlap it, you would then have to compare each point in this subset to see if it falls in the rectangle.
In essence, the spatial tree helps you prune the search space.
You might be able to use a simpler solution, such as partitioning the points in ranges. Say where x is from 0,10 as one range, 11,20 as another. Any solution that lets you prune the search space will help.
请参阅此问题。
Stony Brook 算法存储库 有一些 KDTree 的实现C++,
尽管它们不是 STL 或 Boost 的一部分。
Please see this question.
The Stony Brook Algorithm Repository has some implementations of KDTrees in C++,
though they are not part of STL nor Boost.
对数组进行排序需要 O(nlogn) 时间。 简单地单独检查每个点（不排序）需要 O(n) 时间。
因此，仅仅遍历并检查每个点比排序更快。 而且它也比构建四叉树更快。
编辑：如果您有很多矩形要检查，那就是另一回事了。 但如果您只需要检查少量固定数量的矩形，那么就用“显而易见”的方式来做！
Sorting an array takes O(nlogn) time. Simply checking each point individually (without sorting) takes O(n) time.
Ergo, just going through and checking each point is faster than sorting. And it's faster than building a quadtree too.
EDIT: If you have many rectangles to check, it's a different story. But if you only need to check a small, fixed number of rectangles then just do it the "obvious" way!
使用四叉树，您有 3 种类型的 qtree 节点：
use a quadtree, and you have 3 types of qtree nodes:
按照 Yuval F 的链接，我找到了 Range Search，它似乎正是您正在寻找的东西。 我从那里跟踪了一些链接，发现 CGAL，一个开源 C++ 库，它实现了范围搜索，示例此处。
Following Yuval F's link, I found Range Search, which appears to be the exact sort of thing you're looking for. I followed some links from there, and found CGAL, an open source C++ library, which implements a range search, with examples here.
您的排序函数可以在添加点时检查矩形内部的点，并将矩形内部的所有点排序在矩形外部的所有点之前。 您必须跟踪每个存在的数量，或者对整个集合使用二分搜索来找到查找时的截止点。
Your sort function could check points as they are added for inside-the-rectangle-ness, and sort all points inside the rectangle before all points outside the rectangle. You would have to keep track of how many of each exist, or use a binary search on the entire set to find the cutoff point at lookup time.