5

我有大量的 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 建议的通过所有点进行线性搜索更有效。不过，我还是会试一试！我不希望用户非常频繁地设置矩形。因此，关于实施工作，它可能对我来说是一个很好的解决方案。

4

6 回答 6

6

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

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

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

于 2008-11-19T20:35:25.443 回答
3

请看这个问题。 Stony Brook Algorithm Repository有一些 KDTrees 在 C++ 中的实现，尽管它们不是 STL 或 Boost 的一部分。

于 2008-11-19T20:35:42.527 回答
2

对数组进行排序需要 O( n log n ) 时间。简单地单独检查每个点（不排序）需要 O( n ) 时间。

因此，只需遍历并检查每个点比排序要快。它也比构建四叉树更快。

编辑：如果你有很多矩形要检查，那就另当别论了。但是，如果您只需要检查一小部分固定数量的矩形，那么只需以“明显”的方式进行操作！

于 2008-11-19T21:11:31.767 回答
1

使用四叉树，您有 3 种类型的 qtree 节点：

  1. 节点在目标矩形之外：忽略
  2. 节点在目标矩形内：包括节点内的所有点
  3. 节点部分位于矩形之外：对节点内的点进行边界检查
于 2008-11-19T20:35:33.227 回答
1

在 Yuval F 的链接之后，我找到了Range Search，这似乎正是您正在寻找的东西。我从那里找到了一些链接，找到了CGAL，一个开源 C++ 库，它实现了范围搜索，这里有示例。

于 2008-11-19T20:55:34.327 回答
-1

您的排序函数可以在为矩形内部添加点时检查点，并将矩形内的所有点排序在矩形外的所有点之前。您必须跟踪每个存在的数量，或者对整个集合使用二进制搜索以在查找时找到截止点。

于 2008-11-19T20:43:59.000 回答