Come si calcola l'indice lineare di una coordinata 3D e viceversa?

Question

Se ho un punto (x, y z), come trovo l'indice lineare, i per quel punto? Il mio schema di numerazione sarebbe (0,0,0) è 0, (1, 0, 0) è 1,. . ., (0, 1, 0) è la dimensione massima x, .... Inoltre, se ho una coordinata lineare, come trovo (x, y, z)? Non riesco a trovare questo su google, tutti i risultati sono pieni di altre cose irrilevanti. Grazie!

Answer 1

Esistono alcuni modi per associare una coordinata 3D a un singolo numero. Ecco un modo.

una certa funzione f (x, y, z) fornisce l'indice lineare delle coordinate (x, y, z). Ha alcune costanti a, b, c, d che vogliamo derivare in modo da poter scrivere un'utile funzione di conversione.

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

Hai specificato che (0,0,0) mappe per 0. Quindi:

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

che è d risolto. Hai specificato che (1,0,0) mappe a 1. Quindi:

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

che è un risolto. Decidiamo arbitrariamente che il successivo numero più alto dopo (MAX_X, 0, 0) sia (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 

Questo è risolto. Decidiamo arbitrariamente che il successivo numero più alto dopo (MAX_X, MAX_Y, 0) sia (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) 

ora che sappiamo a, b, c, d, possiamo scrivere la funzione come segue:

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 
} 

È possibile ottenere la coordinata dall'indice lineare logica simile. Ho una dimostrazione davvero meravigliosa di questo, che questa pagina è troppo piccola per contenere. Quindi salterò la lezione di matematica e ti darò il metodo finale.

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

Se non si dispone di un limite superiore sulle coordinate, è possibile numerarle da origo e verso l'esterno. Strato per strato.

(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 

L'inverso è più difficile, poiché si dovrebbe risolvere un polinomio di terzo grado.

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

dove

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) potrebbe essere sia calcolato dal large analytic solution, o ha cercato con some numeric method.

---

Ecco il mio tentativo di una soluzione algebrica (javascript). Sto usando le sostituzioni p = a+b+c, q = a+b, r = a per semplificare le equazioni.

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