Làm cách nào để tính toán chỉ số tuyến tính của tọa độ 3D và ngược lại?

Question

Nếu tôi có một điểm (x, y z), làm cách nào để tìm chỉ mục tuyến tính, tôi cho điểm đó? Lược đồ đánh số của tôi sẽ là (0,0,0) là 0, (1, 0, 0) là 1,. . ., (0, 1, 0) là kích thước tối đa x, .... Ngoài ra, nếu tôi có tọa độ tuyến tính, i, làm cách nào để tìm (x, y, z)? Tôi dường như không thể tìm thấy điều này trên google, tất cả các kết quả được lấp đầy với những thứ không liên quan khác. Cảm ơn bạn!

Answer 1

Có một số cách để ánh xạ tọa độ 3d thành một số duy nhất. Đây là một cách.

một số hàm f (x, y, z) cho chỉ số tuyến tính của tọa độ (x, y, z). Nó có một số hằng số a, b, c, d mà chúng ta muốn lấy được để chúng ta có thể viết một hàm chuyển đổi hữu ích.

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

Bạn đã xác định rằng (0,0,0) bản đồ đến 0. Vì vậy:

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

Đó là d giải quyết. Bạn đã chỉ định (1.0,0) bản đồ đó cho 1. Vì vậy:

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

Đó là giải pháp. Hãy tự ý quyết định rằng số cao nhất tiếp theo sau (MAX_X, 0, 0) là (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 

Đã giải quyết xong. Hãy tự ý quyết định rằng số cao nhất tiếp theo sau (MAX_X, MAX_Y, 0) là (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) 

bây giờ mà chúng ta biết a, b, c, d, chúng ta có thể viết hàm của bạn như sau:

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 
} 

Bạn có thể nhận được phối hợp từ các chỉ số tuyến tính bằng logic tương tự. Tôi có một cuộc biểu tình thực sự tuyệt vời về điều này, trang này quá nhỏ để chứa. Vì vậy, tôi sẽ bỏ qua bài giảng toán học và chỉ cung cấp cho bạn phương pháp cuối cùng.

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

Nếu bạn không có giới hạn trên tọa độ, bạn có thể đánh số chúng từ màu da và ra ngoài. Tầng tầng lớp lớp.

(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 

Nghịch đảo khó hơn, vì bạn sẽ phải giải quyết đa thức bậc 3.

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

nơi

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) thể hoặc được tính từ large analytic solution, hoặc tìm kiếm với some numeric method.

---

Đây là nỗ lực của tôi tại giải pháp đại số (javascript). Tôi đang sử dụng các thay thế p = a+b+c, q = a+b, r = a để đơn giản hóa các phương trình.

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