Координаты с несколькими измерениями

Question

В настоящее время я создаю дерево (используя Python), которое будет поддерживать несколько измерений, но, как начало, я сначала пытаюсь понять 2D-часть. Каждый узел в двумерном дереве будет содержать координаты квадрата, который он представляет, и содержащуюся в нем точку данных. 2D-случай представляет QuadTree - https://en.wikipedia.org/wiki/Quadtree. Меня интересует только создание координат.

Корень будет содержать [(0,1), (0,1)] для координат. Раз разбивая квадрат, мы получаем 2^n квадратов для каждого узла (n = число измерений, 2 в этом случае). Если корень содержит [(0,1), (0,1)], первый уровень будет содержать:

Node1: [(0,0.5),(0,0.5)] 
Node2: [(0.5,1),(0,0.5)] 
Node3: [(0,0.5),(0.5,1)] 
Node4: [(0.5,1),(0.5,1)] 

Мне интересно, как реализовать вычисление координат таким образом, что это приводит к множеству кортежей снова , Я столкнулся с Itertools, у которого есть метод комбинаций, но я не совсем уверен, как снова восстановить набор кортежей, так что никакие координаты не равны друг другу, т. Е. У нас нет (0,5,0,5). Какие-либо предложения?

Вот некоторые жёстки тестирования я сделал для 6D случая:

#initial root coordinates 
H = [(0,1), (0,1), (0,1), (0,1), (0,1), (0,1)] 

#get all the coordinates separately 
N = [(H[0][0]+H[0][1])/2, H[0][1], (H[1][0]+H[1][1])/2, H[1][1], 
    (H[2][0]+H[2][1])/2, H[2][1], (H[3][0]+H[3][1])/2, H[3][1], 
    (H[3][0]+H[3][1])/2, H[4][1], (H[5][0]+H[5][1])/2, H[5][1]] 

#will print 924 
print(len(list(itr.combinations(N,6)))) 

#make a new list of the previous coordinates but divide them by 2 
N2 = [N[0]/2, N[1]/2, N[2]/2, N[3]/2, N[4]/2, N[5]/2, 
     N[6]/2, N[7]/2, N[8]/2, N[9]/2, N[10]/2, N[11]/2] 

N2_comb = list(itr.combinations(N2,6)) 

#find duplicates and remove them 
for each in N2_comb: 
    if (each[0] == each[1] or each[1] == each[2] or each[2] == each[3] or 
    each[3] == each[4] or each[4] == each[5]): 
     N2_comb.remove(each) 

#print 488 
print(len(N2_comb)) 

Для случая 6D мне нужен 64 узлов/родитель так 488 координаты достаточно. Просто я не знаю, правильно ли это, и не знаю, как реализовать кортежи с этого момента. Любые предложения для случая 2D и/или 6D?

Примечание: Я знаю, что приведенный выше фрагмент не является наилучшей реализацией; это жестко закодированный случай, пока я не пойму все, а затем оптимизирую.

Answer 1

itertools не работает так, как я думаю, вы хотите: поддиапазон действителен только для измерения, на котором он был вычислен. Чтобы упростить типизацию, я рассмотрю квадрат над (0,8) вместо (0,1). На первом расколе мы получаем четыре квадрата; давайте посмотрим на (0,4), (4,8). Теперь мы хотим разделить это при х = 2 и у = 6, что дает

(0, 2), (4, 6) 
(0, 2), (6, 8) 
(2, 4), (4, 6) 
(2, 4), (6, 8) 

Однако вашей комбинации можно найти только все координаты для пространства с тем же стартовым диапазоном во всех измерениях, так как он не различает размеры. В приведенном выше случае, было бы также генерировать

(0, 6), (2, 4) 

Если все, что вы пытаетесь сделать, это генерировать все возможности сразу, это будет охватывать поле. Однако структура дерева теряется.

---

Я думаю, что это может быть то, что вы хотите, по своей сути: все комбинации происходят в «четырехъядерный» раскол (2^N раздельным) ваши данные координат диапазонов. Для иллюстрации я остался с вашим 6D-корпусом, но выбрал расширенные диапазоны размера 2 с различным диапазоном для каждого измерения - как если бы мы уже сделали несколько разделов, и мы просто работаем над одной из 6-кубических гиперкубов на момент.

Этот код сначала разбивает начальные координаты пополам, сохраняя два новых интервала в кортеже (пара). Затем мы применяем itertools.product к списку пар, давая все комбинации нижнего/верхнего интервала для каждого из 6 измерений.

import itertools as itr 

#initial root coordinates 
H = [(10.0,12.0), (8.0,10.0), (6.0,8.0), (4.0,6.0), (2.0,4.0), (0.0,2.0)] 

#get all the coordinates separately 
choice = [] 
for coord in H: 
    low = coord[0] 
    top = coord[1] 
    mid = (low+top)/2 
    choice.append(((low, mid), (mid, top))) 

print "choice list:", choice 

#will print 924 
quad_split = list(itr.product(*choice)) 
print len(quad_split) 

Выход:

choice list: [((10.0, 11.0), (11.0, 12.0)), ((8.0, 9.0), (9.0, 10.0)), ((6.0, 7.0), (7.0, 8.0)), ((4.0, 5.0), (5.0, 6.0)), ((2.0, 3.0), (3.0, 4.0)), ((0.0, 1.0), (1.0, 2.0))] 
64 half-sized hypercubes: 
((10.0, 11.0), (8.0, 9.0), (6.0, 7.0), (4.0, 5.0), (2.0, 3.0), (0.0, 1.0)) 
((10.0, 11.0), (8.0, 9.0), (6.0, 7.0), (4.0, 5.0), (2.0, 3.0), (1.0, 2.0)) 
((10.0, 11.0), (8.0, 9.0), (6.0, 7.0), (4.0, 5.0), (3.0, 4.0), (0.0, 1.0)) 
((10.0, 11.0), (8.0, 9.0), (6.0, 7.0), (4.0, 5.0), (3.0, 4.0), (1.0, 2.0)) 
((10.0, 11.0), (8.0, 9.0), (6.0, 7.0), (5.0, 6.0), (2.0, 3.0), (0.0, 1.0)) 
((10.0, 11.0), (8.0, 9.0), (6.0, 7.0), (5.0, 6.0), (2.0, 3.0), (1.0, 2.0)) 
((10.0, 11.0), (8.0, 9.0), (6.0, 7.0), (5.0, 6.0), (3.0, 4.0), (0.0, 1.0)) 
((10.0, 11.0), (8.0, 9.0), (6.0, 7.0), (5.0, 6.0), (3.0, 4.0), (1.0, 2.0)) 
((10.0, 11.0), (8.0, 9.0), (7.0, 8.0), (4.0, 5.0), (2.0, 3.0), (0.0, 1.0)) 
((10.0, 11.0), (8.0, 9.0), (7.0, 8.0), (4.0, 5.0), (2.0, 3.0), (1.0, 2.0)) 
((10.0, 11.0), (8.0, 9.0), (7.0, 8.0), (4.0, 5.0), (3.0, 4.0), (0.0, 1.0)) 
((10.0, 11.0), (8.0, 9.0), (7.0, 8.0), (4.0, 5.0), (3.0, 4.0), (1.0, 2.0)) 
((10.0, 11.0), (8.0, 9.0), (7.0, 8.0), (5.0, 6.0), (2.0, 3.0), (0.0, 1.0)) 
((10.0, 11.0), (8.0, 9.0), (7.0, 8.0), (5.0, 6.0), (2.0, 3.0), (1.0, 2.0)) 
((10.0, 11.0), (8.0, 9.0), (7.0, 8.0), (5.0, 6.0), (3.0, 4.0), (0.0, 1.0)) 
((10.0, 11.0), (8.0, 9.0), (7.0, 8.0), (5.0, 6.0), (3.0, 4.0), (1.0, 2.0)) 
((10.0, 11.0), (9.0, 10.0), (6.0, 7.0), (4.0, 5.0), (2.0, 3.0), (0.0, 1.0)) 
((10.0, 11.0), (9.0, 10.0), (6.0, 7.0), (4.0, 5.0), (2.0, 3.0), (1.0, 2.0)) 
((10.0, 11.0), (9.0, 10.0), (6.0, 7.0), (4.0, 5.0), (3.0, 4.0), (0.0, 1.0)) 
((10.0, 11.0), (9.0, 10.0), (6.0, 7.0), (4.0, 5.0), (3.0, 4.0), (1.0, 2.0)) 
((10.0, 11.0), (9.0, 10.0), (6.0, 7.0), (5.0, 6.0), (2.0, 3.0), (0.0, 1.0)) 
((10.0, 11.0), (9.0, 10.0), (6.0, 7.0), (5.0, 6.0), (2.0, 3.0), (1.0, 2.0)) 
((10.0, 11.0), (9.0, 10.0), (6.0, 7.0), (5.0, 6.0), (3.0, 4.0), (0.0, 1.0)) 
((10.0, 11.0), (9.0, 10.0), (6.0, 7.0), (5.0, 6.0), (3.0, 4.0), (1.0, 2.0)) 
((10.0, 11.0), (9.0, 10.0), (7.0, 8.0), (4.0, 5.0), (2.0, 3.0), (0.0, 1.0)) 
((10.0, 11.0), (9.0, 10.0), (7.0, 8.0), (4.0, 5.0), (2.0, 3.0), (1.0, 2.0)) 
((10.0, 11.0), (9.0, 10.0), (7.0, 8.0), (4.0, 5.0), (3.0, 4.0), (0.0, 1.0)) 
((10.0, 11.0), (9.0, 10.0), (7.0, 8.0), (4.0, 5.0), (3.0, 4.0), (1.0, 2.0)) 
((10.0, 11.0), (9.0, 10.0), (7.0, 8.0), (5.0, 6.0), (2.0, 3.0), (0.0, 1.0)) 
((10.0, 11.0), (9.0, 10.0), (7.0, 8.0), (5.0, 6.0), (2.0, 3.0), (1.0, 2.0)) 
((10.0, 11.0), (9.0, 10.0), (7.0, 8.0), (5.0, 6.0), (3.0, 4.0), (0.0, 1.0)) 
((10.0, 11.0), (9.0, 10.0), (7.0, 8.0), (5.0, 6.0), (3.0, 4.0), (1.0, 2.0)) 
((11.0, 12.0), (8.0, 9.0), (6.0, 7.0), (4.0, 5.0), (2.0, 3.0), (0.0, 1.0)) 
((11.0, 12.0), (8.0, 9.0), (6.0, 7.0), (4.0, 5.0), (2.0, 3.0), (1.0, 2.0)) 
((11.0, 12.0), (8.0, 9.0), (6.0, 7.0), (4.0, 5.0), (3.0, 4.0), (0.0, 1.0)) 
((11.0, 12.0), (8.0, 9.0), (6.0, 7.0), (4.0, 5.0), (3.0, 4.0), (1.0, 2.0)) 
((11.0, 12.0), (8.0, 9.0), (6.0, 7.0), (5.0, 6.0), (2.0, 3.0), (0.0, 1.0)) 
((11.0, 12.0), (8.0, 9.0), (6.0, 7.0), (5.0, 6.0), (2.0, 3.0), (1.0, 2.0)) 
((11.0, 12.0), (8.0, 9.0), (6.0, 7.0), (5.0, 6.0), (3.0, 4.0), (0.0, 1.0)) 
((11.0, 12.0), (8.0, 9.0), (6.0, 7.0), (5.0, 6.0), (3.0, 4.0), (1.0, 2.0)) 
((11.0, 12.0), (8.0, 9.0), (7.0, 8.0), (4.0, 5.0), (2.0, 3.0), (0.0, 1.0)) 
((11.0, 12.0), (8.0, 9.0), (7.0, 8.0), (4.0, 5.0), (2.0, 3.0), (1.0, 2.0)) 
((11.0, 12.0), (8.0, 9.0), (7.0, 8.0), (4.0, 5.0), (3.0, 4.0), (0.0, 1.0)) 
((11.0, 12.0), (8.0, 9.0), (7.0, 8.0), (4.0, 5.0), (3.0, 4.0), (1.0, 2.0)) 
((11.0, 12.0), (8.0, 9.0), (7.0, 8.0), (5.0, 6.0), (2.0, 3.0), (0.0, 1.0)) 
((11.0, 12.0), (8.0, 9.0), (7.0, 8.0), (5.0, 6.0), (2.0, 3.0), (1.0, 2.0)) 
((11.0, 12.0), (8.0, 9.0), (7.0, 8.0), (5.0, 6.0), (3.0, 4.0), (0.0, 1.0)) 
((11.0, 12.0), (8.0, 9.0), (7.0, 8.0), (5.0, 6.0), (3.0, 4.0), (1.0, 2.0)) 
((11.0, 12.0), (9.0, 10.0), (6.0, 7.0), (4.0, 5.0), (2.0, 3.0), (0.0, 1.0)) 
((11.0, 12.0), (9.0, 10.0), (6.0, 7.0), (4.0, 5.0), (2.0, 3.0), (1.0, 2.0)) 
((11.0, 12.0), (9.0, 10.0), (6.0, 7.0), (4.0, 5.0), (3.0, 4.0), (0.0, 1.0)) 
((11.0, 12.0), (9.0, 10.0), (6.0, 7.0), (4.0, 5.0), (3.0, 4.0), (1.0, 2.0)) 
((11.0, 12.0), (9.0, 10.0), (6.0, 7.0), (5.0, 6.0), (2.0, 3.0), (0.0, 1.0)) 
((11.0, 12.0), (9.0, 10.0), (6.0, 7.0), (5.0, 6.0), (2.0, 3.0), (1.0, 2.0)) 
((11.0, 12.0), (9.0, 10.0), (6.0, 7.0), (5.0, 6.0), (3.0, 4.0), (0.0, 1.0)) 
((11.0, 12.0), (9.0, 10.0), (6.0, 7.0), (5.0, 6.0), (3.0, 4.0), (1.0, 2.0)) 
((11.0, 12.0), (9.0, 10.0), (7.0, 8.0), (4.0, 5.0), (2.0, 3.0), (0.0, 1.0)) 
((11.0, 12.0), (9.0, 10.0), (7.0, 8.0), (4.0, 5.0), (2.0, 3.0), (1.0, 2.0)) 
((11.0, 12.0), (9.0, 10.0), (7.0, 8.0), (4.0, 5.0), (3.0, 4.0), (0.0, 1.0)) 
((11.0, 12.0), (9.0, 10.0), (7.0, 8.0), (4.0, 5.0), (3.0, 4.0), (1.0, 2.0)) 
((11.0, 12.0), (9.0, 10.0), (7.0, 8.0), (5.0, 6.0), (2.0, 3.0), (0.0, 1.0)) 
((11.0, 12.0), (9.0, 10.0), (7.0, 8.0), (5.0, 6.0), (2.0, 3.0), (1.0, 2.0)) 
((11.0, 12.0), (9.0, 10.0), (7.0, 8.0), (5.0, 6.0), (3.0, 4.0), (0.0, 1.0)) 
((11.0, 12.0), (9.0, 10.0), (7.0, 8.0), (5.0, 6.0), (3.0, 4.0), (1.0, 2.0))