0

我有一个基于这个算法的希尔伯特曲线指数。我取两到四个值（纬度、经度、unix 格式的时间和一个 id 代码）并创建一维希尔伯特曲线。

我正在寻找一种使用此数据创建边界框查询的方法（即“查找此矩形内的所有 ID）。

我正在寻找一种无需将一维希尔伯特码解码回其组成部分的方法。使用 Morton/Z 阶曲线似乎更容易做到这一点，但我想知道局部性保留。

我的问题是：如果我创建了一个 2d 希尔伯特曲线范围（即我将框的范围转换为希尔伯特曲线，因此 x1y1-> hilbert value1 和 x2y2-> hilbertvalue2）是否会相应的 2d hilbert 值的所有值都落在它们的范围内？

例如，如果我将 (1,2) 和 (20,30) 转换为 Hilbert 值，然后搜索 hilbertvalue1 和 hilbertvalue2 之间的所有值，我得到的所有值是否都在 (1,2) 和 (20, 30) 之内，还是我必须执行额外的转换？

当您有超过 2 个维度时，另一个问题是制作一个范围。我有能力进出希尔伯特曲线，但我怎样才能确保即使是 4d 值的纬度和经度也在同一个矩形/边界框中？

谢谢。

4

2 回答 2

2

我的问题是：如果我创建了一个 2d 希尔伯特曲线范围（即我将框的范围转换为希尔伯特曲线，因此 x1y1-> hilbert value1 和 x2y2-> hilbertvalue2）是否会相应的 2d hilbert 值的所有值都落在它们的范围内？

答案是不。这是使用希尔伯特指数所面临的挑战的一部分。下面是一个示例曲线。您会注意到曲线上可能有一个点，其索引高于包含该点的框的顶点。浅蓝色框是一个示例，其中顶点的索引为 117、122、133、138，但内部（尽管在边界上）的值为 143。

一种简单的方法是蛮力访问搜索区域中的每个单元格并计算这些单元格中的索引。然后编译将在查询中使用的索引范围列表。您可能会加入一些范围并稍后过滤作为基于基准的性能优化（许多小范围查询可能比查询较少的较大范围后跟一个过滤器需要更长的时间）。我想看到比这更优雅的东西，但还没有看到。

更新：我已经找到了比蛮力技术更优雅的方法，详细信息（和 java 库）位于https://github.com/davidmoten/hilbert-curve。简而言之，恰好覆盖搜索框的范围的端点都将位于该区域的周边。如果您对区域周边的所有希尔伯特曲线值进行排序并从最小值开始，您可以通过测试曲线上的下一个点是保持在周边上、离开盒子还是在里面来配对所有范围盒子。

当您有超过 2 个维度时，另一个问题是制作一个范围。我有能力进出希尔伯特曲线，但我怎样才能确保即使是 4d 值的纬度和经度也在同一个矩形/边界框中？

上述周边技术适用于任意数量的维度（但当然会变得更加昂贵！）。

于 2019-04-03T06:23:03.493 回答
0

对于 2 维，您可以将曲线视为以 4 为底的数字（四键）并从左到右搜索。

于 2019-04-09T12:12:18.253 回答