From Wikipedia, the free encyclopedia
En informàtica, un Quadtree (o arbre quaternari) és un tipus d'arbre d'estructura de dades utilitzat en sistemes de simulació de partícules.
La seva funció és reduir el cost computacional requerit al comprovar en tot moment i per cada partícula la posició de totes les altres partícules de la graella.[1] Per fer-ho, l'algorisme divideix la graella en quatre regions o quadrants rectangulars (tot i que existeixen variants amb altres quantitats i mides) i cadascuna de les regions és tractada com una graella sencera, de manera recursiva, fins a assolir el nombre de partícules màxim per quadrant que busquem. D'aquesta manera, per cada partícula llavors es comprova la posició de les partícules d'aquell quadrant i no de tota la graella, estalviant així la part més feixuga de la computació. El seu cost computacional és O(n log n) on n és el nombre total de partícules, mentre que sense l'algorisme el cost és d'O(n²), molt més elevat.[2]
En una simulació de partícules les forces externes poden ser aplicades per cada partícula paral·lelament, i la col·lisió de partícules només requereix la interacció de les partícules més properes, per tant tots dos casos tenen un cost computacional molt baix, de només O(n). Ara bé, altres forces aplicades a cada partícula poden dependre de tot el conjunt de partícules, per exemple la gravetat, i per tant tenen un cost computacional molt més alt, d'O(n) per cada partícula, és a dir un total d'O(n²). La funció de l'algorisme és proporcionar per cada partícula un rang de comprovació molt menor al total de la graella, de manera que es redueix el cost a O(log n) per cada partícula, és a dir un total d'O(n log n).[2]
Els Quadtree són l'anàleg en dues dimensions dels Octree, que utilitzen el mateix principi en tres dimensions, i utilitzen un sistema de partició de la graella similar als Q-tree (o arbres-Q).[3] Van ser descrits per Raphael Finkel i Jon Bentley el 1974,[1] i són utilitzats en molts de camps diferents, entre ells l'astrofísica, mecànica celeste, simulació de plasma, dinàmica molecular i dinàmica computacional de fluids.[4]
També poden ser utilitzats en la resolució d'equacions diferencials parcials el·líptiques i càlculs de la radiositat en computació gràfica.[5][6]
En general, els Quadtree s'utilitzen per realitzar simulacions de n-cossos i emmagatzemar eficientment grups de dades distribuïts a un pla.[7] La simulació de Barnes-Hut és l'algorisme més sovint utilitzat per emmagatzemar n-cossos en una estructura Quadtree o Octree.[8]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.