c++ - 使用 STL map 搜索位于矩形区域中的点？

Question

我有很多 x,y 点，每个 x,y 点都有一些与之相关的额外数据。我将把这些额外数据存储在一个结构中。我的应用程序要求给定任何一个点，我必须找出在该点周围的矩形区域内还有多少其他点(该点位于矩形的中心)。

我想到的一个逻辑是将所有 x 点存储为 map A 中的键，将所有 y 点存储为另一个 map B 中的键。映射 A 将 x 作为键，y 值作为值。Map B 将以 y 作为键，将关联的结构作为值。

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

我使用 map 的全部目的是因为我有大量的 x,y 点存储，并且必须每两秒进行一次搜索。所以我不得不使用 map 的 log(n) 搜索。我觉得这可以用更有效的方式来完成。有什么建议吗？

Answer 1

这是 quadtree 的典型应用.四叉树有助于在 O(log(n) + m) 中查找位于矩形中的 m 个点，其中 n 是点的总数。

编辑:您使用 map 的方法效率不高。对于随机分布的点，它的平均复杂度为 O(sqrt(n))，最坏情况为 O(n)。