spatial - MX-CIF 四叉树的批量加载算法

Question

我的应用程序从 map 文件加载约 100k 项(矩形)的集合，然后构建 MX-CIF 四叉树作为快速查找的索引。四叉树是在启动时构建的，其内容在运行时不会更改。

(在 MX-CIF 四叉树中，项目由完全包含它的最小节点存储......内部节点和叶节点都可能包含项目)

在第一遍中，我找到了集合的外部范围，因此我知道根节点有多大。

在第二遍中，我将每个项目添加到完全包含它的最小节点。一旦节点传递了一定数量的项目，它就会被拆分，并且子节点将在新的父节点和 4 个子节点之间重新分配。

鉴于我预先拥有所有项目，我怎样才能更有效地构建树？

Answer 1

您真的需要 MX-CIF 树吗？对于矩形，我建议使用 X 树或 PH 树。

X 树源自 R 树，如果您提前知道整个数据集(批量加载)，则其插入时间会很短。它们还具有非常好的范围查询性能。可以在此处找到示例实现: XXL Library

PH-Tree 在批量加载时稍微慢一些，但如果之后更新/移动对象，速度会快得多。范围查询性能与X树类似，但是PH树在提取小结果集时速度更快(主要成本在于提取值，而对于X树来说主要成本在于处理查询(找到第一个节点) ，...))。 PH 树实现可在此处获得:PH-Tree

免责声明:我参与了 PH-tree 的开发。