代码之家 › 专栏 › 技术社区 › pstatix

基于多边形MBR的R树构造算法

r-tree binary-search-tree algorithm

pstatix · 技术社区 · 6 年前

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

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的方法?

1 回复 | 直到 6 年前

TilmannZ 6 年前

"The R*-tree: an efficient and robust access method for points and rectangles" .

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

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

AABB-Tree ,它类似于R树,但每个节点只有两个边界框。我认为它在计算机图形学中有很多应用,但我对它了解不多,只知道它对于R树来说相对简单。

(更新以回答评论)

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

搜索堆栈溢出我也发现了 this answer

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

推荐文章

mourinho · Python中按顺序遍历树返回列表

7 年前

Dongho Han · 用C语言中的二叉搜索树查找合计

7 年前

Richard Cooper · 使用递归的C++二叉搜索树

7 年前

Pranshu · 无法删除二进制搜索树中的根节点

7 年前

user2411290 · BST Delete函数不删除目标节点(Java)

7 年前

Shuklaswag · 为什么我们要通过堆而不是二进制搜索树进行排序?

7 年前

Vanshaj · 给定的数字序列是否有唯一的二进制搜索树?

7 年前

M.Hamra · 如何编写递归函数来返回BST中的最小值?

7 年前

Matt · 二进制搜索树遍历方法,以便字符串

7 年前

I.Klein · 递归获取二叉搜索树的高度[闭合]

7 年前