Python appliquer une grille sur des données 2D, enregistrer des cellules non vides dans l'arbre

Question

J'ai un ensemble de données de ~ 500 points en 2D, avec des coordonnées données (ce qui implique aussi que je peux me référer à chaque point avec un entier) (x, y) entre 0 et 10. Maintenant, j'essaie de diviser la zone en cellules carrées régulières en appliquant une grille. Notez que ce processus est répété dans un algorithme et qu'à un certain moment il y aura >>> 500 cellules carrées. Ce que je veux réaliser: Boucle sur tous les points, pour chaque point trouver la cellule carrée dans laquelle le point se trouve et enregistrer cette information.
Quelques étapes plus tard: Bouclez à nouveau tous les points, pour chaque point, identifiez sa cellule et les cellules adjacentes de la cellule. Prenez tous les points de ces cellules et ajoutez-les par ex. une liste, pour un usage ultérieur.

Mon processus de pensée: Comme il y aura beaucoup de cellules vides et que je ne veux pas perdre de mémoire pour eux, utilisez un arbre.
Exemple: Dans cell_39_41 et cell_39_42 est un point. Premier niveau: nœud racine avec enfant 39
Deuxième niveau: 39 noeuds avec des enfants 41,42
Troisième niveau: noeud 41 avec Point1 des enfants et 42 noeuds avec un enfant point2
Quatrième niveau: les noeuds représentant des points réels
Si Je trouve plus de points dans cell_39_41 ou cell_39_42 ils seront ajoutés en tant qu'enfants de leurs nœuds de troisième niveau respectifs.

class Node(object): 

def __init__(self, data): 
    self.data = data 
    self.children = [] 

def add_child(self, obj): 
    self.children.append(obj) 

J'ai omis une méthode non pertinente pour retourner des points dans une cellule. 1.Si j'ajoute un nœud de deuxième ou troisième niveau, je devrai me référer à lui pour pouvoir ajouter des enfants ou trouver des points dans une certaine cellule et ses cellules adjacentes. Cela signifie que je dois faire beaucoup de recherches linéaires coûteuses puisque les listes d'enfants ne sont pas triées.
2.Je vais ajouter des centaines de nœuds, mais je dois pouvoir y faire référence par des noms uniques. Cela peut être un grand échec personnel, mais je ne peux pas penser à un moyen de générer de tels noms dans une boucle.

Donc, fondamentalement, je suis assez sûr qu'il ya une erreur dans mon processus de pensée ou peut-être l'implémentation d'un arbre ne convient pas. J'ai lu beaucoup d'implémentation de b-trees ou similiar, mais puisque ce problème est limité à la 2D, j'ai senti qu'ils étaient juste trop et pas adapté.

Answer 1

utilisation dict de dicts comme arbre:

tree = { 
    '_data': 123, 
    'node1': { 
     '_data': 456, 
     'node11': { 
      'node111': {} 
     }, 
    'node2': { 
    } 
} 

recherche dans dicts sont rapides!

tree['node1']['node12']['node123']['_data'] = 123 # adding 

noms uniques:

shortcuts = {} 
shortcuts['name'] = tree['node1']['node11']['node111'] 
print shortcuts['name']['_data'] 

Answer 2

Que diriez-vous cela ... il

def add_point(data_dict, row, column, point): 
    # modifies source of data_dict in place, since dictionaries are mutable 
    data_dict.setdefault(row, {}).setdefault(column, []).append(point) 

def get_table(data): 
    out_dict = {} 
    for row, column, point in data: 
     add_point(out_dict, row, column, point) 
    return out_dict 


if __name__ == "__main__": 
    data = [(38, 41, 38411), (39, 41, 39411), (39, 42, 39421)] 
    points = get_table(data)  
    print points  
    add_point(points, 39, 42, 39422)  
    print points