Прохождение 3D-массива из центра
Я пытаюсь найти порядок обхода для трехмерного массива с равномерным размером n. Порядок обхода должен сортироваться по возрастанию на расстоянии до центра куба (порядок ячеек с равными индексами произвольный).
Пример для 2d-массива:
7 4 8
3 0 1
6 2 5
В основном это расстояние в Показатель Манхэттена:
2 1 2
1 0 1
2 1 2
Обход в качестве относительных координат относительно начала координат:
[ 0, 0]
[ 1, 0]
[ 0,-1]
[-1, 0]
[ 0, 1]
[ 1,-1]
[-1,-1]
[-1, 1]
[ 1, 1]
Я знаю о некоторых способах решения этого вопроса, например, о предварительном вычислении всех индексов и их сортировке в соответствии с их расстоянием до начала координат. Однако, поскольку этот алгоритм предназначен для выполнения на графическом процессоре, существуют некоторые ограничения:
- Нет рекурсии (я знаю о возможности рекурсии в
итеративный алгоритм - сохранение стека, однако, не является
подходящее решение в моем опыте)
- Нет автономных вычислений (= расчет на CPU и передача результата на графический процессор). Решение должно быть таким же гибким, как и
возможно
При поиске решений я наткнулся на этот вопрос, и это именно та проблема, которую я, как правило, решаю, принятый ответ, хотя и включает в себя древовидную структуру, которая не соответствует указанным требованиям: Трассировка 3D-массива в другом порядке
Я также подумал о способе создания индексов с использованием сферических координат, что, к сожалению, не дает правильного порядка. Каков подходящий алгоритм для генерирования заданного порядка обхода для 3d-массивов?
Изменить: Штормград предоставил отличное альтернативное описание для данной проблемы: "[Проблема] - это фактически преобразование адресации из одного пространства в другое. Преобразование между 1 (1,2), (1,2) (2,1)... но это больше похоже на преобразование с восходящего 1- (или, по крайней мере, квадрат) на" восходящее октаэдровое многослойное "пространство, когда" восходящий "означает" самый внутренний слой сначала "в дополнение к существующему (хотя и произвольному) порядку приращения на каждой поверхности слоя".
Ответы
Ответ 1
[Я использую Манхэттенское расстояние в решении]
Для простоты давайте начнем принимать 3D-массивы нечетной размерности ([2N+1, 2N+1, 2N+1])
Используя расстояние по манхэттену, наибольшее расстояние между центром ([0,0,0]) и точкой 3N ([N,N,N], [N,N,-N],...)
Итак, в основном идея - найти способ генерации всех координат, имеющих определенное расстояние. Затем, начиная с расстояния 0 до 3N, создавая эти координаты.
Чтобы сгенерировать координаты [X,Y,Z], что расстояние до центра в некотором значении K, нам нужны все числа X, Y, Z между -N и N такими, что ABS(X) + ABS(Y) + ABS(Z) == K, Это можно сделать следующим образом:
FUNC COORDS_AT_DIST(K)
FOR X = -MIN(N, K) TO MIN(N, K)
FOR Y = -MIN(N, K - ABS(X)) TO MIN(N, K - ABS(X))
LET Z = K - ABS(X) - ABS(Y)
IF Z <= N
VISIT(X, Y, Z)
IF Z != 0
VISIT(X, Y, -Z)
Затем используйте эту функцию следующим образом:
FOR K = 0 TO 3N
COORDS_AT_DIST(K)
Этот код посещает все координаты со значениями между [-N,-N,-N] и [N,N,N], отсортированными в соответствии с расстоянием до [0,0,0].
Теперь, чтобы обрабатывать четные измерения, нам нужны дополнительные проверки, так как значения в координатах для измерения L идут между [-(L/2-1),-(L/2-1),-(L/2-1)] и [L/2,L/2,L/2].
Что-то вроде этого:
FUNC VISIT_COORDS_FOR_DIM(L)
LET N = L/2 //Integer division
FOR K = 0 TO 3N
FOR X = -MIN(N - REM(L+1, 2), K) TO MIN(N, K)
FOR Y = -MIN(N - REM(L+1, 2), K - ABS(X)) TO MIN(N, K - ABS(X))
LET Z = K - ABS(X) - ABS(Y)
IF Z <= N
VISIT(X, Y, Z)
IF Z != 0 && (REM(L, 2) != 0 || Z < N)
VISIT(X, Y, -Z)
Просто для ясности:
MIN(X, Y): Minimum value between X and Y
ABS(X): Absolute value of X
REM(X, Y): Remainder after division of X by Y
VISIT(X, Y, Z): Visit the generated coordinate (X, Y, Z)
Используя VISIT_COORDS_FOR_DIM функцию с L=3, вы получите следующее:
1. [0, 0, 0] DISTANCE: 0
2. [-1, 0, 0] DISTANCE: 1
3. [0, -1, 0] DISTANCE: 1
4. [0, 0, -1] DISTANCE: 1
5. [0, 0, 1] DISTANCE: 1
6. [0, 1, 0] DISTANCE: 1
7. [1, 0, 0] DISTANCE: 1
8. [-1, -1, 0] DISTANCE: 2
9. [-1, 0, -1] DISTANCE: 2
10. [-1, 0, 1] DISTANCE: 2
11. [-1, 1, 0] DISTANCE: 2
12. [0, -1, -1] DISTANCE: 2
13. [0, -1, 1] DISTANCE: 2
14. [0, 1, -1] DISTANCE: 2
15. [0, 1, 1] DISTANCE: 2
16. [1, -1, 0] DISTANCE: 2
17. [1, 0, -1] DISTANCE: 2
18. [1, 0, 1] DISTANCE: 2
19. [1, 1, 0] DISTANCE: 2
20. [-1, -1, -1] DISTANCE: 3
21. [-1, -1, 1] DISTANCE: 3
22. [-1, 1, -1] DISTANCE: 3
23. [-1, 1, 1] DISTANCE: 3
24. [1, -1, -1] DISTANCE: 3
25. [1, -1, 1] DISTANCE: 3
26. [1, 1, -1] DISTANCE: 3
27. [1, 1, 1] DISTANCE: 3
И для L=4:
1. [0, 0, 0] DISTANCE: 0 33. [1, -1, -1] DISTANCE: 3
2. [-1, 0, 0] DISTANCE: 1 34. [1, -1, 1] DISTANCE: 3
3. [0, -1, 0] DISTANCE: 1 35. [1, 0, 2] DISTANCE: 3
4. [0, 0, -1] DISTANCE: 1 36. [1, 1, -1] DISTANCE: 3
5. [0, 0, 1] DISTANCE: 1 37. [1, 1, 1] DISTANCE: 3
6. [0, 1, 0] DISTANCE: 1 38. [1, 2, 0] DISTANCE: 3
7. [1, 0, 0] DISTANCE: 1 39. [2, -1, 0] DISTANCE: 3
8. [-1, -1, 0] DISTANCE: 2 40. [2, 0, -1] DISTANCE: 3
9. [-1, 0, -1] DISTANCE: 2 41. [2, 0, 1] DISTANCE: 3
10. [-1, 0, 1] DISTANCE: 2 42. [2, 1, 0] DISTANCE: 3
11. [-1, 1, 0] DISTANCE: 2 43. [-1, -1, 2] DISTANCE: 4
12. [0, -1, -1] DISTANCE: 2 44. [-1, 1, 2] DISTANCE: 4
13. [0, -1, 1] DISTANCE: 2 45. [-1, 2, -1] DISTANCE: 4
14. [0, 0, 2] DISTANCE: 2 46. [-1, 2, 1] DISTANCE: 4
15. [0, 1, -1] DISTANCE: 2 47. [0, 2, 2] DISTANCE: 4
16. [0, 1, 1] DISTANCE: 2 48. [1, -1, 2] DISTANCE: 4
17. [0, 2, 0] DISTANCE: 2 49. [1, 1, 2] DISTANCE: 4
18. [1, -1, 0] DISTANCE: 2 50. [1, 2, -1] DISTANCE: 4
19. [1, 0, -1] DISTANCE: 2 51. [1, 2, 1] DISTANCE: 4
20. [1, 0, 1] DISTANCE: 2 52. [2, -1, -1] DISTANCE: 4
21. [1, 1, 0] DISTANCE: 2 53. [2, -1, 1] DISTANCE: 4
23. [2, 0, 0] DISTANCE: 2 54. [2, 0, 2] DISTANCE: 4
23. [-1, -1, -1] DISTANCE: 3 55. [2, 1, -1] DISTANCE: 4
24. [-1, -1, 1] DISTANCE: 3 56. [2, 1, 1] DISTANCE: 4
25. [-1, 0, 2] DISTANCE: 3 57. [2, 2, 0] DISTANCE: 4
26. [-1, 1, -1] DISTANCE: 3 58. [-1, 2, 2] DISTANCE: 5
27. [-1, 1, 1] DISTANCE: 3 59. [1, 2, 2] DISTANCE: 5
28. [-1, 2, 0] DISTANCE: 3 60. [2, -1, 2] DISTANCE: 5
29. [0, -1, 2] DISTANCE: 3 61. [2, 1, 2] DISTANCE: 5
30. [0, 1, 2] DISTANCE: 3 62. [2, 2, -1] DISTANCE: 5
31. [0, 2, -1] DISTANCE: 3 63. [2, 2, 1] DISTANCE: 5
32. [0, 2, 1] DISTANCE: 3 64. [2, 2, 2] DISTANCE: 6
Это решение имеет такие преимущества, что нет необходимости в какой-либо специальной структуре данных, даже не в массиве.
Другое решение может быть, если вы можете использовать очередь (ее нетрудно реализовать с помощью массива), а 3D-логический (или int) массив - это как BFS, начиная с центра.
Во-первых, чтобы определить, что такое сосед, вы можете использовать массивы перемещения, например:
-
Две ячейки являются соседями, если имеют общую сторону (Манхэттенское расстояние):
DX = { 1, 0, 0, -1, 0, 0 }
DY = { 0, 1, 0, 0, -1, 0 }
DZ = { 0, 0, 1, 0, 0, -1 }
-
Две ячейки являются соседями, если имеют общий ребро:
DX = { 1, 0, 0, -1, 0, 0, 1, 1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0 }
DY = { 0, 1, 0, 0, -1, 0, 1, 0, 1, 1, 0, -1, -1, 0, 1, -1, 0, -1 }
DZ = { 0, 0, 1, 0, 0, -1, 0, 1, 1, 0, 1, 1, 0, -1, -1, 0, -1, -1 }
-
Две ячейки являются соседями, если имеют общий угол (Чебышевское расстояние):
DX = { 1, 0, 0, -1, 0, 0, 1, 1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0, 1, -1, 1, 1, -1, -1, 1, -1 }
DY = { 0, 1, 0, 0, -1, 0, 1, 0, 1, 1, 0, -1, -1, 0, 1, -1, 0, -1, 1, 1, -1, 1, -1, 1, -1, -1 }
DZ = { 0, 0, 1, 0, 0, -1, 0, 1, 1, 0, 1, 1, 0, -1, -1, 0, -1, -1, 1, 1, 1, -1, 1, -1, -1, -1 }
Теперь, используя очередь, вы можете начать с центрального положения, затем добавить соседей, потом соседей соседей и так далее. На каждой итерации вы можете посетить каждую сгенерированную позицию.
Что-то вроде этого:
DX = { 1, 0, 0, -1, 0, 0 }
DY = { 0, 1, 0, 0, -1, 0 }
DZ = { 0, 0, 1, 0, 0, -1 }
VISIT_COORDS_FOR_DIM(L):
LET N = L/2
IF (REM(L, 2) == 0)
N--
V: BOOLEAN[L, L, L]
Q: QUEUE<POINT3D>
V[N, N, N] = TRUE
ENQUEUE(Q, POINT3D(N, N, N))
WHILE COUNT(Q) > 0
P = DEQUEUE(Q)
VISIT(P.X - N, P.Y - N, P.Z - N) //To Transform coords to [-N, N] range.
FOR I = 0 TO LENGTH(DX) - 1
LET X = P.X + DX[I]
LET Y = P.Y + DY[I]
LET Z = P.Z + DZ[I]
IF IS_VALID_POS(L, X, Y, Z) && V[X, Y, Z] == FALSE
V[X, Y, Z] = TRUE
ENQUEUE(Q, POINT3D(X, Y, Z))
IS_VALID_POS(L, X, Y, Z)
RETURN X >= 0 && X < L &&
Y >= 0 && Y < L &&
Z >= 0 && Z < L
Используемые функции:
REM(X, Y): Remainder after division of X by Y
ENQUEUE(Q, X): Enqueue element X in queue Q
DEQUEUE(Q): Dequeue first element from queue Q
COUNT(Q): Number of elements in queue Q
VISIT(X, Y, Z): Visit the generated coordinate (X, Y, Z)
Это решение имеет преимущества, которые вы можете определить, когда две позиции являются соседями, использующими массивы перемещения.
Ответ 2
Подумав некоторое время, я придумал идею представлять 3d-массив как последовательность узлов с направлениями: +i, -i, +j, -j, +k, -k.
Подход
Для 2-мерного массива было бы достаточно иметь только три правила:
- Каждая итерация по каждой из них node перемещает ее вдоль своей оси в ее направлении, т.е. node
+j будет увеличивать 2-й индекс, node -i уменьшит 1-й индекс.
- Существует два типа узлов:
Main и Secondary. Основная ось имеет один индекс 0. Каждая итерация над вершинами оси Main i и j (я буду называть их i и j) производит Secondary node по часовой стрелке на 90 градусов:
-
+I -> -j
-
-J -> -i
-
-I -> +j
-
+J -> +i
- Каждый node имеет время жизни, которое уменьшает каждую итерацию. Время жизни node равно
(n-1)/2 для нечетных значений n (для четных значений см. Код ниже). После того, как время жизни достигнет 0, следует удалить node.
Чтобы включить третье измерение, необходимо применить другое правило:
- Третий тип узлов с направлением вдоль оси
k (здесь - глубина) создает на каждой итерации набор осей i и j:
-
+K -> +I, -J, -I, +J
-
-K -> +I, -J, -I, +J
Вот как это будет выглядеть:
![3D array]()
При таком подходе элементы будут автоматически отсортированы по расстоянию Манхэттена, как в решении Артуро Менчаки.
Реализация
Вот код python, который делает то, что я описал. Существует много места для усовершенствований, это просто доказательство концепции. У него нет сортировки, нет рекурсии, и я не вижу никаких автономных вычислений.
Он также содержит несколько тестов. Run
NO = ( 0, 0, 0, 2, 0)
Pi = (+1, 0, 0, 0, 0)
PI = (+1, 0, 0, 0, 1)
Pj = ( 0,+1, 0, 0, 0)
PJ = ( 0,+1, 0, 0, 1)
PK = ( 0, 0,+1, 0, 2)
Mi = (-1, 0, 0, 1, 0)
MI = (-1, 0, 0, 1, 1)
Mj = ( 0,-1, 0, 1, 0)
MJ = ( 0,-1, 0, 1, 1)
MK = ( 0, 0,-1, 1, 2)
# i j k ^ ^
# | Id for comparison
# Lifetime index
PRODUCE = {
PI: [ Mj ], # +I -> -j
MJ: [ Mi ], # -J -> -i
MI: [ Pj ], # -I -> +j
PJ: [ Pi ], # +J -> +i
NO: [ NO ],
Pi: [ NO ],
Pj: [ NO ],
Mi: [ NO ],
Mj: [ NO ],
PK: [ PI, MI, PJ, MJ ], # +K -> +I, -J, -I, +J
MK: [ PI, MI, PJ, MJ ], # -K -> +I, -J, -I, +J
}
class Index:
LastDistance = 0
NumberOfVisits = 0
MinIndex = 0
MaxIndex = 0
def __init__(self, i, j, k, lifetime, direction):
self.globalLifetime = lifetime
self.direction = direction
# Assign parent position
self.i = i
self.j = j
self.k = k
# Step away from parent
self.lifetime = lifetime[direction[3]]
self.step()
def isLive(self):
return self.lifetime > 0
def visit(self):
Index.NumberOfVisits += 1
distance = self.distance()
if distance < Index.LastDistance:
raise NameError("Order is not preserved")
Index.LastDistance = distance
Index.MinIndex = min(self.i, Index.MinIndex)
Index.MinIndex = min(self.j, Index.MinIndex)
Index.MinIndex = min(self.k, Index.MinIndex)
Index.MaxIndex = max(self.i, Index.MaxIndex)
Index.MaxIndex = max(self.j, Index.MaxIndex)
Index.MaxIndex = max(self.k, Index.MaxIndex)
print("[{}, {}, {}]".format(self.i, self.j, self.k))
def step(self):
# Move in your direction
self.i += self.direction[0]
self.j += self.direction[1]
self.k += self.direction[2]
def iterate(self):
self.lifetime -= 1
def produce(self, result):
for direction in PRODUCE[self.direction]:
self.create(direction, result)
def create(self, direction, result):
index = Index(self.i, self.j, self.k, self.globalLifetime, direction)
if index.isLive():
result.append(index)
def distance(self):
# Manhattan Distance
return abs(self.i) + abs(self.j) + abs(self.k)
def Traverse(N):
TotalNumber = N*N*N
halfA = halfB = (N-1)/2
if N % 2 == 0:
halfA = N/2
halfB = N/2-1
MinIndex = -min(halfB, halfA)
MaxIndex = max(halfB, halfA)
lifetime = (halfA, halfB, 0)
SecondaryNodes = []
MainNodes = []
KNodes = []
# visit center
center = Index(0, 0, 0, lifetime, NO)
center.visit()
center.create(PI, MainNodes)
center.create(MI, MainNodes)
center.create(PJ, MainNodes)
center.create(MJ, MainNodes)
center.create(PK, KNodes)
center.create(MK, KNodes)
while len(SecondaryNodes) + len(MainNodes) + len(KNodes) > 0:
# First - visit all side nodes
temp = []
for m in SecondaryNodes:
m.visit()
m.step()
m.iterate()
# Save node only if it is alive
if m.isLive():
temp.append(m)
SecondaryNodes = temp
# Second - visit all main nodes as they may produce secondary nodes
temp = []
for m in MainNodes:
m.visit() # 1 - Visit
m.produce(SecondaryNodes) # 2 - Produce second
m.step() # 3 - Step
m.iterate() # 4 - Lose a life
if m.isLive():
temp.append(m)
MainNodes = temp
# Third - visit all K nodes as they may produce main nodes
temp = []
for m in KNodes:
m.visit()
m.produce(MainNodes)
m.step()
m.iterate()
if m.isLive():
temp.append(m)
KNodes = temp
if TotalNumber != Index.NumberOfVisits:
raise NameError("Number of visited elements does not match {}/{}".format(Index.NumberOfVisits, TotalNumber))
if MinIndex != Index.MinIndex:
raise NameError("Minimal index is out of bounds {}/{}".format(Index.MinIndex, MinIndex))
if MaxIndex != Index.MaxIndex:
raise NameError("Maximal index is out of bounds {}/{}".format(Index.MaxIndex, MaxIndex))
Traverse(6)
Упрощенная реализация
Класс помощника для хранения индекса:
class Index:
def __init__(self, i, j, k, lifetime):
self.i = i
self.j = j
self.k = k
self.lifetime = lifetime
def visit(self):
print("[{}, {}, {}]".format(self.i, self.j, self.k))
Набор функций для итерации узлов Main в правильном направлении:
def StepMainPlusI(mainPlusI, minusJ, lifetime):
result = []
for m in mainPlusI:
if lifetime > 0:
minusJ.append(Index(m.i, m.j-1, m.k, lifetime))
m.lifetime -= 1
m.i += 1
if m.lifetime > 0:
result.append(m)
return result
def StepMainMinusJ(mainMinusJ, minusI, lifetime):
result = []
for m in mainMinusJ:
if lifetime > 0:
minusI.append(Index(m.i-1, m.j, m.k, lifetime))
m.lifetime -= 1
m.j -= 1
if m.lifetime > 0:
result.append(m)
return result
def StepMainMinusI(mainMinusI, plusJ, lifetime):
result = []
for m in mainMinusI:
if lifetime > 0:
plusJ.append(Index(m.i, m.j+1, m.k, lifetime))
m.lifetime -= 1
m.i -= 1
if m.lifetime > 0:
result.append(m)
return result
def StepMainPlusJ(mainPlusJ, plusI, lifetime):
result = []
for m in mainPlusJ:
if lifetime > 0:
plusI.append(Index(m.i+1, m.j, m.k, lifetime))
m.lifetime -= 1
m.j += 1
if m.lifetime > 0:
result.append(m)
return result
Набор функций для итерации трехмерных узлов k:
def StepMainPlusK(mainPlusK, mainPlusI, mainMinusI, mainPlusJ, mainMinusJ, lifetimeA, lifetimeB):
result = []
for m in mainPlusK:
if lifetimeA > 0:
mainPlusI.append(Index(+1, 0, m.k, lifetimeA))
mainPlusJ.append(Index(0, +1, m.k, lifetimeA))
if lifetimeB > 0:
mainMinusI.append(Index(-1, 0, m.k, lifetimeB))
mainMinusJ.append(Index(0, -1, m.k, lifetimeB))
m.lifetime -= 1
m.k += 1
if m.lifetime > 0:
result.append(m)
return result
def StepMainMinusK(mainMinusK, mainPlusI, mainMinusI, mainPlusJ, mainMinusJ, lifetimeA, lifetimeB):
result = []
for m in mainMinusK:
if lifetimeA > 0:
mainPlusI.append(Index(+1, 0, m.k, lifetimeA))
mainPlusJ.append(Index(0, +1, m.k, lifetimeA))
if lifetimeB > 0:
mainMinusI.append(Index(-1, 0, m.k, lifetimeB))
mainMinusJ.append(Index(0, -1, m.k, lifetimeB))
m.lifetime -= 1
m.k -= 1
if m.lifetime > 0:
result.append(m)
return result
Эти две функции имеют два разных параметра времени жизни для случая, когда n нечетно, а половина может быть меньше другого. Я разделил их на знак - отрицательно ориентированная будет иметь более низкую половину индексов.
Набор функций для итерации узлов Secondary:
def StepPlusI(plusI):
result = []
for m in plusI:
m.i += 1
m.lifetime -= 1
if m.lifetime > 0:
result.append(m)
return result
def StepMinusI(minusI):
result = []
for m in minusI:
m.i -= 1
m.lifetime -= 1
if m.lifetime > 0:
result.append(m)
return result
def StepPlusJ(plusJ):
result = []
for m in plusJ:
m.j += 1
m.lifetime -= 1
if m.lifetime > 0:
result.append(m)
return result
def StepMinusJ(minusJ):
result = []
for m in minusJ:
m.j -= 1
m.lifetime -= 1
if m.lifetime > 0:
result.append(m)
return result
И основная функция:
def Traverse(N):
halfA = halfB = (N-1)/2
if N % 2 == 0: # size is even
halfA = N/2
halfB = N/2-1
# visit center
Index(0,0,0,0).visit()
# Secondary nodes
PlusI = []
MinusI = []
PlusJ = []
MinusJ = []
# Main nodes
MainPlusI = []
MainMinusI = []
MainPlusJ = []
MainMinusJ = []
MainPlusK = []
MainMinusK = []
# Add Main nodes
if halfA > 0:
MainPlusI.append( Index(+1, 0, 0, halfA) )
MainPlusJ.append( Index(0, +1, 0, halfA) )
MainPlusK.append( Index(0, 0, +1, halfA) )
if halfB > 0:
MainMinusI.append( Index(-1, 0, 0, halfB) )
MainMinusJ.append( Index(0, -1, 0, halfB) )
MainMinusK.append( Index(0, 0, -1, halfB) )
# Finish condition flag
visited = True
while visited:
visited = False
# visit all Main nodes
for m in MainPlusI:
m.visit()
visited = True
for m in MainMinusI:
m.visit()
visited = True
for m in MainPlusJ:
m.visit()
visited = True
for m in MainMinusJ:
m.visit()
visited = True
for m in MainPlusK:
m.visit()
visited = True
for m in MainMinusK:
m.visit()
visited = True
# Visit all Secondary nodes
for m in PlusI:
m.visit()
visited = True
for m in MinusI:
m.visit()
visited = True
for m in PlusJ:
m.visit()
visited = True
for m in MinusJ:
m.visit()
visited = True
# Iterate Secondary nodes first
PlusI = StepPlusI(PlusI)
MinusI = StepMinusI(MinusI)
PlusJ = StepPlusJ(PlusJ)
MinusJ = StepMinusJ(MinusJ)
# Iterate all Main nodes as they might generate Secondary nodes
MainPlusI = StepMainPlusI(MainPlusI, MinusJ, halfB)
MainMinusJ = StepMainMinusJ(MainMinusJ, MinusI, halfB)
MainMinusI = StepMainMinusI(MainMinusI, PlusJ, halfA)
MainPlusJ = StepMainPlusJ(MainPlusJ, PlusI, halfA)
# Iterate K nodes last as they might produce Main nodes
MainPlusK = StepMainPlusK(MainPlusK, MainPlusI, MainMinusI, MainPlusJ, MainMinusJ, halfA, halfB)
MainMinusK = StepMainMinusK(MainMinusK, MainPlusI, MainMinusI, MainPlusJ, MainMinusJ, halfA, halfB)
И живой пример Code
Ответ 3
Октатная симметрия
Клетки в кубической матрице, находящиеся на некотором расстоянии от центра Манхэттена, образуют октаэдр, симметричный относительно плоскостей ху, xz и yz, проходящих через центр куба.
![расстояние 3 в матрице 9x9x9]()
Это означает, что вам нужно всего лишь найти ячейки, которые образуют одну грань октаэдра, в первом octant куба, и зеркалировать их, чтобы получить ячейки в других 7 октантах. Таким образом, проблема сводится к пересечению первого октананта куба (который сам является кубом) по диагонали, от центра (расстояние 0) до угловой ячейки (максимальное расстояние = 3 & times; n/2).
![расстояние 3 в первом октане]()
Алгоритм для нахождения координат
Поиск клеток, находящихся на некотором расстоянии Манхэттена от (0,0,0) ячейки в первом октанте (т.е. клетки, которые образуют одну грань октаэдра, перпендикулярно диагонали куба), означает нахождение ячеек, координаты которых (x, y, z) суммируются с этим расстоянием. Итак, в примере октанта 5x5x5 ячейки на расстоянии 3 являются ячейками с координатами:
(3,0,0) (2,1,0) (1,2,0) (0,3,0)
(2,0,1) (1,1,1) (0,2,1)
(1,0,2) (0,1,2)
(0,0,3)
Вы заметите сходство с разбиением расстояния (на самом деле это так называемый слабый состав с ограниченной длиной 3).
Поиск этих комбинаций может быть легко осуществлен с помощью трех вложенных циклов; единственное усложнение заключается в том, что расстояние в каждом измерении ограничено n/2, поэтому вам нужно пропустить значения для x и/или y, для которых не существует значения для z, так что x, y и z суммируются с расстоянием; это пример min() и max() в примере кода JavaScript и переменные xmin, xmax, ymin и ymax в примере кода C.
Зеркализация ячеек в кубе четного размера проста; в кубе нечетного размера ячейки не отражаются в размерности, для которой их координата равна нулю (т.е. когда ячейка лежит в плоскости симметрии). Это то, что проверяет, являются ли x, y или z равными нулю в примерах кода.
Параллельное программирование
Я мало знаю о программировании на GPU, но я предполагаю, что вы можете полностью параллелизировать алгоритм. Для каждой итерации внешнего цикла (т.е. Для каждого расстояния), после вычисления минимального и максимального значений x, итерации с разными значениями x могут выполняться параллельно. Затем для каждого значения x после вычисления минимального и максимального значений y итерации с разными значениями y могут выполняться параллельно. И, наконец, для каждого набора координат (x, y, z) зеркальное отображение других октантов может выполняться параллельно.
Пример кода 1 (JavaScript)
(запустите фрагмент кода, чтобы увидеть обход изнутри матрицы 9x9x9, как показано на диаграммах.)
function insideOut(n) {
var half = Math.ceil(n / 2) - 1;
for (var d = 0; d <= 3 * half; d++) {
for (var x = Math.max(0, d - 2 * half); x <= Math.min(half, d); x++) {
for (var y = Math.max(0, d - x - half); y <= Math.min(half, d - x); y++) {
document.write("<br>distance " + d + " (±" + x + ",±" + y + ",±" + (d - x - y) + ") → ");
n % 2 ? mirrorOdd(x, y, d - x - y) : mirrorEven(x, y, d - x - y);
}
}
}
function mirrorEven(x, y, z) {
for (var i = 1; i >= 0; --i, x *= -1) {
for (var j = 1; j >= 0; --j, y *= -1) {
for (var k = 1; k >= 0; --k, z *= -1) {
visit(half + x + i, half + y + j, half + z + k);
}
}
}
}
function mirrorOdd(x, y, z) {
for (var i = 0; i < (x ? 2 : 1); ++i, x *= -1) {
for (var j = 0; j < (y ? 2 : 1); ++j, y *= -1) {
for (var k = 0; k < (z ? 2 : 1); ++k, z *= -1) {
visit(half + x, half + y, half + z);
}
}
}
}
function visit(x, y, z) {
document.write("(" + x + "," + y + "," + z + ") " );
}
}
insideOut(9);
Ответ 4
Ключом к тому, чтобы получить эффективный алгоритм для этого вопроса, является наличие геометрии, лежащей в основе этого вопроса. То, о чем вы просите, состоит в том, чтобы решить диофантовое уравнение N = a ^ 2 + b ^ 2 + c ^ 2 для каждого последующего значения N, перечисляя такие решения в любом порядке. Решения этого уравнения являются целыми точками на сфере радиуса N. Итак, в некотором смысле ваша задача - перечисление сфер.
Во-первых, должно быть ясно, что здесь сложная проблема заключается в перечислении неотрицательных решений для координат (a, b, c). Для каждой такой координаты существует восемь других решений зеркальной симметрии вокруг координатных плоскостей, так как a ^ 2 = (-a) ^ 2 и т.д. (В общем случае, если один или несколько из a, b, c равны нулю, вы получаете меньше зеркальных точек.) Там есть дополнительная симметрия, переставляя координаты так, чтобы a <= b <= c. Это легкая часть перечисления.
Суть алгоритма перечисления сферы состоит в том, чтобы рассмотреть два набора точек, которые аппроксимируют сферу радиуса N: одну, которая состоит из точек с нормой "чуть меньше", чем N, и одной, которая состоит из их решеточных соседей с нормой "немного больше", чем N или равно N. "Чуть меньше" означает, что для точки (a, b, c) a ^ 2 + b ^ 2 + c ^ 2 < N, но одна или несколько точек (a + 1, b, c), (a, b + 1, c) или (a, b, c + 1) имеют норму >= N. Что касается кода, вам не нужно представлять "немного меньше"; он уже обработан. Этого достаточно, чтобы создать кучу "немного большего" набора, отсортированного по их норме.
Каждый шаг алгоритма изменяется на "немного большее" множество для N в один для N + 1. Удалите наименьший элемент кучи, скажем, (a, b, c). Теперь добавим к куче свои ближайшие соседние точки с большей нормой, три точки (a + 1, b, c), (a, b + 1, c) и (a, b, c + 1). Некоторые из них уже могут быть там; Я вернусь к этому. Когда вы добавляете инкрементную точку в кучу, вам нужна ее норма. Однако вам не нужно вычислять его с нуля. Положитесь на тождество (a + 1) ^ 2 - a ^ 2 = 2a + 1. Другими словами, вам не нужны операции умножения для вычисления этих норм. В зависимости от вашего графического процессора вы можете вычислять выражения a < 1 + 1 или, возможно, a + a + 1.
Вы также можете оптимизировать проверку существующих точек в куче. Каждая точка имеет шесть ближайших соседних решетчатых соседей. Сосед с решеткой с наименьшей нормой будет первым, кто ее добавит. Предположим, b < c для точки (a, b, c). Его сосед с наименьшей нормой (a, b, c-1). Таким образом, при перечислении точки (a-1, b, c) точка (a, b, c) уже находится в куче; вам не нужно даже проверять его там. Обратите внимание на особые случаи, когда некоторые из координат равны.
Этот алгоритм перечисляет сферы, а не кубы. Достаточно легко ограничить внимание кубом с максимальным индексом D. Если одна из координат равна D, то не добавляйте три точки, но меньше. Перечисление заканчивается на точке (D, D, D), когда нет более подходящих соседних точек для добавления.
Производительность этого алгоритма должна быть очень быстрой. Ему нужна куча размера O (N ^ 2). Если вы перечисляете все баллы заранее, вам нужно хранить O (N ^ 3). Кроме того, он не нуждается в умножении, для дальнейшей постоянной скорости.
Ответ 5
Если это просто центры: существует множество разных действительных заказов. Просто вычислите 3d-карту с упорядоченными по порядку элементами. Смещение по происхождению. Сделайте карту:
for x,y,z -domain, domain
map.add ( x,y,z, distance(x,y,z) )
map.sort ( distance )
Тогда в точке x, y, z пройти через
for ( i=0; i++ )
visit ( map[i].xyz + x,y,z )
Если это реальное расстояние, а не воксельные центры, это становится намного сложнее.
Ответ 6
генерирование индексов в порядке Manhatan distance аналогично задаче subset sum, поэтому просто вычислите максимальное расстояние (сумму), а затем разделите оси, чтобы уменьшить проблему. Здесь С++ пример:
int x,y,z,d,dx,dy,dz,D;
// center idx
int cx=n>>1;
int cy=n>>1;
int cz=n>>1;
// min idx
int x0=-cx;
int y0=-cy;
int z0=-cz;
// max idx
int x1=n-1-cx;
int y1=n-1-cy;
int z1=n-1-cz;
// max distance
x=max(x0,x1);
y=max(y0,y1);
z=max(z0,z1);
D=x+y+z;
// here do your stuff
#define traverse(x,y,z) { /* do something with the array beware x,y,z are signed !!! */ }
// traversal
for (d=0;d<=D;d++) // distance
for (dx=d ,x=-dx;x<=dx;x++) if ((x>=x0)&&(x<=x1)) // x axis separation
for (dy=d-abs(x) ,y=-dy;y<=dy;y++) if ((y>=y0)&&(y<=y1)) // y axis separation
{
dz=d-abs(x)-abs(y); // z axis have only 1 or 2 options
z=-dz; if (z>=z0) traverse(x,y,z);
z=+dz; if ((z)&&(z<=z1)) traverse(x,y,z);
}
#undef traverse
Вы можете заменить макрос traverse(x,y,z) на любой материал или функцию, которую вы хотите. beware x,y,z, поэтому они могут быть отрицательными, чтобы получить индексы стиля С++, которые вам нужно использовать (x+cx,y+cy,z+cz).
Это может обрабатывать четные и нечетные индексы, а также нечеткие разрешения (если вы просто конвертируете n в nx,ny,nz в первые несколько вычислений констант). Также [0,0,0] может быть везде (не в центре), поэтому он легко применим к любым потребностям, которые я могу придумать...
Здесь пример вывода для n=5
[ 0, 0, 0] = 0
[-1, 0, 0] = 1
[ 0,-1, 0] = 1
[ 0, 0,-1] = 1
[ 0, 0, 1] = 1
[ 0, 1, 0] = 1
[ 1, 0, 0] = 1
[-2, 0, 0] = 2
[-1,-1, 0] = 2
[-1, 0,-1] = 2
[-1, 0, 1] = 2
[-1, 1, 0] = 2
[ 0,-2, 0] = 2
[ 0,-1,-1] = 2
[ 0,-1, 1] = 2
[ 0, 0,-2] = 2
[ 0, 0, 2] = 2
[ 0, 1,-1] = 2
[ 0, 1, 1] = 2
[ 0, 2, 0] = 2
[ 1,-1, 0] = 2
[ 1, 0,-1] = 2
[ 1, 0, 1] = 2
[ 1, 1, 0] = 2
[ 2, 0, 0] = 2
[-2,-1, 0] = 3
[-2, 0,-1] = 3
[-2, 0, 1] = 3
[-2, 1, 0] = 3
[-1,-2, 0] = 3
[-1,-1,-1] = 3
[-1,-1, 1] = 3
[-1, 0,-2] = 3
[-1, 0, 2] = 3
[-1, 1,-1] = 3
[-1, 1, 1] = 3
[-1, 2, 0] = 3
[ 0,-2,-1] = 3
[ 0,-2, 1] = 3
[ 0,-1,-2] = 3
[ 0,-1, 2] = 3
[ 0, 1,-2] = 3
[ 0, 1, 2] = 3
[ 0, 2,-1] = 3
[ 0, 2, 1] = 3
[ 1,-2, 0] = 3
[ 1,-1,-1] = 3
[ 1,-1, 1] = 3
[ 1, 0,-2] = 3
[ 1, 0, 2] = 3
[ 1, 1,-1] = 3
[ 1, 1, 1] = 3
[ 1, 2, 0] = 3
[ 2,-1, 0] = 3
[ 2, 0,-1] = 3
[ 2, 0, 1] = 3
[ 2, 1, 0] = 3
[-2,-2, 0] = 4
[-2,-1,-1] = 4
[-2,-1, 1] = 4
[-2, 0,-2] = 4
[-2, 0, 2] = 4
[-2, 1,-1] = 4
[-2, 1, 1] = 4
[-2, 2, 0] = 4
[-1,-2,-1] = 4
[-1,-2, 1] = 4
[-1,-1,-2] = 4
[-1,-1, 2] = 4
[-1, 1,-2] = 4
[-1, 1, 2] = 4
[-1, 2,-1] = 4
[-1, 2, 1] = 4
[ 0,-2,-2] = 4
[ 0,-2, 2] = 4
[ 0, 2,-2] = 4
[ 0, 2, 2] = 4
[ 1,-2,-1] = 4
[ 1,-2, 1] = 4
[ 1,-1,-2] = 4
[ 1,-1, 2] = 4
[ 1, 1,-2] = 4
[ 1, 1, 2] = 4
[ 1, 2,-1] = 4
[ 1, 2, 1] = 4
[ 2,-2, 0] = 4
[ 2,-1,-1] = 4
[ 2,-1, 1] = 4
[ 2, 0,-2] = 4
[ 2, 0, 2] = 4
[ 2, 1,-1] = 4
[ 2, 1, 1] = 4
[ 2, 2, 0] = 4
[-2,-2,-1] = 5
[-2,-2, 1] = 5
[-2,-1,-2] = 5
[-2,-1, 2] = 5
[-2, 1,-2] = 5
[-2, 1, 2] = 5
[-2, 2,-1] = 5
[-2, 2, 1] = 5
[-1,-2,-2] = 5
[-1,-2, 2] = 5
[-1, 2,-2] = 5
[-1, 2, 2] = 5
[ 1,-2,-2] = 5
[ 1,-2, 2] = 5
[ 1, 2,-2] = 5
[ 1, 2, 2] = 5
[ 2,-2,-1] = 5
[ 2,-2, 1] = 5
[ 2,-1,-2] = 5
[ 2,-1, 2] = 5
[ 2, 1,-2] = 5
[ 2, 1, 2] = 5
[ 2, 2,-1] = 5
[ 2, 2, 1] = 5
[-2,-2,-2] = 6
[-2,-2, 2] = 6
[-2, 2,-2] = 6
[-2, 2, 2] = 6
[ 2,-2,-2] = 6
[ 2,-2, 2] = 6
[ 2, 2,-2] = 6
[ 2, 2, 2] = 6
Ответ 7
Расстояние от начала координат известно, что для каждой точки (a, b, c) должно быть sqrt(a*a + b*b + c*c). Мы можем определить это как distance(a, b, c). & dagger;
Для каждой точки вашего 3D-массива вы можете вставить ее в min heap, используя distance в качестве ваших критериев заказа. Чтобы избежать перерасчета, добавьте свое представление точки в кучу, чтобы включить кешированный расчет distance для этой точки, когда он был вставлен в кучу.
heap_element = (x, y, z, d)
heap_compare (heap_element a, heap_element b) = a.d < b.d
для каждой точки (x, y, z) в трехмерном массиве
& middot; heap.add(heap_element (x, y, z, distance (x, y, z)))
Теперь вы можете просто вытащить каждую точку из верхней части кучи, чтобы получить ваш заказ.
N = heap.size
для я в 0..N
& middot; заказ [i] = heap.top
& middot; heap.pop
<суб > &кинжал; Для целей этого алгоритма использование фактического расстояния не является критическим. По соображениям производительности вы можете опустить sqrt и просто использовать a*a + b*b + c*c как метрику для критериев упорядочения кучи.
Суб >
Ответ 8
В рубине я просто получаю все точки за каждое расстояние от центра по порядку.
def get_points(side_len)
side_len % 2 == 0 ? min_dist = 1 : min_dist = 0
if side_len % 2 == 0
min_dist = 1
max_1d_dist = side_len / 2
else
min_dist = 0
max_1d_dist = (side_len - 1) / 2
end
max_dist = 3 * max_1d_dist
min_dist.upto(max_dist) do |dist|
min_x_dist = [min_dist, dist - 2 * max_1d_dist].max
max_x_dist = [dist - 2 * min_dist, max_1d_dist].min
min_x_dist.upto(max_x_dist) do |x_dist|
min_y_dist = [min_dist, dist - x_dist - max_1d_dist].max
max_y_dist = [dist - x_dist - min_dist, max_1d_dist].min
min_y_dist.upto(max_y_dist) do |y_dist|
z_dist = dist - x_dist - y_dist
print_vals(x_dist, y_dist, z_dist)
end
end
end
end
def print_vals(x_dist, y_dist, z_dist)
x_signs = [1]
y_signs = [1]
z_signs = [1]
x_signs << -1 unless x_dist == 0
y_signs << -1 unless y_dist == 0
z_signs << -1 unless z_dist == 0
x_signs.each do |x_sign|
y_signs.each do |y_sign|
z_signs.each do |z_sign|
puts "[#{x_sign*x_dist}, #{y_sign*y_dist}, #{z_sign*z_dist}]"
end
end
end
end
Выход:
2.1.2 :277 > get_points(1)
[0, 0, 0]
2.1.2 :278 > get_points(2)
[1, 1, 1]
[1, 1, -1]
[1, -1, 1]
[1, -1, -1]
[-1, 1, 1]
[-1, 1, -1]
[-1, -1, 1]
[-1, -1, -1]
2.1.2 :279 > get_points(3)
[0, 0, 0]
[0, 0, 1]
[0, 0, -1]
[0, 1, 0]
[0, -1, 0]
[1, 0, 0]
[-1, 0, 0]
[0, 1, 1]
[0, 1, -1]
[0, -1, 1]
[0, -1, -1]
[1, 0, 1]
[1, 0, -1]
[-1, 0, 1]
[-1, 0, -1]
[1, 1, 0]
[1, -1, 0]
[-1, 1, 0]
[-1, -1, 0]
[1, 1, 1]
[1, 1, -1]
[1, -1, 1]
[1, -1, -1]
[-1, 1, 1]
[-1, 1, -1]
[-1, -1, 1]
[-1, -1, -1]
Ответ 9
Это простой и быстрый алгоритм для поперечного перемещения трехмерного массива с использованием Манхэттенского расстояния.
3D-массив с размером n в каждом измерении должен быть представлен системой координат с началом в середине вашего массива. Для определения центра, мы предполагаем, что размер массива в каждом измерении является нечетным числом. Каждый элемент имеет тройную координату, подобную этой [x, y, z], и каждая координата может достигать максимального значения `(n/2) -1. (Информация: Добавленные фотографии в 2D для лучшего понимания)
- Сначала мы можем упростить это, рассматривая только положительный октант (все координаты положительны). Все остальные элементы могут быть получены путем отражения.
![введите описание изображения здесь]()
- В одном октане все элементы с одинаковым расстоянием до центра определяются плоскостью с уравнением:
x+y+z=distance. Мы достигаем этого путем подсчета расстояния от 0 до n-1 за один шаг. Для каждого расстояния мы ищем весь элемент на соответствующей плоскости.
![введите описание изображения здесь]()
- При достижении
distance>(n/2)-1 некоторые из точек будут вне массива (один из coord > (n/2)-1). Поэтому мы должны исключить их из результатов.
![введите описание изображения здесь]()
- Каждый вычисленный элемент представляет до 8 элементов, которые вы получаете отражением (см. пункт 1). Вы можете просто добиться этого, поочередно умножая каждую координату на
-1. [+/-x, +/-y, +/-z] (8 возможных комбинаций, если все coords != 0)
![введите описание изображения здесь]()
Вот схема кода для моего алгоритма:
//rise the distance by one each iteration
for(distance=0; distance<n-1; distance++) //loop distance from 0 to n-1
for(i=0; i<=distance; i++)
x=i; //x ∈ [0, distance]
for(j=0; j<=distance-x; j++)
y=j; //y ∈ [0, distance-x]
z=distance-(x+y); //because distance=x+y+z
//now we have to exclude all elements with one coord <= (n/2)-1
if(x<=(n/2)-1 && y<=(n/2)-1 && z<=(n/2)-1)
//[x,y,z] we found a valid element!
//let generate the 7 corresponding elements (up to 7)
if(x!=0) //[-x,y,z]
if(y!=0) //[x,-y,z]
if(z!=0) //[x,y,-z]
if(x!=0 && y!=0) //[-x,-y,z]
if(x!=0 && z!=0) //[-x,y,-z]
if(y!=0 && z!=0) //[x,-y,-z]
if(y!=0 && y!=0 && z!=0) //[-x,-y,-z]
Вот результат для n=7:
Distance:0 [0,0,0]
Distance:1 [0,0,1] [0,0,-1] [0,1,0] [0,-1,0] [1,0,0] [-1,0,0]
Distance:2 [0,0,2] [0,0,-2] [0,1,1] [0,-1,1] [0,1,-1] [0,-1,-1] [0,2,0] [0,-2,0] [1,0,1] [-1,0,1] [1,0,-1] [-1,0,-1] [1,1,0] [-1,1,0] [1,-1,0] [-1,-1,0] [2,0,0] [-2,0,0]
Distance:3 [0,1,2] [0,-1,2] [0,1,-2] [0,-1,-2] [0,2,1] [0,-2,1] [0,2,-1] [0,-2,-1] [1,0,2] [-1,0,2] [1,0,-2] [-1,0,-2] [1,1,1] [-1,1,1] [1,-1,1] [1,1,-1] [-1,-1,1] [-1,1,-1] [1,-1,-1] [-1,-1,-1] [1,2,0] [-1,2,0] [1,-2,0] [-1,-2,0] [2,0,1] [-2,0,1] [2,0,-1] [-2,0,-1] [2,1,0] [-2,1,0] [2,-1,0] [-2,-1,0]
Distance:4 [0,2,2] [0,-2,2] [0,2,-2] [0,-2,-2] [1,1,2] [-1,1,2] [1,-1,2] [1,1,-2] [-1,-1,2] [-1,1,-2] [1,-1,-2] [-1,-1,-2] [1,2,1] [-1,2,1] [1,-2,1] [1,2,-1] [-1,-2,1] [-1,2,-1] [1,-2,-1] [-1,-2,-1] [2,0,2] [-2,0,2] [2,0,-2] [-2,0,-2] [2,1,1] [-2,1,1] [2,-1,1] [2,1,-1] [-2,-1,1] [-2,1,-1] [2,-1,-1] [-2,-1,-1] [2,2,0] [-2,2,0] [2,-2,0] [-2,-2,0]
Distance:5 [1,2,2] [-1,2,2] [1,-2,2] [1,2,-2] [-1,-2,2] [-1,2,-2] [1,-2,-2] [-1,-2,-2] [2,1,2] [-2,1,2] [2,-1,2] [2,1,-2] [-2,-1,2] [-2,1,-2] [2,-1,-2] [-2,-1,-2] [2,2,1] [-2,2,1] [2,-2,1] [2,2,-1] [-2,-2,1] [-2,2,-1] [2,-2,-1]
Если вы используете Евклидскую норму, вам нужно заменить свое расстояние: sqrt(x*x+y*y+z*z), и вы не можете увеличить расстояние с шагом один. Но помимо этого вы могли бы сделать это очень похоже.
Ответ 10
Дождался, пока гонка ралли не будет завершена, чтобы не мешать. Тем не менее я хотел бы отметить, что imho все ответы, которые я вижу atm, довольно сомнительны. Вопрос содержит следующее утверждение:
"этот алгоритм предназначен для выполнения на графическом процессоре"
Действительно, можно делать эффективную числовую обработку на графическом процессоре, но все решения здесь предлагают какой-то цикл. Это не то, как работает графический процессор.
Графический процессор выполняется параллельно. Действительно, в GPU можно зацикливаться, но тогда это происходит чрезвычайно изолированным образом. Для цикла требуется "глобальный контроллер", например счетчик, но точка выполнения графического процессора заключается в том, что он выполняется в без определенного порядка, используя несколько ядер. Невозможно "захватить" результат выполнения одного ядра и использовать его в качестве аргумента для вычисления других ядер. Это просто не то, как работает графический процессор.
Возможно вычисление многомерных массивов на графическом процессоре, даже на 3-мерном. Это всего лишь вопрос адресации ячеек, и тривиально обратиться, например, к 4 измерениям с использованием одномерного адресного пространства и описать/получить доступ к соответствующим данным.
Но невозможно переходить через ячейки (пиксели, ячейки памяти) один за другим, в определенном порядке - для этого нет никакого контроля. И невозможно увеличивать или иметь петли или иметь внутренние циклы. На графическом процессоре последний элемент может быть выполнен первым. На графическом процессоре каждый элемент полностью автономный. Никакой расчет не знает о каких-либо других расчетах, поскольку между ними нет связи. Окружающая среда для каждого вычисления на графическом процессоре является , если она была одна в мире.
Ответы, приведенные в этом потоке, предполагают логику CPU. Если решить проблему с CPU, это тривиально. Взяв 2-мерный пример, здесь приведены абсолютные координатные пары x, y для 5x5, скорректированные для нуля в середине:
┌───┬───┬───┬───┬───┐
│2 2│2 1│2 0│2 1│2 2│
├───┼───┼───┼───┼───┤
│1 2│1 1│1 0│1 1│1 2│
├───┼───┼───┼───┼───┤
│0 2│0 1│0 0│0 1│0 2│
├───┼───┼───┼───┼───┤
│1 2│1 1│1 0│1 1│1 2│
├───┼───┼───┼───┼───┤
│2 2│2 1│2 0│2 1│2 2│
└───┴───┴───┴───┴───┘
Добавление пар в каждой ячейке дает нам Манхэттенские расстояния:
4 3 2 3 4
3 2 1 2 3
2 1 0 1 2
3 2 1 2 3
4 3 2 3 4
В то же время у нас может быть система индексирования (это, однако, слабость в вопросе, так как она не имеет состояний, адресующих пробелы):
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
Мы можем сгладить оба расстояния:
dist = 4 3 2 3 4 3 2 1 2 3 2 1 0 1 2 3 2 1 2 3 4 3 2 3 4
и индексы
index = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Уникальные манхэттенские расстояния для массива N (или N * N или N * N * N) все числа между 1 и N-1, предшествующие 0, если N нечетно. Для матрицы 5 * 5:
0 1 2 3 4
Пройдите через каждое расстояние и посмотрите, где это расстояние равно "dist". Для 5 * 5:
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 // dist = 0 at locations 13
0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 // dist = 1 at locations 8 12 14 18
0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 // dist = 2 at locations 3 7 9 11 15 17 19 23
0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 // dist = 3 at locations 2 4 6 10 16 20 22 24
1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 // dist = 4 at locations 1 5 21 25
и создайте массив на основе этих местоположений. То есть. иметь массив ampty, добавить 13 к нему в качестве первого элемента, затем добавить 8 12 14 18 и т.д. В конечном итоге результат будет
13 8 12 14 18 3 7 9 11 15 17 19 23 2 4 6 10 16 20 22 24 1 5 21 25
Это желаемый порядок sord. Просто переустановить это, например, на двумерное адресное пространство, используя деление, мин и вычет.
Однако этот способ вычисления НЕОБХОДИМО НА GPU. Для этого требуется конкретный порядок выполнения, а у нас нет на графическом процессоре.
При решении порядка обхода на графическом процессоре решение должно быть
lookupcoordinates = fn (currentposition)
Возможно, можно описать fn, но вопрос слишком неполный - требуется гораздо больше деталей, чем просто говорить "на GPU". Как описывается 3d-массив? В какой памяти он находится? Каков результат адресного пространства? И т.д.
Я был бы рад услышать более подробную информацию об этом, а также поправки к тому, что я пишу выше.
Добавление для обсуждения с пользователем m69
Одна (второстепенная) мысль выполняет вычисления в шагах [число измерений], где скопление из предыдущего измерения будет использоваться для следующего, вплоть до, например, 3. Возможно, численное поведение было бы полезно в таких случай.
Если взглянуть ближе на основы, можно было бы предположить линейное целевое пространство, так что это простой вектор индексирования от 1 до [числа ячеек], где, например, куб 10 * 10 * 10 имел бы линейный 1D из 1000 индексов, от 1 до 1000. В дальнейшем можно повторно перефразировать эти индексы в квадратный или более размерный формат.
В одномерном случае предположим, что у нас есть 9-элементный "куб" (тот же, что и 9 * 1 * 1, если он выражен трехмерно). Будет ниже
x x x x x x x x x // Data
1 2 3 4 5 6 7 8 9 // Indexes
4 3 2 1 0 1 2 3 4 // Manhattan distances
5 4 6 3 7 2 8 1 9 // Pick order, starting from center
Следовательно, нам нужен fnкоторый отображается ниже
┌──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐
│1 to 5│2 to 4│3 to 6│4 to 3│5 to 7│6 to 2│7 to 8│8 to 1│9 to 9│
└──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┘
Теперь, если, например, посмотрите на индекс 4 результата, fn должен иметь возможность независимо от любого другого индекса разрешить результат = 3, т.е. fn (4) = 3. Должно быть возможно описать fn. Сначала можно сделать вывод, что "4" находится в слое 2 (если слой 0 является самым внутренним). После этого должно быть возможно сделать вывод о том, как имеет место слой 2-й клетки (все слои имеют 2 ячейки) и, наконец, является ли эта ячейка первым или вторым событием/элементом слоя 2. Это разрешится на 3, т.е. для результата [4] мы выбираем данные [3].
Теперь, если предположить двумерный "куб" размера 11 * 11 (* 1), мы имеем следующую ситуацию:
0 1 2 3 4 5 6 7 8 9 10 // Unique Manhattan distances
1 4 8 12 16 20 20 16 12 8 4 // How many cells in each distance-layer?
Отметим, что "сколько" довольно симметрично и даже более симметрично для 10 * 10:
1 2 3 4 5 6 7 8 9 // Unique Manhattan distances
4 8 12 16 20 16 12 8 4 // How many cells in each distance-layer?
4 12 24 40 60 76 88 96 100 // Cumulative sum of "How many..."
Обратите внимание на "совокупную сумму"! Используя это, если мы принимаем решение, например index = 55 (может произойти в любое время, до или после 54, помните!), Мы можем заключить, что в настоящее время мы нацелены на уровень 5, который содержит 20 элементов, с индексом = 40... 60.
Этот слой начинается с 40, а теперь мы находимся на 55. Разница равна 15. Может быть, можно описать offset (x, y) -координаты от "уровня 5-начала x, y), используя это" 15"? Я предполагаю, что мы просто входим в четвертый квадрант.
То же самое для 3D?
