我正在寻找一种方法，可以在我正在进行的项目中帮助我。这个想法是，在二维空间中有一些矩形，我想查询一个矩形区域，看看它是否与该区域中的任何矩形重叠。如果是，它就会失败。如果没有，意味着空间是空的，那么它就成功了。
我被链接到z顺序曲线，以帮助将二维坐标转换为一维坐标。当我读到它的时候，我遇到了希尔伯特曲线。我读到希尔伯特曲线比z阶曲线更受欢迎，因为它能更好地保持点的接近度。我还读到希尔伯特曲线用于生成更高效的四叉树和八叉树。
我在读这篇文章https://sigmodrecord.org/publications/sigmodRecord/0103/3.lawder.pdf寻找可能的解决方案，但我不知道这是否适用于我的情况。
我也看到了这个评论https://news.ycombinator.com/item?id=14217760其中提到了非点对象的多个索引条目。
有没有一种优雅的方法可以使用希尔伯特曲线来实现这一点？只需要一个矩形数组就可以了吗？
我非常确信这是可能的，并且可以非常有效。但其中涉及到很多复杂性。
我已经为z阶曲线实现了这一点，并称之为PH树，你可以在Java和C++中找到实现，以及链接中的理论背景。PH树类似于z有序四叉树，但有一些修改，可以充分利用空间填充曲线。
这里有一些东西需要打开包装。
希尔伯特曲线与z阶曲线：是的，希尔伯特曲线的接近度略高于z阶曲线。更好的接近性可以做两件事：1)减少要查看的元素(节点、数据)的数量；2)改进线性访问模式(减少跳跃)。如果空间索引存储在磁盘上，并且I/O成本很高(尤其是旧磁盘驱动器)，则两者都很重要。
如果我没记错的话，希尔伯特曲线和z阶足够相似，总是访问相同数量的数据。希尔伯特曲线唯一擅长的是线性访问。然而，希尔伯特曲线的计算要复杂得多，在我用内存索引进行的测试中(我承认，测试不是很彻底)，我发现z阶曲线的效率要高得多，因为减少的CPU时间超过了访问稍微无序的数据的成本。
空间填充曲线(至少是希尔伯特曲线和z曲线)允许一些巧妙的位级技巧，可以加快索引操作。然而，即使是z排序，我也发现要想正确处理这些问题需要大量思考(我为此写了一整篇论文)。我相信这些操作可以适用于希尔伯特曲线，但我可能需要一些时间，正如我在上面所写的，它可能根本不会提高性能。
在空间曲线索引中存储矩形：对空间曲线中的矩形进行编码有不同的方法。我所知道的所有方法都将矩形编码为多维点。我发现以下编码效果最好(假设轴对齐的矩形)。我们通过左下角的最小值和右上角的最大值来定义矩形，例如min={min0，min1}={2,3}/max={max0，max1}={8,4}。我们将其(通过交错最小/最大值)转换为4维点{2,8,3,4}，并将该点存储在索引中。其他方法使用不同的排序(2，3，8，4)，或者存储中心点和边的长度，而不是两个角。
查询：如果你想找到任何与给定区域重叠/相交的矩形(我们称之为窗口查询)，我们需要创建一个4维查询框，即由4D最小点和4D最大点定义的轴对齐框(从这里复制)：
min=｛-∞，min_0，-∞，min _1｝=｛-1，2，-∞3｝
max={max_0，+∞，max_1，+∞}={8，+∞、4，+∞}
我们可以一个接一个地处理尺寸。第一个最小/最大对是{-∞，8}，它将匹配最小x坐标为8或更低的任何2D矩形。所有坐标：
- d=0:min/max对是｛-∞，8｝：匹配任何2D min-x<=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-Star-Tree)不相上下，请参阅我在这里制作的一些基准测试。具体来说，我发现z顺序索引具有非常好的插入/更新/删除时间(我不知道这对你来说是否重要)，并且非常适合小查询结果大小(听起来你经常期望它为零，即找不到重叠的矩形)。它通常适用于大型数据集(1000或数百万个条目)和具有强大集群的数据集。对于较小的数据集，如果你希望通常能找到很多结果(当然，一旦找到第一个匹配项，你可以提前中止查询！)，其他索引类型可能会更好。
最后一点，我发现数据集的特征对哪个索引效果最好有很大的影响。此外，实现似乎至少与底层算法一样重要。特别是对于四叉树，我发现不同的实现在性能上有很大的差异。