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

Question

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

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

希尔伯特曲线

显然，深度 3 对这个搜索是最优的，但是与从深度 1 到深度 2 的下降相比，缩小的搜索空间只下降了一小部分。

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

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

score 1 · Accepted Answer

尽管您的问题需要更多详细信息，但需要一些答案：

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

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

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

score 0 · Accepted Answer

当您使用希尔伯特曲线时，它是空间索引，而不是四叉树。四叉树也有一些限制，例如您可以存储多少点。因此，在希尔伯特曲线上，最好使用小图块，这样边界框就可以很好地拟合。

2 回答 2