1

我正在寻找一种支持查找“n”个区域中的哪个包含点“p”的数据结构。我正在查看 Quadtree 和 R-tree，但我认为它们并不完全符合我的要求。

本质上，我希望能够向这棵树添加一些 3 维矩形区域，然后能够针对这棵树测试一个 3 维点并返回哪个区域最严格地约束该点。没有区域会有重叠的边界。

我目前使用的简单算法是针对每个矩形区域的每个维度简单地测试点“p”。

for(region in regionList):
    if(p.x > region.x1 && p.x < region.x2 && p.y > region.y1 && py < region.y2 && p.z > region.z1 && p.z < region.z2)
        return region
end

这在 O(n) 时间内运行，其中 n 是区域数。我希望搜索将 O(log n) 作为四叉树用于查找 2d 点的点。

4

2 回答 2

0

查看Segment Trees和KD Trees。

于 2013-02-05T05:56:31.840 回答
0

我建议使用 QuadTree 来存储像 MX-CIF 树这样的区域。它本质上是一个基于二维 (x,y) 的四叉树。一旦找到包含 (x,y) 方面的点的适当节点，您可以检查它是否包含所有三个 (x,y,z) 维度中的点。

我在 Java 中做过类似的事情。

您还可以查看八叉树，它是一个 3 维四叉树。

于 2013-02-05T17:12:06.993 回答