3

问题

假设我知道 Hilbert Curve Face 和 Quadtree，例如4/032212303102122(face 4, level 15)。

或者我知道 S2 Geometry CellId，例如9749618424903892992.

如何从一种转换为另一种？

应用

（这是你需要为Pokemon GO和Ingress地图做的事情）

勘探

我正在尝试在 JavaScript 中执行此操作，并且存在一个用于操作 64 位整数 ( long.js) 以及 S2CellIds ( s2-geometry.js) 的库。

另外，我对通过简单地通过添加或减去基数四数来行走希尔伯特曲线感觉非常好（除了交叉脸时，但这种情况很少发生，我会没事的......一段时间......），只是不确定如何使用 64 位 id 来回切换。

4

1 回答 1

2

事实证明，使用字符串比使用二进制要容易得多，而且由于这是 JavaScript，使用 位移位long.js将花费更多时间，它实际上更快！

代码示例：

来自s2-geometry-javascript：

'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 编码

请注意，+ 表示 concat 而不是添加

(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

人脸编码

  • “人类可读”形式以 10 为基数
  • 3 位 - 即一个展开的 6 面立方体，具有 0、1、2、3、4、5 的基数 10 面表示
  • 6 和 7 未使用且无效
  • 3 个二进制字符 - 即 000、001、010、011、100、101
  • 110 和 111 未使用且无效
  • 用 '0' 左填充到 3 位（即 001）

位置编码

  • “人类可读”形式是基数 4（四键）
  • 61 位
  • 60 个数据位，1 位用于 lsb 标记
  • 用 0 向左填充到 LEVEL（即 00322130 表示第 8 级）

级别编码

  • “人类可读”形式以 10 为基数
  • 希尔伯特曲线四键/四叉树字符串的长度是级别
  • 从二进制形式的最低有效位计算
  • lsb（最低有效位）标记为 '1'，就在位置的右侧
  • 右填充到 MAX_LEVEL*2（在 lsb 标记之后），前导 '0'
    • （即 30 级为“1”，27 级为“1000”）
于 2016-07-28T00:05:27.787 回答