algorithm - 数据结构预处理给定的 N 点集并给定查询并行带输出所有点都位于带内

Question

我被要求设计一种算法来预处理给定的 N 个点集，例如给定的查询并行 strip ，输出所有点都位于 strip 内。

我尝试设计算法，但我只能单独解决查询。

我不知道使用哪种数据结构并预处理给定的 N 个点，这样我就可以轻松回答查询。

我只需要知道如何去做，以及它的复杂性。

Answer 1

解决此类问题的常用方法是使用 bounding volume hierarchy .

考虑将点打包在盒子中，然后将那些盒子打包在更大的盒子中，等等...如果您的一个较大的盒子完全在 strip 之外，那么您不需要检查它。但是，如果它在 strip 内，那么您将不得不看看里面有什么。如果里面的东西有一个不在 strip 中的盒子，你也不必检查那个盒子的内容。当然，关键是包装框，这样您通常可以跳过检查很多子框和点。

(请注意，并非所有 BVH 都使用盒子——一些使用球体，一些使用 simplices，一些使用有点奇怪的分区，但大多数使用盒子。)

R-trees在大型数据库中的二维应用程序中很受欢迎。您还可以使用 space partitioning结构(或多或少只是 BVH 的一种特殊化)，您可能会这样做，因为那里已经有很多用于 K-d 树(一种空间分区)的库。

无论你最终采用什么结构，顶层算法都将保持不变:

# This algorithm could be implemented with a stack or recursively
# instead of maintaining a potentially very long list of nodes.
nodes = { top_level_node }
loop while there are nodes left to process
    set node = first element of nodes
    remove node from nodes
    if node does not intersect strip continue loop
    if node directly contains points that are within the strip add them to the output
    if node directly contains subnodes that intersect the strip add them to nodes
end loop

根据您使用的结构，对于固定数量的维度，您可以预期一般行为是 O(o log n) 其中 n 是总点数，o 是 strip 内的点数。请注意，这个有点幼稚的算法使用 O(o) 内存，但如果使用堆栈或递归，它可以使用 O(log n) 代替。

Box2D 物理引擎有一个不错的 2D BVH 实现，非常容易使用。 (许可证看起来非常宽松。)Box2D 的 BVH 一度基于 Bullet 的(并且可能仍然如此)。 Bullet 物理引擎具有 3D BVH 实现，我之前已将其转换为 2D，并且它具有 zlib(非常宽松)许可证。实时物理引擎的问题在于它们通常对获得最优树不感兴趣——它们感兴趣的是在几毫秒内“尽可能好”地获得它，因为它们没有时间进行最优。但是，它们可能足以满足您的目的。

Rosettacode 甚至有一个 K-d tree entry -- 但你的里程数可能会有所不同，因为我希望这些条目比一个使用良好的库(例如 FLANN 我相信它包含一个 K-d 树)更少经过测试。