Lorsque vous placez des objets géométriques dans un quadtree (ou octree), vous pouvez placer des objets plus grands qu'un seul nœud de plusieurs manières:
- Placer la référence de l'objet dans chaque feuille pour laquelle il est contenu
- Placer la référence de l'objet dans le nœud le plus profond pour lequel il est entièrement contenu
- # 1 et # 2
Par exemple:
Dans cette image, vous pouvez soit placer le cercle dans les quatre nœuds foliaires (méthode n ° 1), soit uniquement dans le nœud racine (méthode n ° 2) ou les deux (méthode n ° 3).
Pour interroger le quadtree, quelle méthode est la plus courante et pourquoi?
graphics
data-structures
computational-geometry
nsantorello
la source
la source
Réponses:
En supposant que vous stockez une référence, pas l'objet lui-même, il peut être judicieux de le faire différemment selon votre application.
Par exemple, si vous calculiez des collisions avec ce cercle (plein) et que la collision se produisait dans le coin inférieur gauche, ce serait plus facile si vous aviez accès à toutes les géométries de cette feuille directement depuis cette feuille (méthode n ° 3) (sans avoir à traverser l'arbre vers le haut et à déterminer la géométrie héritée). Mais, supposons que vous utilisiez simplement des arbres quadratiques pour dessiner la géométrie, vous voudrez utiliser la méthode # 1, car cela n'a de sens que de dessiner quelque chose dans le nœud pour lequel il est entièrement contenu (il serait plus difficile de déterminer quelle partie dessiner pour chaque nœud de feuille et où).
Quant à ce qui est le plus courant, ma seule expérience avec les quadtrees est d'écrire une simulation à n corps où les objets géométriques n'étaient vraiment que des points sans zone, donc je ne peux pas y répondre définitivement.
la source
L'un des avantages d'un Quadtree est que vous n'avez pas à diviser un nœud en ses nœuds enfants si tous les nœuds enfants contiennent les mêmes informations. Cela peut vous faire économiser beaucoup de mémoire et accélérer le traitement.
Suivant ce principe, je pense qu'il est plus logique de le stocker uniquement dans le nœud racine (méthode # 2). Cela pourrait vous faire économiser beaucoup de mémoire et je pense que cela faciliterait également le traitement. Par exemple, si vous avez essayé de trouver des intersections du cercle avec une ligne passant par trois des nœuds foliaires, vous devrez soit calculer l'intersection séparément pour chaque nœud foliaire, soit vous rappeler que vous avez déjà croisé ce cercle.
D'un autre côté, si vous avez des objets dans les nœuds feuilles, cela pourrait vous aider à éliminer les faux positifs (objets dont vous devez vérifier l'intersection, car ils sont dans le nœud correct, mais qui ne se croisent pas réellement).
Donc, je pense que les deux approches ont leurs utilisations et je ne sais pas comment choisir laquelle utiliser.
Je n'utiliserais probablement pas l'approche n ° 3, car je n'y vois aucun élément positif.
la source