Python, разделяющий N-мерный том на однородные субтомы

Question

У меня есть объект, занимающий нижележащую N-мерную квадратную сетку (представленную массивом), так что занято только 25% точек сетки.Каждый 1x1x1x ... N-куб (т. Е. Гиперкуб) в этой сетке содержит одинаковое количество этого объекта (расположенного только в некоторых вершинах этого гиперкуба).У меня есть массив координат всех занятых точек сетки.Задача состоит в том, чтобы циклически проходить через этот массив и извлекать занятые координаты для каждого гиперкуба 1x1x1 ... и сохранять их в новом массиве для дальнейшей обработки.

Ситуацию лучше всего объяснить на примере.Рассмотрим трехмерный случай, когда базовая сетка была выбрана так, чтобы 1<=i,j,k<=4 давал массив двумерных пустышек: A = [[1 1 1] [1 2 1] [1 3 1] [1 4 1] [2 1 1] [2 2 1] [2 3 1] [2 4 1] [3 1 1] [3 2 1] [3 3 1] [3 4 1] [4 1 1] [4 2 1] [4 3 1] [4 4 1] [1 1 2] [1 2 2] [1 3 2] [1 4 2] [2 1 2] [2 2 2] [2 3 2] [2 4 2] [3 1 2] [3 2 2] [3 3 2] [3 4 2] [4 1 2] [4 2 2] [4 3 2] [4 4 2] [1 1 3] [1 2 3] [1 3 3] [1 4 3] [2 1 3] [2 2 3] [2 3 3] [2 4 3] [3 1 3] [3 2 3] [3 3 3] [3 4 3] [4 1 3] [4 2 3] [4 3 3] [4 4 3] [1 1 4] [1 2 4] [1 3 4] [1 4 4] [2 1 4] [2 2 4] [2 3 4] [2 4 4] [3 1 4] [3 2 4] [3 3 4] [3 4 4] [4 1 4] [4 2 4] [4 3 4] [4 4 4]]

Пример массива 2d numpy, который мне нужно обработать в этом случае: B = [[1,1,1], [1,2,1], [1,3,1], [1,4,1], [2,2,1], [2,3,1], [2,4,1], [3,2,1], [3,3,1],[3,4,1], [4,1,1], [4,3,1], [1,1,2], [1,4,2], [2,1,2], [2, 2,2], [2,4,2], [3,1,2], [3,2,2], [3,4,2], [4,1,2], [4,2, 2], [4,3,2], [4,4,2], [1,1,3], [1,4,3], [2,1,3], [2,2,3], [2,3,3], [2,4,3], [3,1,3], [3,2,3], [3,3,3], [4,1,3],[4, 2,3], [4,3,3], [4,4,3], [1,2,4], [1,3,4], [1,4,4], [2,1, 4], [2,2,4], [2,3,4], [3,1,4], [3,2,4], [3,3,4], [4,3,4], [4,4,4]]

B - массив только занятых точек сетки.Перебирая B, я хотел бы получить занятые координаты, относящиеся к каждому из кубов базовой сетки.Края куба определяются как 1<=i,j,k<=2, (3<=i<=4) & (1<=j,k<=2) и т. Д. Например, для куба, обозначенного 1<=i,j,k<=2, я хотел бы извлечь массив [[1,1,1], [1,1,2], [1,2,1], [2,1,2], [2,2,1], [2,2,2]] из B и сохраните его вновый массив для дальнейшей обработки.Затем это повторяется до тех пор, пока не будут учтены все 8 кубов в этом примере.Обратите внимание, что сетки всегда выбираются так, чтобы этот тип разбиения всегда был возможен.Несмотря на то, что я могу выбрать сетки, чтобы быть четными, я не могу контролировать занятость объекта объектом.

Нарезка массивов не работает, потому что, как правило, точки сетки не являются непрерывными в B.Я попытался написать код с использованием циклов for для наложения диапазонов по краям кубов, но он слишком быстро усложнился и это не похоже на правильный подход.Тогда есть функция "numpy.where";но сложность условия делает его довольно сложным.Аналогичные проблемы возникают с «numpy.extract».

Answer 1

Если у вас есть сетка в виде ndim+1 -мерного массива координат, например,

a = np.stack(np.mgrid[1:5, 1:5], -1)

, тогда это просто вопрос разумного изменения формы и транспонирования:

import itertools as it

# dimensions for reshape:
# split all coordinate axes into groups of two, leave the
# "dimension subscript" axis alone     
chop = *it.chain.from_iterable((i//2, 2) for i in a.shape[:-1]),

# shuffle for transpose:
# regroup axes into coordinates then pairs then subscript
ax_shuf = *(1 ^ np.r_[1:4*a.ndim-3:2] % (2*a.ndim-1)), -1

# put it together and flatten, i.e. join coordinates and join pairs
a.reshape(*chop, -1).transpose(*ax_shuf).reshape(np.prod(chop[::2]), -1, a.shape[-1])

Результат:

array([[[1, 1],
        [1, 2],
        [2, 1],
        [2, 2]],

       [[1, 3],
        [1, 4],
        [2, 3],
        [2, 4]],

       [[3, 1],
        [3, 2],
        [4, 1],
        [4, 2]],

       [[3, 3],
        [3, 4],
        [4, 3],
        [4, 4]]])

Обновление

Если B - неупорядоченное подмножество полной сетки, вы можете выполнить следующий трюк:

1. вычтите минимум по столбцу, чтобы убедиться, что четность начинается с четного
2. деления этажа на 2, углы каждого интересующего куба свернутся в одну точку
3. , теперь используйте np.unique в строках, чтобыget goups

Примечание. При необходимости вы можете сделать это немного быстрее, заменив argsort в приведенном ниже коде одним из решений на Самый эффективный способ сортировки массива вкорзины, заданные индексным массивом? .

B = np.array(B)
unq, idx, cts = np.unique((B-B.min(0))//2, axis=0, return_inverse=True, return_counts=True)
if (cts[0]==cts).all():
    result = B[idx.argsort()].reshape(len(unq), cts[0], -1)
else:
    result = np.split(B[idx.argsort()], cts[:-1].cumsum())

Результат:

array([[[1, 1, 1],
        [1, 2, 1],
        [2, 2, 1],
        [2, 2, 2],
        [2, 1, 2],
        [1, 1, 2]],

       [[2, 2, 3],
        [2, 1, 3],
        [1, 1, 3],
        [2, 1, 4],
        [2, 2, 4],
        [1, 2, 4]],

       [[1, 4, 2],
        [2, 4, 2],
        [1, 3, 1],
        [1, 4, 1],
        [2, 3, 1],
        [2, 4, 1]],

       [[1, 4, 4],
        [1, 3, 4],
        [2, 4, 3],
        [2, 3, 3],
        [1, 4, 3],
        [2, 3, 4]],

       [[4, 1, 1],
        [4, 1, 2],
        [3, 2, 1],
        [3, 2, 2],
        [4, 2, 2],
        [3, 1, 2]],

       [[4, 2, 3],
        [3, 2, 4],
        [3, 1, 3],
        [3, 2, 3],
        [3, 1, 4],
        [4, 1, 3]],

       [[4, 4, 2],
        [4, 3, 2],
        [3, 4, 2],
        [4, 3, 1],
        [3, 4, 1],
        [3, 3, 1]],

       [[4, 3, 3],
        [3, 3, 3],
        [4, 3, 4],
        [3, 3, 4],
        [4, 4, 3],
        [4, 4, 4]]])