Quadtree avec doublons

J'implémente un quadtree. Pour ceux qui ne connaissent pas cette structure de données, j'inclus la petite description suivante:

Un Quadtree est une structure de données et est dans le plan euclidien ce qu'est un Octree dans un espace tridimensionnel. L'indexation spatiale est une utilisation courante des quadtre.

Pour résumer leur fonctionnement, un quadtree est une collection - disons de rectangles ici - avec une capacité maximale et un cadre de délimitation initial. Lorsque vous essayez d'insérer un élément dans un quadtree qui a atteint sa capacité maximale, le quadtree est subdivisé en 4 quadtrees (dont une représentation géométrique aura une surface quatre fois plus petite que l'arbre avant l'insertion); chaque élément est redistribué dans les sous-arbres selon sa position, ie. la limite supérieure gauche lorsque vous travaillez avec des rectangles.

Ainsi, un quadtre est soit une feuille et a moins d'éléments que sa capacité, soit un arbre avec 4 quadruples enfants (généralement nord-ouest, nord-est, sud-ouest, sud-est).

Ma préoccupation est que si vous essayez d'ajouter des doublons, qu'il s'agisse du même élément plusieurs fois ou de plusieurs éléments différents avec la même position, les arbres quadruples ont un problème fondamental avec la gestion des bords.

Par exemple, si vous travaillez avec un quadtree d'une capacité de 1 et le rectangle d'unité comme boîte englobante:

[(0,0),(0,1),(1,1),(1,0)]

Et vous essayez d'insérer deux fois un rectangle dont la limite supérieure gauche est l'origine: (ou de même si vous essayez de l'insérer N + 1 fois dans un quadtree avec une capacité de N> 1)

quadtree->insert(0.0, 0.0, 0.1, 0.1)
quadtree->insert(0.0, 0.0, 0.1, 0.1)

Le premier insert ne sera pas un problème:

Mais alors le premier insert déclenchera une subdivision (car la capacité est de 1):

Les deux rectangles sont donc placés dans le même sous-arbre.

Là encore, les deux éléments arriveront dans le même quadtree et déclencheront une subdivision…

Et ainsi de suite, et ainsi de suite, la méthode de subdivision s'exécutera indéfiniment car (0, 0) sera toujours dans le même sous-arbre sur les quatre créés, ce qui signifie qu'un problème de récursion infini se produit.

Est-il possible d'avoir un quadtree avec des doublons? (Sinon, on peut l'implémenter comme a Set)

Comment résoudre ce problème sans rompre complètement l'architecture d'un quadtree?

Vous implémentez une structure de données, vous devez donc prendre des décisions d'implémentation.

À moins que le quadtree n'ait quelque chose de spécifique à dire sur l'unicité - et je ne suis pas conscient qu'il en soit ainsi - c'est une décision de mise en œuvre. Il est orthogonal à la définition d'un quadtree et vous pouvez choisir de le gérer comme vous le souhaitez. Le quadtree vous indique comment insérer et mettre à jour des clés, mais pas si elles doivent être uniques ou ce que vous pouvez attacher à chaque nœud.

Prendre des décisions de mise en œuvre ne réinvente pas la roue , du moins pas plus que d'écrire votre propre mise en œuvre en premier lieu.

À titre de comparaison, la bibliothèque standard C ++ propose un ensemble unique, un ensemble multiple non unique, une carte unique (essentiellement un ensemble de paires clé-valeur ordonnées et comparées uniquement par la clé) et une carte multiple non unique. Ils sont tous généralement implémentés en utilisant le même arbre rouge-noir et aucun ne casse l'architecture , simplement parce que la définition de l'arbre rouge-noir n'a rien à dire sur l'unicité des clés ou les types stockés dans les nœuds feuilles.

Enfin, si vous pensez qu'il y a des recherches à ce sujet, trouvez-les, puis nous pourrons en discuter. Il y a peut-être un invariant quadtree que j'ai négligé, ou une contrainte supplémentaire qui permet de meilleures performances.

Je pense qu'il y a une mauvaise compréhension ici.

Si je comprends bien, chaque nœud quadtree contient une valeur indexée par un point. En d'autres termes, il contient le triple (x, y, valeur).

Il contient également 4 pointeurs vers des nœuds enfants, qui peuvent être nuls. Il existe une relation algorithmique entre les clés et les liens enfants.

Vos inserts devraient ressembler à ceci.

quadtree->insert(0.0, 0.0, value1)
quadtree->insert(0.0, 0.0, value2)

La première insertion crée un nœud (parent) et y insère une valeur.

La deuxième insertion crée un nœud enfant, y établit un lien et y insère une valeur (qui peut être identique à la première valeur).

Le nœud enfant instancié dépend de l'algorithme. Si l'algorithme est sous la forme [x) et l'espace de coordonnées se situe dans la plage [0,1), alors chaque enfant s'étendra sur la plage [0,0,5) et le point sera placé dans l'enfant NW.

Je ne vois pas de récursion infinie.

La résolution commune que j'ai rencontrée (dans les problèmes de visualisation, pas dans les jeux) est d'abandonner l'un des points, en remplaçant toujours ou en ne remplaçant jamais.

Je suppose que le principal point en faveur est que c'est facile à faire.

Je suppose que vous indexez des éléments qui sont tous à peu près de la même taille, sinon la vie devient complexe, ou lente, ou les deux ……

Un nœud Quadtree n'a pas besoin d'avoir une capacité fixe. La capacité est utilisée pour

• Autoriser la taille fixe de chaque nœud d'arborescence en mémoire ou sur disque - non requis si le nœud d'arborescence contient un ensemble d'éléments de taille variable et que vous utilisez un système d'allocation d'espace qui s'adapte. (Par exemple, objets java / c # en mémoire.)
• Décidez quand diviser un nœud.
  • Vous pouvez simplement redéfinir la règle, de sorte qu'un nœud est divisé s'il contient plus de «n» éléments de district, où le district est défini en fonction de l'emplacement des éléments.
  • Ou utilisez un " élément composite ", donc s'il y a des éléments multipliés au même endroit, vous introduisez un nouvel élément qui contient une liste de ces éléments multipliés.

Lorsque vous rencontrez des problèmes d'indexation spatiale, je recommande en fait de commencer avec un hachage spatial ou mon préféré: la vieille grille simple.

... et comprendre ses faiblesses avant de passer à des structures arborescentes qui permettent des représentations clairsemées.

L'une des faiblesses évidentes est que vous pourriez gaspiller de la mémoire sur un grand nombre de cellules vides (bien qu'une grille décemment implémentée ne devrait pas nécessiter plus de 32 bits par cellule, sauf si vous avez réellement des milliards de nœuds à insérer). Un autre est que si vous avez des éléments de taille moyenne qui sont plus grands que la taille d'une cellule et couvrent souvent, disons, des dizaines de cellules, vous pouvez perdre beaucoup de mémoire en insérant ces éléments de taille moyenne dans beaucoup plus de cellules que l'idéal. De même, lorsque vous effectuez des requêtes spatiales, vous devrez peut-être vérifier plus de cellules, parfois beaucoup plus, que l'idéal.

Mais la seule chose à raffiner avec une grille pour la rendre aussi optimale que possible contre une certaine entrée est cell size, ce qui ne vous laisse pas trop de choses à penser et à tripoter, et c'est pourquoi c'est ma structure de données préférée. pour des problèmes d'indexation spatiale jusqu'à ce que je trouve des raisons de ne pas l'utiliser. C'est très simple à mettre en œuvre et ne vous oblige pas à jouer avec autre chose qu'une seule entrée d'exécution.

Vous pouvez tirer le meilleur parti d'une ancienne grille simple et j'ai en fait battu beaucoup d'implémentations d'arbres quadruples et kd utilisées dans les logiciels commerciaux en les remplaçant par une ancienne grille simple (bien qu'elles ne soient pas nécessairement les meilleures implémentées) , mais les auteurs ont passé beaucoup plus de temps que les 20 minutes que j'ai passées à concocter une grille). Voici une petite chose rapide que j'ai fouettée pour répondre à une question ailleurs en utilisant une grille de détection de collision (même pas vraiment optimisée, juste quelques heures de travail, et j'ai dû passer la plupart du temps à apprendre comment fonctionne le pathfinding pour répondre à la question et c'était aussi ma première implémentation de détection de collision de ce type):

Une autre faiblesse des grilles (mais ce sont des faiblesses générales pour de nombreuses structures d'indexation spatiale) est que si vous insérez beaucoup d'éléments coïncidents ou se chevauchant, comme de nombreux points avec la même position, ils vont être insérés dans la même cellule exacte (s ) et dégrader les performances lors de la traversée de cette cellule. De même, si vous insérez de nombreux éléments massifs qui sont bien, beaucoup plus grands que la taille des cellules, ils voudront être insérés dans une cargaison de cellules et utiliser beaucoup, beaucoup de mémoire et dégrader le temps requis pour les requêtes spatiales dans tous les domaines. .

Cependant, ces deux problèmes immédiats ci-dessus avec des éléments coïncidents et massifs sont en fait problématiques pour toutes les structures d'indexation spatiale. La vieille grille simple gère en fait ces cas pathologiques un peu mieux que beaucoup d'autres car elle ne veut au moins pas subdiviser les cellules de manière récursive encore et encore.

Lorsque vous commencez avec la grille et que vous vous dirigez vers quelque chose comme un arbre quadruple ou KD, le problème principal que vous souhaitez résoudre est le problème avec les éléments insérés dans trop de cellules, ayant trop de cellules, et / ou devoir vérifier trop de cellules avec ce type de représentation dense.

Mais si vous pensez à un quadruple arbre comme une optimisation sur une grillepour des cas d'utilisation spécifiques, il est alors utile de penser encore à l'idée d'une "taille de cellule minimale", pour limiter la profondeur de la subdivision récursive des nœuds à quatre arbres. Lorsque vous faites cela, le pire des scénarios du quad-arbre se dégradera toujours en une grille dense au niveau des feuilles, seulement moins efficace que la grille, car il faudra du temps logarithmique pour passer de la racine à la cellule de la grille au lieu de à temps constant. Pourtant, penser à cette taille de cellule minimale évitera le scénario de boucle / récursion infinie. Pour les éléments massifs, il existe également des variantes alternatives comme des arbres quadruples lâches qui ne se divisent pas nécessairement également et pourraient avoir des AABB pour les nœuds enfants qui se chevauchent. Les BVH sont également intéressants en tant que structures d'indexation spatiale qui ne subdivisent pas également leurs nœuds. Pour les éléments coïncidents contre les structures arborescentes, l'essentiel est d'imposer simplement une limite à la subdivision (ou, comme d'autres l'ont suggéré, il suffit de les rejeter ou de trouver un moyen de les traiter comme s'ils ne contribuaient pas au nombre unique d'éléments dans une feuille lors de la détermination du moment où la feuille devrait subdiviser). Un arbre Kd peut également être utile si vous prévoyez des entrées avec beaucoup d'éléments coïncidents, car vous n'avez besoin de prendre en compte qu'une seule dimension pour déterminer si un nœud doit être divisé en médiane.