Если у меня есть точка (x, y z), как мне найти линейный индекс i для этой точки? Моя схема нумерации будет (0,0,0) равно 0, (1, 0, 0) равно 1, . . ., (0, 1, 0) - это максимальное x-размерность, .... Кроме того, если у меня есть линейная координата i, как мне найти (x, y, z)? Я не могу найти это в Google, все результаты заполнены другими не относящимися к делу вещами. Благодарю вас!
Как вычислить линейный индекс трехмерной координаты и наоборот?
Ответы (2)
Есть несколько способов сопоставить трехмерную координату с одним числом. Вот один из способов.
некоторая функция 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)
}
coordinateFromLinearIndex
. Я мог бы отредактировать ответ, чтобы показать, как я получил окончательный блок кода, но сначала мне нужно вспомнить, как я это сделал :-)
- person Kevin; 09.05.2014
divmod()
? Я уверен, что coordinateFromLinearIndex()
мог бы извлечь выгоду из своих уникальных свойств.
- person Martijn Pieters; 26.01.2015
Если у вас нет верхнего предела координат, вы можете пронумеровать их от начала и дальше. Слой за слоем.
(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
Обратное сложнее, так как вам придется решать многочлен 3-й степени.
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];
}
(N,N,N)
или(N1,N2,N3)
? - person John Alexiou   schedule 05.06.2012