Coordonnées en plusieurs dimensions

Je suis en train de construire un arbre (en utilisant Python) qui supportera plusieurs dimensions mais, pour commencer, j'essaie de comprendre la partie 2D en premier. Chaque nœud de l'arborescence 2D contiendra les coordonnées du carré qu'il représente et un point de données qu'il contient. Le cas 2D représente un QuadTree - https://en.wikipedia.org/wiki/Quadtree. Je suis seulement intéressé à construire les coordonnées maintenant.Coordonnées en plusieurs dimensions

La racine contiendra [(0,1), (0,1)] pour les coordonnées. Une fois que nous avons divisé le carré, nous obtenons 2^n carrés pour chaque nœud (n = nombre de dimensions, 2 dans ce cas). Si la racine contient [(0,1), (0,1)], le premier niveau contiendra:

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

Je me demande comment mettre en œuvre le calcul des coordonnées de telle sorte qu'il en résulte un ensemble de tuples à nouveau . Je suis tombé sur Itertools qui a une méthode de combinaisons mais je ne suis pas tout à fait sûr de reconstruire l'ensemble des tuples de telle sorte qu'aucune coordonnée ne soit égale à l'autre, c'est-à-dire que nous n'en avons pas (0.5.0.5). Aucune suggestion?

Voici quelques tests hardcoded je l'ai fait pour le cas 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))

Pour le cas 6D j'ai besoin 64 noeuds/parent donc 488 coordonnées suffit. C'est juste que je ne sais pas si c'est la bonne approche et je ne sais pas comment implémenter les tuples à partir de ce point. Des suggestions pour le cas 2D et/ou 6D?

Note: Je sais que l'extrait ci-dessus n'est pas la meilleure implémentation; c'est un cas codé jusqu'à ce que je comprenne tout et optimise ensuite.

Source

2016-06-22 vFlav

Pouvez-vous expliquer la signification des parties d'un noeud (par exemple'Node2: [(0.5,1), (0,0.5)] ')? Je m'attendrais à quelque chose comme'Node: (x, y, level) 'et je ne comprends pas pourquoi chaque noeud a quatre composants dans votre exemple. – Felix

Ces coordonnées représentent la plage du carré dans chaque dimension. – Prune

Comme @Prune mentionné, ce sont les plages des carrés pour chaque dimension. En ce moment, je suis préoccupé par la construction des coordonnées. Le niveau est stocké dans un champ différent et fait partie de l'implémentation Tree - un sujet différent. Je vais utiliser les plages de carrés pour vérifier si un point de données est contenu dans ce carré. Si nous avons plusieurs points de données dans le carré, nous divisons à nouveau le carré en 4 petits carrés; C'est quand il devient un peu brouillon avec les coordonnées. – vFlav

Le itertools ne fonctionne pas comme je le souhaite: la sous-plage n'est valide que pour la dimension sur laquelle elle a été calculée. Pour simplifier un peu la saisie, je vais considérer un carré au-dessus de (0,8) au lieu de (0,1). Sur la première division, nous obtenons quatre carrés; regardons (0,4), (4,8). Nous voulons maintenant diviser cela à x = 2 et y = 6, donnant

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

Cependant, vos combinaisons ne peut trouver tous les coordonnées d'un espace avec la même gamme de départ dans toutes les dimensions, depuis il ne différencie pas les dimensions. Dans le cas ci-dessus, il serait également générer

(0, 6), (2, 4)

Si tout ce que vous essayez de faire est de générer toutes les possibilités à la fois, cela couvrira le terrain. Cependant, la structure de l'arbre est perdue.

Je pense que cela pourrait être ce que vous voulez, à sa base: toutes les combinaisons d'entrer dans une division « quad » (2^N split) de vos coordonnées données plages. Par exemple, je suis resté avec votre cas 6D, mais j'ai choisi des plages étendues de taille 2, avec une gamme différente pour chaque dimension - comme si nous avions déjà fait plusieurs splits, et nous travaillons simplement sur l'un des hypercubes 6D à le moment. Ce code sépare d'abord les coordonnées initiales en deux, en conservant les deux nouveaux intervalles dans une paire (paire). Ensuite, nous appliquons itertools.product à la liste des paires, donnant toutes les combinaisons d'intervalle inférieur/supérieur pour chacune des 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)

Sortie:

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

Source

2016-06-22 16:08:40 Prune

Je comprends ce que vous dites, mais si chaque noeud contient ses coordonnées alors que je peux avoir une fonction: 'def __get_coordinates __ (self): coords = self.hypercube new_coordinates = ' Le La fonction devrait savoir qu'elle devrait utiliser les coordonnées stockées dans le nœud actuel. – vFlav

Bien sûr - mais itertools.combinations n'est pas ce dont vous avez besoin pour cela. Lors de ma prochaine pause, je vais essayer de rattraper quelque chose qui fonctionne pour vous. – Prune

J'ai aussi essayé différentes méthodes d'itertools mais aucune n'a donné le résultat escompté. Merci de votre aide. J'y reviendrai plus en profondeur d'ici là. – vFlav

Coordonnées en plusieurs dimensions

Répondre

Questions connexes