利用希尔弗特曲线查询矩形区域并查看它是否与其他矩形重叠

Question

我正在寻找一种方法，可以帮助我的项目，我正在工作。我的想法是，在2d空间中有一些矩形，我想查询一个矩形区域，看看它是否与该区域中的任何矩形重叠。如果是的话，那就失败了。如果没有，这意味着空间是空的，它就成功了。

我被连接到z阶曲线，以帮助将2d坐标转换为一维。当我读到它的时候，我遇到了希尔伯特曲线。我读到希尔伯特曲线比z阶曲线更可取，因为它保持了点的更接近。我还读到希尔伯特曲线被用来制造更有效的四叉树和八叉树。

我读这篇文章https://sigmodrecord.org/publications/sigmodRecord/0103/3.lawder.pdf是为了寻找一个可能的解决方案，但我不知道这是否适用于我的情况。

我还看到了这个注释https://news.ycombinator.com/item?id=14217760，它提到了非点对象的多个索引条目。

有没有一种优雅的方法，我可以用希尔伯特曲线来实现这一点？有可能只有一个矩形数组吗？

Answer 1

我很确定这是可能的，而且可以非常有效。但其中涉及到许多复杂的问题。

我为z阶曲线实现了这个函数，并将其命名为PH树，您可以在C++和Java中找到实现，以及链接中的理论背景。PH树类似于z序四叉树，但经过几次修改，允许充分利用空间填充曲线。

这里有几件东西要打开。

希尔伯特曲线与z阶曲线：是的，希尔伯特曲线比z阶曲线有更好的接近性.更好的接近可以做两件事: 1)减少要查看的元素(节点、数据)的数量；2)改进线性访问模式(减少跳跃)。如果空间索引存储在磁盘上，而I/O成本很高(特别是旧磁盘驱动器)，两者都很重要。

如果我没记错的话，希尔伯特曲线和z阶是相似的，所以总是访问相同数量的数据。希尔伯特曲线唯一擅长的是线性访问。然而，希尔伯特曲线的计算要复杂得多，在我用内存索引进行的测试中(我承认，不是很彻底的测试)，我发现z阶曲线的效率要高得多，因为CPU时间的减少超过了访问数据的成本。

空间填充曲线(至少希尔伯特曲线和z曲线)允许一些整洁的位级黑客，可以加快索引操作。然而，即使是z排序，我也发现要正确处理这些问题需要大量的思考(我为此写了一整篇论文)。我相信这些操作可以适应希尔伯特曲线，但我可能需要一些时间，正如我上面所写的，它可能根本不会提高性能。

在空间曲线索引中存储矩形：在空间曲线中对矩形进行编码有不同的方法。所有的方法，我知道编码矩形在一个多维点。我发现下面的编码工作最好(假设轴对齐矩形)。我们用左下角和右上角来定义矩形，例如min={min0，min1}={2,3}/max={max0，max1}={8,4}。我们将此值(通过交错最小/最大值)转换为一个四维点{2,8,3,4}，并将此点存储在索引中。其他方法使用不同的排序(2,3,8,4)或者，而不是两个角，存储中心点和边的长度。

Querying：如果要查找与给定区域重叠/相交的任何矩形(我们称之为窗口查询)，则需要创建一个4维查询框，即由4D min点和4D最大点(抄袭而来)定义的轴对齐框：

min ={ min_0，−∞，−∞，min_1} = {−∞，2，−∞，3}

max = {max_0，+∞，max_1，+∞} = {8，+∞，4，+∞}

我们可以一个一个地处理维度。第一个min/max对是{−∞，8}，它将匹配最小x坐标为8或更低的任何2D矩形。所有坐标：

• d=0: min/max对为{−∞，8}：匹配任何2D min <= 8
• d=1: min/max对为{2，+∞}：匹配任何2D max-x >= 2
• d=2: min/max对为{−∞，4}：匹配任何2D min-y <= 4。
• d=3: min/max对为{3，+∞}：匹配任何2D max-y <= 3

如果所有这些条件都为真，则存储的矩形与查询窗口重叠。

结束语：这听起来很复杂，但可以非常有效地实现(也有助于向量化)。我发现这与其他索引(四叉树，R)不相上下，参见我在这里做的一些基准。具体来说，我发现z顺序索引具有很好的插入/更新/删除时间(我不知道这对您是否重要)，并且对于小的查询结果大小非常好(听起来您通常期望它为零，即没有发现重叠的矩形)。它通常适用于大型数据集(1000 s或数百万个条目)和具有强集群的数据集。对于较小的数据集，如果您期望通常会找到许多结果(当然，您可以在找到第一次匹配后尽早中止查询！)其他索引类型可能更好。

在最后一点上，我发现数据集的特性对哪个索引最有效有相当大的影响。此外，实现似乎至少与底层算法一样重要。特别是对于四叉树，我发现不同实现在性能上存在巨大差异。