Aeds

Trabalho Pratico 0
Algoritmo e Estrutura de Dados III
Quadtree
Mauri Miguel Costa Jr
Departamento de Ciências da Computação – Universidade Federal de Minas Gerais [e-mail] INTRODUÇÃO:
Este trabalho teve como objetivo a implementação de uma Quadtree. Quadtree é uma técnica de indexação especial, ela é um grafo onde o vértice raiz cobre toda a área que esta sendo mapeada e os demais vértices ou são vértices folhas onde são guardados os pontos ou são vértices internos possuindo exatamente quatro filhos, onde cada um representando um quarto da área mapeada pelo vértice anterior.
Ilustração de exemplo:

.

Figura: Representação de como uma Quadtree é organizada.

A inserção de pontos em uma Quadtree é feita a partir da raiz analisando a coordenada do ponto a ser inserido e a comparando com a região mapeada pelos vértices internos, é feito essa processo recursivamente ate que se encontre o vértice folha onde será adicionado o ponto.
Porem existe um limite pré-determinado de pontos que um vértice folha deve guardar, portanto caso o numero de pontos adicionados no vértice folha exceda esse limite, deve-se subdividir a área mapeada pelo vértice folha em quatro novos quadrantes e redistribuir os pontos nos novos vértices de acordo com suas coordenadas.

Segue abaixo a regra para a distribuição dos pontos nos novos quadrantes:

Onde X e Y são as coordenadas do ponto ser inserido e A e B os limites da região mapeada pelo vértice.
Após a inserção de todos os pontos na Quadtree, o problema se resume em dada uma região do espaço mapeado dizer quais pontos estão presentes nele.
DESCRIÇÃO DO PROBLEMA:
Neste trabalho foi implementado na linguagem de programação C, uma Quadtree como uma generalização multidimensional de uma arvore binaria. Onde cada nó ou é uma folha onde são guardados os pontos e não contem filhos, ou são vértices internos onde não contem pontos, mas contem exatamente quatro filhos, sendo que cada vértice guarda a