0

我目前正在构建一个支持多维的树（使用 Python），但首先，我试图先了解 2D 部分。2D 树中的每个节点都将包含它所代表的正方形的坐标和其中包含的一个数据点。2D 案例代表四叉树 - 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 机箱有什么建议吗？

注意：我知道上面的代码片段不是最好的实现；在我了解所有内容然后进行优化之前，这是一个硬编码案例。

4

1 回答 1

1

itertools不能按照我认为您想要的方式工作：子范围仅对计算它的维度有效。为了稍微简化输入，我将考虑使用 (0,8) 上的正方形而不是 (0,1)。在第一次拆分时，我们得到四个正方形；让我们看看（0,4），（4,8）。我们现在想在 x=2 和 y=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 的扩展范围，每个维度的范围不同 - 好像我们已经进行了几次拆分，我们只是在处理其中一个 6D 超立方体此时此刻。

此代码首先将初始坐标分成两半，将两个新区间保持在一个元组（对）中。然后我们将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))
于 2016-06-22T16:08:40.460 回答