如何计算三维坐标的线性索引以及反过来呢？

Question

如果有一个点(x, y, z)，我该如何找到这个点的线性索引i呢？我的编号方案是(0, 0, 0)为0，(1, 0, 0)为1，……，(0, 1, 0)为最大x维度，等等。另外，如果我有一个线性坐标i，我该如何找到(x, y, z)呢？ 我在谷歌上找不到这个问题的答案，所有的结果都是其他无关的内容。谢谢！

- user1438116

---

坐标是否总是由整数组成？您可以有负坐标吗？除了x轴之外，您是否有任何轴的最大值？ - Kevin

每个坐标都有相同的划分数，还是不同的？最后一个点表示为(N,N,N)还是(N1,N2,N3)？ - John Alexiou

Answer 1

有几种将三维坐标映射到单个数字的方法。下面是其中一种方式。

某些函数 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

问题已经解决。 你已经指定了(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)
}

- Kevin

---

太棒了！我想我会再花375年来琢磨你的神奇证明（但现在它有意义了）。非常感谢。 - user1438116

在答案被接受后，您不应该在编辑中更改代码 - 应该在评论中完成。 - John Nicholas

@MarkAnderson，如果我没记错的话，在我编写coordinateFromLinearIndex函数时，数学讲座只存在于我的脑海中。我可以编辑答案以展示我是如何推导出最终的代码块的，但首先我需要回忆起我是如何做到的 :-) - Kevin

收藏了！算法背后的数学解释很棒。 - IAbstract

@Kevin，有没有通用算法可以将高维数组进行转换？比如说4维和5维的数组？ - zwlayer

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

相反的情况更难，因为您必须解决一个三次方程。

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) 可以通过 大型解析方法 计算，也可以通过 一些数值方法 进行搜索。

---

这是我尝试用代数方法解决问题的代码（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];
}

- Markus Jarderot