¿Cómo calculo el índice lineal de una coordenada 3D y viceversa?

Question

Si tengo un punto (x, yz), ¿cómo puedo encontrar el índice lineal, i para ese punto? Mi esquema de numeración sería (0,0,0) es 0, (1, 0, 0) es 1,. . ., (0, 1, 0) es la dimensión max-x, .... Además, si tengo una coordenada lineal, i, ¿cómo encuentro (x, y, z)? Parece que no puedo encontrar esto en Google, todos los resultados están llenos de otras cosas irrelevantes. ¡Gracias!

Answer 1

Hay algunas formas de asignar una coordenada 3d a un solo número. Aquí hay una manera.

alguna función f (x, y, z) da el índice lineal de coordenadas (x, y, z). Tiene algunas constantes a, b, c, d que queremos derivar para que podamos escribir una función de conversión útil.

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

Usted ha especificado que (0,0,0) los mapas a 0. Por lo tanto:

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

Eso es d resuelto. Usted ha especificado que (1,0,0) los mapas a 1. Así:

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

eso es un resueltos. Decidamos arbitrariamente que el siguiente número más alto después de (MAX_X, 0, 0) es (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 

Eso se solucionó. Decidamos arbitrariamente que el siguiente número más alto después de (MAX_X, MAX_Y, 0) es (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) 

ahora que sabemos que a, b, c, yd, podemos escribir la función de la siguiente manera:

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 
} 

Usted puede obtener la coordenada del índice lineal mediante una lógica similar. Tengo una demostración realmente maravillosa de esto, que esta página es demasiado pequeña para contener. Así que me saltearé la conferencia de matemáticas y solo te daré el método final.

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

Si no tiene un límite superior en las coordenadas, puede numerarlas desde origo y hacia afuera. Capa por capa.

(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 

Lo inverso es más difícil, ya que tendría que resolver un polinomio de 3er grado.

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

donde

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), o bien podría calcularse a partir de la large analytic solution, o buscado con some numeric method.

---

Aquí está mi intento de una solución algebraica (javascript). Estoy usando las sustituciones p = a+b+c, q = a+b, r = a para simplificar las ecuaciones.

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]; 
}