代码之家 › 专栏 › 技术社区 › 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倍。

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

1 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前