Quadtree

Uma quadtree ou árvore quaternária ( árvore Q ) é uma estrutura de dados semelhante a uma árvore na qual cada nó tem quatro filhos. Quadtrees são mais frequentemente usados ​​para particionar um espaço bidimensional, subdividindo-o recursivamente em quatro nós.

Quadtrees são a analogia bidimensional de octrees . O nome é formado por quad e tree . Cada nó de uma quadtree subdivide o espaço que representa em quatro subespaços.

Tipos

Quadtrees podem ser classificados de acordo com o tipo de dados que representam, incluindo regiões, pontos, linhas e curvas. Aqui estão alguns tipos comuns de quadtrees:

A "região" quadtree

A "região" quadtree representa uma partição do espaço em duas dimensões, dividindo a região em quatro quadrantes iguais, então cada quadrante em quatro subquadrantes, e assim por diante, com cada "nó terminal" compreendendo dados correspondentes a um sub- região. Cada nó da árvore tem exatamente: quatro filhos ou nenhum (caso de um nó terminal). A "região" quadtree é um tipo de árvore de prefixo .

Uma quadtree de “região” com profundidade n pode ser usada para representar uma imagem de 2 n  × 2 n  pixels, onde o valor de cada pixel é 0 ou 1. O nó pai representa a imagem inteira. Se os pixels em uma determinada região não forem todos 0 ou 1, essa região será subdividida. Em tal representação de uma imagem, cada nó terminal representa um bloco de pixels que são todos 0 ou todos 1.

Uma quadtree de “região” também pode ser usada como uma representação de resolução variável de um campo de dados. Por exemplo, as temperaturas de uma área podem ser armazenadas em uma quadtree, na qual cada nó terminal armazena a temperatura média da sub-região que representa.

Se uma quadtree “região” é usada para representar um conjunto de pontos (por exemplo, as latitudes e longitudes de um grupo de cidades), as regiões são subdivididas até que cada nó terminal contenha apenas um ponto.

O quadtree "pontual"

A quadtree de “pontos” é uma adaptação de uma árvore binária , usada para representar dados de “pontos” bidimensionais (por exemplo, uma coordenada geográfica). Ele compartilha as características de todos os quadtrees, embora seja uma árvore real , já que o centro de uma subdivisão está sempre em um ponto. A forma da árvore depende da ordem em que os dados são processados. Essa representação é frequentemente muito eficiente em comparação com dados de "pontos" bidimensionais ordenados, geralmente operando em tempo O (log n) .

Estrutura de um nó de uma quadtree "pontual"

O nó de uma quadtree "ponto" é semelhante ao de uma árvore binária , com esta grande diferença: o primeiro possui quatro ponteiros (um para cada quadrante), enquanto o segundo possui apenas dois ("esquerdo" e "direito"). Outra diferença, uma chave geralmente é dividida em duas partes, referindo-se às coordenadas xey. Um nó, portanto, contém as seguintes informações:

  • quatro ponteiros: quad ['NO'], quad ['NE'], quad ['SO'] e quad ['SE']
  • um ponto, que por sua vez contém:
    • uma chave: geralmente coordenadas (x, y)
    • um valor: por exemplo, um nome.

O quadtree "edge"

Quadtrees “Edge” são usados ​​especificamente para armazenar linhas, em vez de pontos. As curvas são aproximadas subdividindo as células em uma resolução muito fina. Isso pode resultar em árvores extremamente desequilibradas, negando assim o valor da indexação.

O quadtree "mapa poligonal"

O “mapa poligonal” quadtree (ou CP-quadtree) é uma variação de quadtree, usado para armazenar coleções de polígonos potencialmente degenerados (ou seja, tendo vértices ou arestas isoladas). Existem três classes principais de CP-quadtrees, variando dependendo das informações que armazenam dentro de cada "nó preto". CP3-quadtrees pode armazenar qualquer quantidade de "arestas não cortantes" e no máximo um ponto. CP2-quadtrees são iguais a CP3-quadtrees, exceto que todas as arestas devem compartilhar o mesmo ponto final. Finalmente, CP1-quadtrees são semelhantes a CP2-quadtrees, mas "nós pretos" podem conter um ponto e suas arestas ou apenas um conjunto de arestas compartilhando um ponto (mas você não pode ter um ponto e um conjunto de arestas. Que não contêm este ponto).

Alguns usos comuns de quadtrees

Pseudo-código

O pseudocódigo a seguir mostra uma possível implementação de um quadtree que trata apenas de pontos. Existem outras abordagens válidas.

Pré-requisitos

Presume-se que as seguintes estruturas são usadas.

// Objet de coordonnées simples pour représenter des points et des vecteurs struct XY { float x; float y; function __construct(float _x, float _y) {...} } // Zone de délimitation alignée sur l'axe, représentée par sa demi-dimension et son centre struct AABB { XY center; XY halfDimension; function __construct(XY center, XY halfDimension) {...} function containsPoint(XY p) {...} function intersectsAABB(AABB other) {...} }

Aula QuadTree

Esta classe representa um quadtree e seu nó pai.

class QuadTree { // Constante arbitraire indiquant combien d'éléments peuvent être stockés dans ce nœud de quadtree constant int QT_NODE_CAPACITY = 4; // Zone de délimitation alignée sur l'axe (représentée par sa demi-dimension et son centre) // représentant les limites de ce quadtree AABB boundary; // Points de ce nœeud de quadtree Array of XY [size = QT_NODE_CAPACITY] points; // Enfants QuadTree* northWest; QuadTree* northEast; QuadTree* southWest; QuadTree* southEast; // Méthodes function __construct(AABB _boundary) {...} function insert(XY p) {...} function subdivide() {...} // créer quatre enfants permettant de diviser ce quadrant en quatre quadrants d'égales dimensions function queryRange(AABB range) {...} }

Inserção

O método a seguir insere um ponto no quadrante apropriado de uma quadtree, realizando uma partição se necessário.

class QuadTree { ... // Insérer un point dans le QuadTree function insert(XY p) { // Ignorer les objets qui n'appartiennent pas à ce quadtree if (!boundary.containsPoint(p)) return false; // l'objet ne doit pas être ajouté // S'il reste de la place dans ce quadtree, y ajouter l'objet if (points.size < QT_NODE_CAPACITY) { points.append(p); return true; } // Sinon, subdiviser le quadtree, puis ajouter le point au nœud qui l'acceptera if (northWest == null) subdivide(); if (northWest→insert(p)) return true; if (northEast→insert(p)) return true; if (southWest→insert(p)) return true; if (southEast→insert(p)) return true; // Sinon, le point ne peut être inséré, pour une raison inconnue (cela ne devrait jamais arriver) return false; } }

Pesquisar em uma área

O método a seguir encontra todos os pontos em uma "caixa de pesquisa".

class QuadTree { ... // Trouver tous les points apparaissant à l'intérieur d'une «zone de recherche» function queryRange(AABB range) { // Préparer le tableau de résultats Array of XY pointsInRange; // Tout interrompre si la «zone de recherche» n'intersecte pas ce quadrant if (!boundary.intersectsAABB(range)) return pointsInRange; // liste vide // Vérifier les objets à ce niveau de quadrant for (int p := 0; p < points.size; p++) { if (range.containsPoint(points[p])) pointsInRange.append(points[p]); } // Terminer ici, s'il n'y a pas d'enfant if (northWest == null) return pointsInRange; // Sinon, relancer la recherche sur les 4 enfants et ajouter les points trouvés pointsInRange.appendArray(northWest→queryRange(range)); pointsInRange.appendArray(northEast→queryRange(range)); pointsInRange.appendArray(southWest→queryRange(range)); pointsInRange.appendArray(southEast→queryRange(range)); return pointsInRange; } }

Veja também

Notas e referências

Notas

  1. Hanan Samet  (in) e Robert Webber. "Armazenando uma coleção de polígonos usando Quadtrees". ACM Transactions on Graphics July 1985: 182-222. InfoLAB . Rede. 23 de março de 2012
  2. Tomas G. Rokicki, "  Um Algoritmo para a Compressão do Espaço e do Tempo  " ,1 ° de abril de 2006(acessado em 20 de maio de 2009 )
  3. Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation , Proceedings of the 13th International Conference on Information Fusion, Edinburgh, UK, July 2010.

Referências gerais

  1. Raphael Finkel e JL Bentley , "  Quad Trees: A Data Structure for Retrieval on Composite Keys  ", Acta Informatica , vol.  4, n o  1,1974, p.  1–9 ( DOI  10.1007 / BF00288933 )
  2. Mark de Berg , Marc van Kreveld , Mark Overmars e Otfried Schwarzkopf , Computational Geometry , Springer-Verlag ,2000( ISBN  3-540-65620-0 )Capítulo 14: Quadtrees: p.  291–306 .
  3. Hanan Samet e Robert Webber , “  Storing a Collection of Polygons Using Quadtrees  ” ,Julho de 1985(acessado em 23 de março de 2012 )

links externos