如何在 Hilbert Curve QuadTree 和 S2 Geometry CellId 之间转换
How to convert between Hilbert Curve QuadTree and S2 Geometry CellId
问题
假设我知道希尔伯特曲线面和四叉树，例如4/032212303102122（面4，级别15）。
或者我知道S2 Geometry CellId，比如9749618424903892992。
如何从一种转换为另一种？
申请
（这是你需要为 Pokemon GO 和 Ingress 地图做的事情）
探索
我正在尝试在 JavaScript 中执行此操作，并且存在用于处理 64 位整数 (long.js) 以及 S2CellIds (s2-geometry.js) 的库。
此外，我对通过简单地加上或减去四个基数来走希尔伯特曲线感觉很好（交叉面时除外，但这种情况很少发生，所以我会没事的......一段时间...)，只是不确定如何使用 64 位 ID 来回切换。
事实证明，使用字符串比使用二进制要容易得多 - 而且由于这是 JavaScript，其中使用 long.js 进行位移将花费更多时间，因此实际上更快！
代码示例：
'use strict';
var Long = require('long');
var S2 = {};
S2.FACE_BITS = 3;
S2.MAX_LEVEL = 30;
S2.POS_BITS = (2 * S2.MAX_LEVEL) + 1;
S2.fromFacePosLevel = function (faceN, posS, levelN) {
var Long = exports.dcodeIO && exports.dcodeIO.Long || require('long');
if (!levelN) {
levelN = posS.length;
}
if (posS.length > levelN) {
posS = posS.substr(0, levelN);
}
var posB = Long.fromString(posS, true, 4).toString(2);
while (posB.length < (2 * levelN)) {
posB = '0' + posB;
}
var bin = Long.fromString(faceN.toString(10), true, 10).toString(2);
while (bin.length < S2.FACE_BITS) {
bin = '0' + bin;
}
bin += posB;
bin += '1';
while (bin.length < (S2.FACE_BITS + S2.POS_BITS)) {
bin += '0';
}
return Long.fromString(bin, true, 2).toString(10);
};
解释：
这里有一个快速的'n'位的肮脏分解
id编码
请注意 + 表示连接而不是添加
(padding + face bits) + (padding + position bits) + (lsb marker + padding)
// quadkey 4/032212303102210
// id (base 10) 9749618446378729472
// base 4 10 032212303102210 1000000000000000
// base 2 100 001110100110110011010010100100 1000000000000000000000000000000
面部编码
- "human readable" 形式是以 10 为底
- 3 位 - 即展开的 6 面立方体，其基数为 10 的面表示为 0,1,2,3,4,5
- 6 和 7 未使用且无效
- 3 个二进制字符 - 即 000、001、010、011、100、101
- 110 和 111 未使用且无效
- 用“0”向左填充到 3 位（即 001）
位置编码
- "human readable" 形式是 base 4 (quadkey)
- 61 位
- 60 个数据位，1 位用于 lsb 标记
- 用“0”向左填充到 LEVEL（即 00322130 表示第 8 级）
级别编码
- "human readable" 形式是以 10 为底
- hilbert curve quadkey / quadtree string 的长度为级别
- 从二进制形式的最低有效位开始计算
- lsb（最低有效位）标记为“1”，就在位置右侧
- 右填充到 MAX_LEVEL*2（在 lsb 标记之后），前导为“0”
- （即“1”表示 30 级，“1000”表示 27 级）
问题
假设我知道希尔伯特曲线面和四叉树，例如4/032212303102122（面4，级别15）。
或者我知道S2 Geometry CellId，比如9749618424903892992。
如何从一种转换为另一种？
申请
（这是你需要为 Pokemon GO 和 Ingress 地图做的事情）
探索
我正在尝试在 JavaScript 中执行此操作，并且存在用于处理 64 位整数 (long.js) 以及 S2CellIds (s2-geometry.js) 的库。
此外，我对通过简单地加上或减去四个基数来走希尔伯特曲线感觉很好（交叉面时除外，但这种情况很少发生，所以我会没事的......一段时间...)，只是不确定如何使用 64 位 ID 来回切换。
事实证明，使用字符串比使用二进制要容易得多 - 而且由于这是 JavaScript，其中使用 long.js 进行位移将花费更多时间，因此实际上更快！
代码示例：
'use strict';
var Long = require('long');
var S2 = {};
S2.FACE_BITS = 3;
S2.MAX_LEVEL = 30;
S2.POS_BITS = (2 * S2.MAX_LEVEL) + 1;
S2.fromFacePosLevel = function (faceN, posS, levelN) {
var Long = exports.dcodeIO && exports.dcodeIO.Long || require('long');
if (!levelN) {
levelN = posS.length;
}
if (posS.length > levelN) {
posS = posS.substr(0, levelN);
}
var posB = Long.fromString(posS, true, 4).toString(2);
while (posB.length < (2 * levelN)) {
posB = '0' + posB;
}
var bin = Long.fromString(faceN.toString(10), true, 10).toString(2);
while (bin.length < S2.FACE_BITS) {
bin = '0' + bin;
}
bin += posB;
bin += '1';
while (bin.length < (S2.FACE_BITS + S2.POS_BITS)) {
bin += '0';
}
return Long.fromString(bin, true, 2).toString(10);
};
解释：
这里有一个快速的'n'位的肮脏分解
id编码
请注意 + 表示连接而不是添加
(padding + face bits) + (padding + position bits) + (lsb marker + padding)
// quadkey 4/032212303102210
// id (base 10) 9749618446378729472
// base 4 10 032212303102210 1000000000000000
// base 2 100 001110100110110011010010100100 1000000000000000000000000000000
面部编码
- "human readable" 形式是以 10 为底
- 3 位 - 即展开的 6 面立方体，其基数为 10 的面表示为 0,1,2,3,4,5
- 6 和 7 未使用且无效
- 3 个二进制字符 - 即 000、001、010、011、100、101
- 110 和 111 未使用且无效
- 用“0”向左填充到 3 位（即 001）
位置编码
- "human readable" 形式是 base 4 (quadkey)
- 61 位
- 60 个数据位，1 位用于 lsb 标记
- 用“0”向左填充到 LEVEL（即 00322130 表示第 8 级）
级别编码
- "human readable" 形式是以 10 为底
- hilbert curve quadkey / quadtree string 的长度为级别
- 从二进制形式的最低有效位开始计算
- lsb（最低有效位）标记为“1”，就在位置右侧
- 右填充到 MAX_LEVEL*2（在 lsb 标记之后），前导为“0”
- （即“1”表示 30 级，“1000”表示 27 级）