algorithm - 在一组四叉树中找到最佳深度/范围以优化边界框中点的检索

Question

如果我有一组四叉树(比如在希尔伯特曲线上)，什么是在特定深度找到最佳(或足够好)范围集的好方法。

例如，如果我正在搜索边界框 0,0 和 1,3 之间的点，那么我可以应用以下原始范围:

• 深度 1 - 范围 0,0-1,0(~33% 搜索空间)
• 深度 2 - 范围 0,0-1,0和 1,0-0,1(~13% 的搜索空间)
• 深度 3 - 范围 0,0-1,0 和 1,3-0,3(~9.8% 的搜索空间)

显然深度 3 对于此搜索是最佳的，但与从深度 1 到深度 2 的下降相比，减少的搜索空间仅下降了一小部分。

在(很多)更大的深度，或者对于跨越边界的搜索，是否有一个很好的算法来估计不同深度之间的差异，或者理想地选择不同深度的范围的组合，以理想地覆盖边界框。

我对多边形特别不感兴趣，但如果有适用于多边形的解决方案，我会加分。

Answer 1

虽然您的问题需要更多详细信息，但需要一些答案:

您可以通过 log4(N) 来估计四边形的深度。
(取元素个数N以4为底的对数。)

根据四叉树的类型，您可以将最大深度限制为该数字。

插入元素的顺序会影响四边形的结构。在插入之前对数据进行预排序可以改进四边形结构。预排序的类型取决于四边形。如果您使用 hilbert 备份四边形，则可以按 hilbert 索引对数据进行预排序。