Estruturas de dados espaciais

RESUMO

Este trabalho apresenta, de forma breve, as Estruturas de Dados Espaciais, especialmente úteis em diversas áreas da computação, como nos jogos, sistemas GIS, sistemas que utilizam informações cartográficas, etc. Além disso, reúne revisões de alguns trabalhos justamente relacionados com as áreas supracitadas.

ABSTRACT

This paper briefly presents the Spatial Data Structures, especially useful in several areas of computing such as games, GIS systems, systems that use map information, and so on. In addition, revisions gathers some papers relating to such areas.

ÍNDICE

LISTA DE FIGURASii
LISTA DE ABREVIATURAS E SIGLASiii
Capítulo 1. Introdução1
1.1. Considerações iniciais1
1.2. Objetivos1
1.3. Organização da monografia1
Capítulo 2. Exemplos de estruturas2
2.1. Introdução2
2.2. Quadtrees 2
2.3. Octrees 4
2.4. K-d-trees 5
2.5. BSP-trees 6
Capítulo 3. Exemplos de aplicações7
3.1. Introdução7
3.2. Detecção de colisões7
3.3. Compressão de imagens9
3.4. Algoritmos de clustering10
3.5. Ray tracing 11
Capítulo 4. Conclusões13
4.1. Conclusões gerais13
Referências14

LISTA DE FIGURAS

Figura 2.1. (a) Exemplo de uma região bidimensional, (b) sua matriz de bits, (c) seus blocos maximais e (d) sua quadtree (SAMET, 1990)4
Figura 2.2. (a) Exemplo de uma região tridimensional, (b) sua decomposição em blocos e (c) a respectiva octree (SAMET, 1990)5
Figura 3.1. (a) Partição Quadtree Adaptativa e (b) Partição em Blocos de Tamanho Fixo (QIN et al., 2009)10

LISTA DE ABREVIATURAS E SIGLAS

BSP-trees: Binary Space Partition Trees
CAD: Computer-Aided Design
K-d-trees: k-dimensional-trees
ODM: Octrees Distance Maps
Capítulo
1
IntroduçãoConsiderações iniciaisOs dados espaciais comumente são definidos em uma dimensão, por exemplo no caso de um ponto, em duas dimensões, no caso das linhas, retângulos e polígonos ou em três dimensões, como no caso das superfícies. Apesar disso, eles também podem ser definidos em dimensões maiores, que