algorithm - 使用多边形 MBR 的 R-Tree 构建算法

Question

当我的集合中有所有已知的多边形最小外接矩形 (MBR) 时，我似乎找不到任何关于如何构建 R 树的文档。 R-Tree 非常适合存储这些空间引用，以消除我当前对多边形相交的蛮力检查:

for p1 in polygons: # O(n)
    for p2 in polygons: # O(n)
        if p2 is not p1: # O(1)
            if p2.intersects(p1): # O(1); computed using DeMorgans law on vertices
                # do stuff

是否有人有引用指示如何确定包含集合中多边形的 MBR 的矩形的分区方法？

Answer 1

R-Tree 划分算法有很多，根据我的经验，最好的一个是 Beckmann 等人的 R*Tree (R-Star-Tree)。只需搜索 "The R*-tree: an efficient and robust access method for points and rectangles" .

如果您更喜欢阅读代码，还有许多开源实现，包括 my own one in Java .不过请注意，R*Tree 算法并不简单。

如果您正在寻找更简单的东西，请尝试四叉树或八叉树。如果插入和更新速度是重中之重，请查看 PH-Tree (同样是我自己的实现)，但它也比四叉树更复杂。

另一个更简单的解决方案是 AABB-Tree ，它就像一个 R 树，但每个节点只有两个边界框。我认为它在计算机图形学中使用了很多，但我对它知之甚少，除了它对于 R-Tree 来说相对简单。

编辑(更新以回答评论)

如果您正在寻找 STR 等批量加载策略，here是原始论文。您可以查看我的 R-Tree 实现，因为它还提供了 implementation of an STR-Loader。可以处理点和矩形。

搜索堆栈溢出我还发现了this answer这显然指向一个专门用于存储矩形的替代散装装载机。

我想指出批量加载(例如 STR-Loading)是加载 R-Tree 的最快方式。然而，在我自己的实验中(参见 Figure 3 here)，这仍然比好的四叉树或 PH 树慢 2-3 倍。