使用STL map查找位于矩形区域内的点？

Question

我手头有许多x,y坐标点，每个点都有一些额外的数据与之相关联。这些额外的数据我将存储在一个结构体中。

我的应用程序需要在给定任意一个点的情况下，找出有多少其他点位于围绕该点的矩形区域内（该点位于矩形的中心）。

我想到的一种方法是将所有的x点作为键存储在一个Map A中，将所有的y点作为键存储在另一个Map B中。 Map A将以x为键，y值为值。 Map B将以y为键，关联的结构体为值。

这样，如果给定的点是(10.5,20.6)，我可以使用upper_bound(10.5+RECTANGLE_WIDTH)和lower_bound(10.5-RECTANGLE_WIDTH)来查找位于矩形内的x值范围，并对应的y值是否在+-20.6的范围内。

我使用Map的整个目的是因为我有大量的x,y点需要搜索，而且每两秒钟就要进行一次搜索。所以我必须使用Map的log(n)搜索。

但我感觉这可以用更有效率的方式来完成。有什么建议吗？

- Nav

---

@Nav 那就预先计算每个点附近的点数并将其添加到你的“结构”中，怎么样？ - Dr. belisarius

@belisarius：你还没有问这些矩形是否总是相同大小。 - Sven Marnach

@Sven 我以为他们是因为 OP 在变量名中使用了大写字母...也许我想多了 :D - Dr. belisarius

@belisarius：不错的建议，但我不想存储周围的点，因为这会占用大量额外的内存，并且我需要应用程序足够灵活，即使要搜索的点不在可用的静态常量点集中，程序也应该能够找到最近的点。是的，矩形的大小始终相同。 - Nav

所以我认为@Sven的答案是你正在寻找的。 - Dr. belisarius

Answer 1

这是一个典型的应用场景，需要使用四叉树。四叉树可以在O(log(n) + m)的时间复杂度内查找矩形中的m个点，其中n是所有点的总数。

补充说明：使用map的方法效率远不如四叉树。对于随机分布的点，它平均的时间复杂度为O(sqrt(n))，最坏情况下为O(n)。

- Sven Marnach

---

实际上，我听说 http://en.wikipedia.org/wiki/Hilbert_curve 比四叉树更高效。只是我从未使用过其中任何一个，所以我认为地图会更快实现。 - Nav

@Nav：我认为基于空间填充曲线的数据结构不可能比四叉树更高效。而且它实现起来肯定更加繁琐。四叉树真的很容易，你可以试一下！ - Sven Marnach

肯定某种空间索引是正确的选择 - 我们不确定有足够的信息来确定哪种类型最好 - 尽管四叉树可能是一个不错的起点。 - jk.

jk：谢谢你的指点。学习四叉树算法比实现地图要花费更多时间，但会是一个更好的投资。 - Nav

Answer 2

你可以将这些点存储为一个简单的二维结构体指针数组，需要查找某个点(x,y)时只需进行简单的索引操作。同样的，对于任何其他点(x+a,y+b)也是如此。

- Dominik Grabiec

---

你假设 x，y 是整数吗？ - Dr. belisarius

这对于大部分点填充的小区域非常有效，但对于大空间特别是稀疏的区域效果非常差。 - Fred Nurk

我一开始以为它们是整数点。但只要你能适当地四舍五入，使用浮点数也相对容易。 - Dominik Grabiec

根据问题陈述，我假设地图上的每个点都有一个相关联的结构，但我使用指针留下了可能存在空区域的可能性。 - Dominik Grabiec

Answer 3

如果您使用点的std::map，查找将始终为O(log N)，其中N是您拥有的点数。

您的另一个选择是将搜索空间分成桶，并将您的点放入桶中。 然后在您的矩形中计算：

• 所有点都在您的矩形内的任何桶
• 存在一些重叠的桶。

对于那些存在一些重叠的部分，您可以使用正确的桶类型每个桶查找，在您的集合中查找它们为O(M),但M应该小于N。 甚至可能会很少超过几个，因此您可以线性地检查它们。

计算哪些桶重叠是一个恒定时间操作，但您必须线性地运行这些操作（甚至要检查它们是否为空），因此拥有太多桶也可能是一个问题。

- CashCow

Answer 4

首先观察到的是，在任何情况下，std::map 都不是最有效的结构。从评论中可以看出，您的输入基本上是固定的。在这种情况下，对排序后的 std::vector 进行 std::binary_search 更有效。与排序后的 std::vector 相比，std::map 的主要优点是插入为 O(log N) 而不是 O(N)，而您并不需要这个。

接下来的观察是，您可能可以在第一阶段稍微不准确一些。您的输出集很可能比点的总数要小得多（否则就需要进行线性搜索）。但是假设是这种情况，您可能会受益于将矩形四舍五入。这将导致更多的候选点，然后您再检查它们是否在精确边界内。

例如，如果您的点在（0,0）和（200,300）之间的XY平面上随机分布，那么可以创建一个20x30矩阵，每个矩阵都包含一个大小为（10,10）的子区域。如果您现在需要从（64,23）到（78,45）的矩形中获取点，则需要检查子区域 [6,2]，[6,3]，[6,4]，[7,2]，[7,3]和[7,4] - 仅有600个中的6个。在第二步中，您将放弃类似于（61,25）的结果。

- MSalters