计算用于希尔伯特R树的点的希尔伯特值？
https://stackoverflow.com/questions/106237
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我有一个应用程序，其中Hilbert R-tree （维基百科） （citeseer）似乎是一个合适的数据结构。具体而言，它需要对将经历大量更新的数据集进行合理快速的空间查询。
但是，据我所知，这个数据结构的算法描述都没有提及如何实际计算必要的 Hilbert值;这是希尔伯特曲线的距离。
那么有关如何计算这个的任何建议？
解决方案
有趣的问题！
我做了一些谷歌搜索，好消息是，我找到了希尔伯特价值的实现。
潜在的坏消息是，它出现在Haskell ......
它还提出了一个您可以更容易计算的Lebesgue距离指标。
其他提示
下面是我的Java代码改编自论文“编码和解码希尔伯特顺序”中的C代码。作者：Xian Lu和Gunther Schrack，发表在Software：Practice and Experience Vol。 26 pp 1335-46（1996）。
希望这会有所帮助。欢迎改进！
迈克尔
/**
* Find the Hilbert order (=vertex index) for the given grid cell
* coordinates.
* @param x cell column (from 0)
* @param y cell row (from 0)
* @param r resolution of Hilbert curve (grid will have Math.pow(2,r)
* rows and cols)
* @return Hilbert order
*/
public static int encode(int x, int y, int r) {
int mask = (1 << r) - 1;
int hodd = 0;
int heven = x ^ y;
int notx = ~x & mask;
int noty = ~y & mask;
int temp = notx ^ y;
int v0 = 0, v1 = 0;
for (int k = 1; k < r; k++) {
v1 = ((v1 & heven) | ((v0 ^ noty) & temp)) >> 1;
v0 = ((v0 & (v1 ^ notx)) | (~v0 & (v1 ^ noty))) >> 1;
}
hodd = (~v0 & (v1 ^ x)) | (v0 & (v1 ^ noty));
return interleaveBits(hodd, heven);
}
/**
* Interleave the bits from two input integer values
* @param odd integer holding bit values for odd bit positions
* @param even integer holding bit values for even bit positions
* @return the integer that results from interleaving the input bits
*
* @todo: I'm sure there's a more elegant way of doing this !
*/
private static int interleaveBits(int odd, int even) {
int val = 0;
// Replaced this line with the improved code provided by Tuska
// int n = Math.max(Integer.highestOneBit(odd), Integer.highestOneBit(even));
int max = Math.max(odd, even);
int n = 0;
while (max > 0) {
n++;
max >>= 1;
}
for (int i = 0; i < n; i++) {
int bitMask = 1 << i;
int a = (even & bitMask) > 0 ? (1 << (2*i)) : 0;
int b = (odd & bitMask) > 0 ? (1 << (2*i+1)) : 0;
val += a + b;
}
return val;
}
请参阅 uzaygezen 。
上面的代码和java代码适用于2D数据点。但是对于更高的维度，您可能需要查看Jonathan Lawder的论文： JKLawder 。使用希尔伯特空间填充曲线计算一维和一维值之间的映射。
我想出了一种更有效的交错比特方式。它可以在斯坦福图形网站。我包含了一个我创建的版本，它可以将两个32位整数交织成一个64位长。
public static long spreadBits32(int y) {
long[] B = new long[] {
0x5555555555555555L,
0x3333333333333333L,
0x0f0f0f0f0f0f0f0fL,
0x00ff00ff00ff00ffL,
0x0000ffff0000ffffL,
0x00000000ffffffffL
};
int[] S = new int[] { 1, 2, 4, 8, 16, 32 };
long x = y;
x = (x | (x << S[5])) & B[5];
x = (x | (x << S[4])) & B[4];
x = (x | (x << S[3])) & B[3];
x = (x | (x << S[2])) & B[2];
x = (x | (x << S[1])) & B[1];
x = (x | (x << S[0])) & B[0];
return x;
}
public static long interleave64(int x, int y) {
return spreadBits32(x) | (spreadBits32(y) << 1);
}
显然， B 和 S 局部变量应该是类常量，但为了简单起见，它就是这样。
迈克尔，
感谢您的Java代码！我测试它似乎工作正常，但我注意到位交错函数溢出在递归级别7（至少在我的测试中，但我使用长值），因为“n”值使用highestOneBit计算（）-function，返回值而不是最高位的位置;所以循环不必要地进行很多交错。
我刚刚将其更改为以下代码段，之后它运行正常。
int max = Math.max(odd, even);
int n = 0;
while (max > 0) {
n++;
max >>= 1;
}
如果您需要具有快速删除/插入功能的空间索引，请查看PH树。它部分基于四叉树，但更快，更节省空间。在内部，它使用Z曲线，其空间属性略差于H曲线，但 更容易计算。
论文： http://www.globis.ethz.ch/脚本/出版物/下载？文档ID = 699
Java实施： http：// globis .ethz.ch /文件/ 2014/11 / ph-tree-2014-11-10.zip
另一个选项是X-tree，也可以在这里找到： https://code.google.com/p/xxl/
建议：空间查询的一个简单有效的简单数据结构是多维二叉树。
在传统的二叉树中，存在一个“判别式”;用于确定是采用左分支还是右分支的值。这可以被认为是一维的情况。
在多维二叉树中，您有多个判别式;连续级别使用不同的判别式。例如，对于二维空间数据，您可以使用X和Y坐标作为判别式。连续的级别将使用X，Y，X，Y ......
对于空间查询（例如，查找矩形内的所有节点），您可以从根开始对树进行深度优先搜索，并在每个级别使用判别式来避免搜索不包含节点的分支。给定矩形。
这使您可以在每个级别将搜索空间减半，从而非常有效地在海量数据集中查找小区域。 （顺便说一句，这个数据结构对于部分匹配查询也很有用，即省略一个或多个判别式的查询。你只需用省略的判别式搜索两个分支。）
关于此数据结构的一篇好文章： http://portal.acm.org /citation.cfm?id=361007 本文有很好的图表和算法描述： http://en.wikipedia.org/wiki/Kd -tree
