現在、複数の次元をサポートするツリーを (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 のケースで行ったハードコードされたテストの一部です。
#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 ケースに関する提案はありますか?
注: 上記のスニペットが最適な実装ではないことはわかっています。すべてを理解して最適化するまでは、ハードコーディングされたケースです。