当我的集合中拥有多边形的所有已知最小边界矩形 (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 的矩形的分区的方法？
有许多R-Tree分区算法，根据我的经验，最好的一种是Beckmann等人的R*Tree(R-Star-Tree(。只需搜索"R*树：一种高效而强大的点和矩形访问方法"。
如果你更喜欢阅读代码，也有许多开源实现，包括我自己的Java实现。但请注意，R*Tree 算法并非微不足道。
如果您正在寻找更简单的东西，请尝试四叉树或八叉树。如果插入和更新速度是重中之重，请查看PH-Tree(再次是我自己的实现(，但它也比四叉树复杂。
另一个更简单的解决方案是AABB-Tree，它就像一个R-Tree，但每个节点只有两个边界框。我认为它在计算机图形学中被大量使用，但我对它了解不多，除了它对于 R 树来说相对简单。
编辑(更新以回答评论(
如果您正在寻找像STR这样的批量加载策略，这里是原始论文。你可以看看我的R-Tree实现，因为它还提供了可以处理点和矩形的STR-Loader的实现。
搜索堆栈溢出，我还发现了这个答案，它显然指向专门用于存储矩形的替代批量加载器。
我想指出的是，批量加载(例如 STR-Load(是加载 R 树的快速方法。然而，在我自己的实验中(参见图3(，这仍然比一个好的四叉树或PH树慢2-3倍。