c++ - 区域搜索中的点

Question

我有接近 Nearest neighbour search 的问题，但不完全是。

对于二维空间中给定的矩形区域(与轴对齐)，我需要找到属于该区域的所有点。 我可以提前准备好关于我的积分集的任何数据。我对点坐标有限制(假设我们拥有的所有点在 X 和 Y 坐标中都在从 0 到 1 的区域内)。

查询数量(区域)>>点数。因此，我的优先事项是:

1. QueryTime - 按地区获取积分的时间。
2. MemorySize - 我需要的额外内存大小(用于准备)。
3. PreparationTime - 额外的数据准备时间。

哪些算法适用于此？(如果有关于该主题的书籍或文章，我会很高兴)。

---

例子:

我有一个点坐标数组，都在 0 到 1 的范围内:

{0.1224,0.2345}, {0.01,0.99}, {0.94,0.5}

并获取一个查询以查找 X 中从 0.1 到 0.2 和 Y 中从 0.2 到 0.4 的区域中的所有点。

然后我需要找到第一个点 {0.1224,0.2345}。

Answer 1

听起来你有一些比赛条件。目前还不清楚你是怎么做到的。 通常的方法是单线程准备，卡住结构(在任何地方都将其作为 const 传递)，然后所有查询都可以在没有协调的情况下并行运行，因为结构是不可变的。

另一种方法是 KD 树或四叉树。您可能会遇到与现在相同的种族问题。 但是，如果您想尝试一下，请使用随机点，或者如果您负担得起，请为拆分选择最佳点(但在实践中应该无关紧要)。 您将得到类似 O(logNP + R) 的结果，其中 R 是结果中的点数。

http://en.wikipedia.org/wiki/Kd_tree http://en.wikipedia.org/wiki/Quadtree