如何在范围搜索中使用Morton Order

如果我有一个数据集，其中键是3D中的点，由3个有符号的64位整数表示。我想使用(排序的)键值存储来存储它们，其中键只是字节数组(但我可以指定一个比较器)。我想我可以通过使用比特交织将所有这些点变成一个字节数组，就像在如何计算3D Morton数中使用Z/Morton顺序所做的那样

除了获取单个点(这可以在没有Morton排序的情况下更简单地完成)之外，我还想进行范围搜索，在与轴对齐的框中进行搜索。我将把A和B分别定义为所有坐标最低的方框角和所有坐标最高的相对角。

现在我的问题是：

概括一下，使用Morton数只是解决实际问题的一种可能方案：当3D点必须映射到一维值时，如何在3D整数空间中有效地进行范围搜索？我想通过在DB中执行单个范围选择，使用最小键和最大键，获得A和B之间的所有点，理想情况下，获得尽可能少的框外点。

4)是的，符号会导致问题，但解决起来很简单。

在创建Morton数之前，只需将x、y和z的符号位与1异或即可

为什么这样做(使用一维签名字节)：

-二进制中的1是11111111

二进制中的0是00000000

二进制中的1是0000000 1

您想要的顺序是-1，0，1，但当前的二进制顺序是0，1和-1。

-1 XOR 10000000=01111111

0 XOR 10000000=10000000

1 XOR 10000000=10000001

现在你的二进制顺序是正确的

似乎我必须自己回答我的问题。答案将与z阶曲线有关，这就是我实际要求的。据我所知：

是的。它总是这样处理z阶曲线
无关紧要，因为1)是真的
这取决于区域的大小和位置，但最坏的情况是，当你真正包括空间的中心时，而不是当你远离它时。对于任何维度，如果你在每个维度中使用深度为N位的索引，那么在特殊情况下，z阶曲线会给你一个精确的匹配，而你只会在搜索框中得到点。当满足以下条件时，会发生这种情况：
搜索区域在所有维度上都是相同的大小，并且是2的幂2^M，其中0<=M<=N
搜索区域是一个与所有轴对齐的超立方体
搜索区域超立方体角的所有坐标都是2^M的倍数。当满足所有这些条件时，搜索区域与子树节点完全对应，因此完全匹配。然而，在一般情况下，你能做的最好的事情就是找到一个能容纳所有所需点的最小节点，并将其递归地细分为提供部分匹配的较小节点，达到某个最大所需深度，以获得更好的匹配，而代价是使用多个查询。找到包含该区域所有角落的最小树节点相当于为所有角落找到Morton代码的公共前缀。当使用单个查询时，返回的区域外的点数是查询节点的体积减去搜索区域的体积
我很确定这是个问题，但我还没有找到这方面的信息

我想说的似乎不清楚，所以我会做一点ASCII ART…

2D中的基本Z阶(Morton阶)曲线如下(路径为A、B、C、D)：

x  0   1
0  A → B
↙
1  C → D

因此，A=(0,0)B=(0,1)C=(1,0)D=(1,1)

现在，2D中的一条基本希尔伯特曲线是这样的(路径是a、B、C、D)：

x  0   1
0  A   D
↓   ↑
1  B → C

因此，A=(0,0)B=(1,0)C=(1,1)D=(0,1)

对于Z阶(Morton阶)，曲线将从最低点a(0,0)开始，并以最高点D(1,1)结束，同时覆盖其间的所有点。这使得范围搜索变得容易，而且它也可以在3D中工作。三维长方体(0,0,0)到(1,1,1)中的所有点都在Morton顺序代码(0,00,0)和(1,11,1)之间。

对于希尔伯特曲线，从(0,0)开始，到(0,1)结束(在三维中可能类似)。因此，执行从(0,0)到(1,1)的希尔伯特码的范围查询不会找到所有点。

因此，如果我要使用希尔伯特曲线来执行3D框(0,0,0)到(1,1,1)的范围查询(作为单个DB查询)，我需要一个函数，该函数告诉我应该使用哪个点作为第一个点，以及应该使用什么点作为最后一个点，因为(,0,0)和(1,10,1)将不起作用。

那么，有没有这样一个函数，你可以给出你的8(对于3D)框坐标，它会返回你的范围查询中使用的第一个和最后一个点？如果没有这些，我就无法使用希尔伯特曲线来解决我的问题。

或者，在伪SQL中：

Morton查询：

SELECT key,data FROM table WHERE (key >= Morton(lowest(box))) AND (key <= Morton(highest(box)))

Hilbert查询：

SELECT key,data FROM table WHERE (key >= Hilbert(XXX(box))) AND (key <= Hilbert(YYY(box)))

所以我需要XXX()和YYY()。

[编辑]这个答案的一部分是针对其他告诉我使用希尔伯特曲线的答案，但后来删除了他们的答案。

通常情况下，尝试将三维减少到一维并没有什么期望。不过，你可以尝试的是：找到主轴(即通过点进行直线拟合)，然后将点投影到线上。这将为每个点提供所需的一维值。当您将方框的角投影到直线上并取这些值的封闭间隔时，您就得到了搜索范围。

相关内容