Wie berechne ich den linearen Index einer 3D-Koordinate und umgekehrt?

Question

Wenn ich einen Punkt (x, y z) habe, wie finde ich den linearen Index, ich für diesen Punkt? Mein Nummerierungsschema wäre (0,0,0) ist 0, (1, 0, 0) ist 1,. . ., (0, 1, 0) ist die Max-X-Dimension, .... Auch, wenn ich eine lineare Koordinate habe, wie finde ich (x, y, z)? Ich kann nicht scheinen, das auf Google zu finden, alle Ergebnisse sind mit anderen irrelevanten Sachen gefüllt. Vielen Dank!

Answer 1

Es gibt mehrere Möglichkeiten, eine 3d-Koordinate einer einzelnen Zahl zuzuordnen. Hier ist ein Weg.

einige Funktion f (x, y, z) gibt den linearen Index der Koordinate (x, y, z). Es hat einige Konstanten a, b, c, d, die wir ableiten wollen, damit wir eine nützliche Konvertierungsfunktion schreiben können.

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

Sie haben festgelegt, dass (0,0,0) Karten auf 0 Also:

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

, das gelöst Ds. Sie haben festgelegt, dass (1,0,0) abbildet 1. So:

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

Das ist ein gelöst wird. Lassen Sie uns willkürlich entscheiden, dass die nächsthöhere Zahl nach (MAX_X, 0, 0) (0,1,0) ist.

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 

Das ist b gelöst. Lassen Sie uns willkürlich entscheiden, dass die nächsthöhere Zahl nach (MAX_X, MAX_Y, 0) (0,0,1) ist.

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) 

jetzt, wo wir wissen, a, b, c und d, können wir Ihre Funktion wie folgt schreiben:

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 
} 

Sie können die von der linearen Index durch eine ähnliche Logik Koordinate erhalten. Ich habe eine wirklich wunderbare Demonstration davon, für die diese Seite zu klein ist. Also überspringe ich die Mathematikvorlesung und gebe Ihnen nur die letzte Methode.

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

Wenn Sie keine obere Grenze für die Koordinaten haben, können Sie sie von origo und outsource nummerieren. Schicht nach Schicht.

(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 

Die Umkehrung ist schwieriger, da Sie ein Polynom dritten Grades lösen müssten.

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

wo

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) entweder aus den large analytic solution berechnet werden kann, oder mit some numeric method gesucht.

---

Hier ist mein Versuch einer algebraischen Lösung (Javascript). Ich benutze die Substitutionen p = a+b+c, q = a+b, r = a, um die Gleichungen zu vereinfachen.

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