我的应用程序从 map 文件加载了大约 100k 个项目(矩形)的集合，然后构建一个 MX-CIF 四叉树作为快速查找的索引。四叉树是在启动时构建的，其内容在运行时不会改变。
(在 MX-CIF 四叉树中，项目由完全包含它的最小节点存储......内部和叶节点都可能包含项目)
在第一遍中，我找到了集合的外部范围，因此我知道根节点有多大。
在第二遍中，我将每个项目添加到完全包含它的最小节点。一旦一个节点通过了一定数量的项目，它就会被拆分，并且子节点在新的父节点和 4 个子节点之间重新分配。
鉴于我预先拥有所有项目，我如何才能更有效地构建树？
最佳答案
你真的需要一棵 MX-CIF 树吗？
对于矩形，我建议使用 X 树或 PH 树。
X 树源自 R 树，如果您事先知道整个数据集(批量加载)，则它具有极好的插入时间。它们还具有非常好的范围查询性能。可以在此处找到示例实现:
XXL Library
PH-Tree 在批量加载时稍慢，但如果对象在之后更新/移动，则速度会快得多。范围查询性能与 X-tree 相似，但 PH-tree 在提取小结果集时更快(主要成本在于提取值，而对于 X-tree 主要成本在于处理查询(找到第一个节点) , ...))。此处提供了 PH 树实现:PH-Tree
免责声明:我参与了 PH 树的开发。
关于spatial - MX-CIF 四叉树的批量加载算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6950150/