複数次元の座標

Question

私は現在、複数の次元をサポートするツリー（Pythonを使用しています）を構築していますが、始めに2Dの部分を理解しようとしています。 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のケースのために行っているいくつかのハードコードされたテストです：私は488点の座標64個のノード/親を必要と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)) 

十分です。これが正しいアプローチであるかどうかわからず、この時点からタプルを実装する方法はわかりません。 2Dおよび/または6Dの場合の提案はありますか？

注：上記のスニペットは最適な実装ではありません。私はすべてを理解してから最適化するまで、ハードコードされたケースです。

Answer 1

itertoolsは、私が望んだと思うようには機能しません。サブレンジは、計算されたディメンションに対してのみ有効です。入力を簡単にするために、（0,1）の代わりに（0,8）の四角形を考えるつもりです。最初の分割では、4つの正方形が得られます。 （0,4）、（4,8）を見てみましょう。私たちは今、しかし、あなたの組み合わせだけ以来、すべての次元で同じ開始範囲とスペースのためすべて座標を見つけることができます

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

を与え、X = 2とy = 6でこれを分割したいですそれは次元を区別しない。あなたがやろうとしているすべてが一度にすべての可能性を生成することである場合上記の場合、それはまた、

(0, 6), (2, 4) 

を生成し、これはフィールドをカバーします。ただし、ツリー構造は失われます。

---

は、私は、これはあなたがその中核に、何をしたいかもしれないと思う：すべての組み合わせは、あなたの与えられた座標範囲の「クワッド」スプリット（2^N分割）に入ります。説明のために、私はあなたの6Dのケースにとどまっていましたが、サイズ2の拡張範囲を選択しました。各ディメンションの範囲が異なります。すでに複数の分割を行っていたかのように、6Dハイパーキューブ瞬間。

このコードは最初に、最初の座標を半分に分割し、2つの新しい間隔をタプル（ペア）に保持します。次に、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))