如何计算3D坐标的线性索引，反之亦然？

Question

如果我有一个点（x，y z），那么我该如何找到线性指数？我的编号方案是（0,0,0）是0，（1,0,0）是1。 。如果我有一个线性坐标，我，我怎么找到（x，y，z）？，（0，1，0）是最大的x维度，.... 我似乎无法在谷歌上找到这一点，所有的结果都充满了其他不相干的东西。谢谢！

Answer 1

有几种方法可以将3d坐标映射到单个数字。这是一种方法。一些函数f（x，y，z）给出坐标（x，y，z）的线性索引。它有一些我们想要派生的常量a，b，c，d，所以我们可以写一个有用的转换函数。

f(x,y,z) = a*x + b*y + c*z + d 

您已经指定了（0,0,0）映射到0.所以：

f(0,0,0) = a*0 + b*0 + c*0 + d = 0 
d = 0 
f(x,y,z) = a*x + b*y + c*z 

那公司的D解决。 您已经指定了（1,0,0）映射到1，所以：

f(1,0,0) = a*1 + b*0 + c*0 = 1 
a = 1 
f(x,y,z) = x + b*y + c*z 

，这是一个解决。 让我们任意决定（MAX_X，0,0）之后的下一个最高数字是（0,1,0）。

f(MAX_X, 0, 0) = MAX_X 
f(0, 1, 0) = 0 + b*1 + c*0 = MAX_X + 1 
b = MAX_X + 1 
f(x,y,z) = x + (MAX_X + 1)*y + c*z 

这就解决了。 让我们任意决定（MAX_X，MAX_Y，0）之后的下一个最高数字是（0,0,1）。

f(MAX_X, MAX_Y, 0) = MAX_X + MAX_Y * (MAX_X + 1) 
f(0,0,1) = 0 + (MAX_X + 1) * 0 + c*1 = MAX_X + MAX_Y * (MAX_X + 1) + 1 
c = MAX_X + MAX_Y * (MAX_X + 1) + 1 
c = (MAX_X + 1) + MAX_Y * (MAX_X + 1) 
c = (MAX_X + 1) * (MAX_Y + 1) 

现在我们知道A，B，c和d，我们可以写出如下的功能：

function linearIndexFromCoordinate(x,y,z, max_x, max_y){ 
    a = 1 
    b = max_x + 1 
    c = (max_x + 1) * (max_y + 1) 
    d = 0 
    return a*x + b*y + c*z + d 
} 

你可以通过类似的逻辑，线性指标的坐标。我有一个真正奇妙的演示，这个页面太小，不能容纳。所以我会跳过数学讲座，给你最后的方法。

function coordinateFromLinearIndex(idx, max_x, max_y){ 
    x = idx % (max_x+1) 
    idx /= (max_x+1) 
    y = idx % (max_y+1) 
    idx /= (max_y+1) 
    z = idx 
    return (x,y,z) 
} 

Answer 2

如果坐标没有上限，可以从原点和外侧对它们进行编号。逐层。

(0,0,0) -> 0 
(0,0,1) -> 1 
(0,1,0) -> 2 
(1,0,0) -> 3 
(0,0,2) -> 4 
    :  : 
(a,b,c) -> (a+b+c)·(a+b+c+1)·(a+b+c+2)/6 + (a+b)·(a+b+1)/2 + a 

由于需要求解3次多项式，所以反比较难。

m1 = InverseTetrahedralNumber(n) 
m2 = InverseTriangularNumber(n - Tetra(m1)) 
a = n - Tetra(m1) - Tri(m2) 
b = m2 - a 
c = m1 - m2 

其中

InverseTetrahedralNumber(n) = { x ∈ ℕ | Tetra(n) ≤ x < Tetra(n+1) } 
Tetra(n) = n·(n+1)·(n+2)/6 
InverseTriangularNumber(n) = { x ∈ ℕ | Tri(n) ≤ x < Tri(n+1) } 
Tri(n) = n·(n+1)/2 

InverseTetrahedralNumber(n)既可以从large analytic solution来计算，或搜索与some numeric method。

---

这是我在一个代数解决方案（javascript）的尝试。我正在使用替代p = a+b+c,q = a+b,r = a来简化公式。

function index(a,b,c) { 
    var r = a; 
    var q = r + b; 
    var p = q + c; 
    return (p*(p+1)*(p+2) + 3*q*(q+1) + 6*r)/6; 
} 

function solve(n) { 
    if (n <= 0) { 
     return [0,0,0]; 
    } 

    var sqrt = Math.sqrt; 
    var cbrt = function (x) { return Math.pow(x,1.0/3); }; 

    var X = sqrt(729*n*n - 3); 
    var Y = cbrt(81*n + 3*X); 
    var p = Math.floor((Y*(Y-3)+3)/(Y*3)); 
    if ((p+1)*(p+2)*(p+3) <= n*6) p++; 
    var pp = p*(p+1)*(p+2); 

    var Z = sqrt(72*n+9-12*pp); 
    var q = Math.floor((Z-3)/6); 
    if (pp + (q+1)*(q+2)*3 <= n*6) q++; 
    var qq = q*(q+1); 

    var r = Math.floor((6*n-pp-3*qq)/6); 
    if (pp + qq*3 + r*6 < n*6) r++; 

    return [r, q - r, p - q]; 
}