Multiple dimensions coordinates

Question

I am currently building a tree (using Python) that will support multiple dimensions but, as a start, I am trying to understand the 2D part first. Each node in the 2D tree will contain the coordinates of the square it represents and a data point contained within it. The 2D case represents a QuadTree - https://en.wikipedia.org/wiki/Quadtree. I am only interested in building the coordinates now.

The root will contain [(0,1), (0,1)] for the coordinates. Once we split the square, we get 2^n squares for every node (n = number of dimensions; 2 in this case). If the root contains [(0,1),(0,1)], the first level will contain:

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)]

I am wondering how to implement the coordinates calculation such that it results in a set of tuples again. I came across Itertools that has a combinations method but I am not entirely sure how to rebuild the set of tuples again such that no coordinates are equal to each other i.e. we do not have (0.5,0.5). Any suggestions?

Here is some hardcoded testing I have done for the 6D case:

#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))

For the 6D case I need 64 nodes/parent so 488 coordinates is enough. It's just that I do not know if this is the right approach and do not know how to implement the tuples from this point. Any suggestions for the 2D and/or 6D case?

Note: I know the above snippet is not the best implementation; it is a hardcoded case until I understand everything and then optimize.

• Felix: Can you explain the meaning of the parts of one node (e.g. ´Node2: [(0.5,1),(0,0.5)]`)? I would expect something like ´Node: (x, y, level)´ and I don't understand why each node has four components in your example.
• Prune: Those coordinates are the square's range in each dimension.
• vFlav: Like @Prune mentioned, those are the squares' ranges for each dimension. Right now I am concerned with building the coordinates. The level is stored in a different field and is part of the Tree implementation - a different topic. I will use the squares ranges to check if a data point is contained within that square. If we have multiple data points within the square, we divide the square again, into 4 smaller squares; this is when it gets a bit messy with the coordinates.

Answer 1

The itertools doesn't work the way I think you want: the subrange is valid only for the dimension on which it was computed. To simplify the typing a little, I'm going to consider a square over (0,8) instead of (0,1). On the first split, we get four squares; let's look at (0,4), (4,8). We now want to divide this at x=2 and y=6, giving

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

However, your combinations can only find all the coordinates for a space with the same starting range in all dimensions, since it doesn't differentiate the dimensions. In the above case, it would also generate

(0, 6), (2, 4)

If all you're trying to do is to generate all possibilities at once, this will cover the field. However, the tree structure is lost.

---

I think this might be what you want, at its core: all the combinations going into a "quad" split (2^N split) of your given coordinate ranges. For illustration, I stayed with your 6D case, but chose expanded ranges of size 2, with a different range for each dimension -- as if we'd already done several splits, and we're simply working on one of the 6D hypercubes at the moment.

This code first splits the initial coordinates in half, keeping the two new intervals in a tuple (pair). Then we apply itertools.product to the list of pairs, yielding all combinations of lower/upper interval for each of the 6 dimensions.

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)

Output:

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))

• vFlav: I understand what you're saying but if each node contains its coordinates then I can have a function: def __get_coordinates__(self): coords = self.hypercube new_coordinates = <the answer to my problem> The function would know that it should use the coordinates stored in the current node.
• Prune: Sure -- but itertools.combinations isn't what you need for that. On my next break, I'll try to swot up something that works for you.
• vFlav: I've also tried different methods from itertools but none of them gave the desired result. Thank you for your help. I will look into it more in-depth in the meantime.
• vFlav: That works perfectly! Thank you! That's precisely what I was looking for. I manually tested for 2D and 3D (by drawing graphs and cubes) and the result is exactly as expected.
• Prune: Great! Glad to be of help.