Estruturas de dados espaciais

Disponível somente no TrabalhosFeitos
  • Páginas : 15 (3553 palavras )
  • Download(s) : 0
  • Publicado : 22 de abril de 2013
Ler documento completo
Amostra do texto
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) suamatriz 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, quepodem inclusive envolver o tempo (SAMET, 1990).
Em um mapa, por exemplo, é possível encontrar alguns exemplos de dados espaciais, que são: os países, os estados, as cidades, as ruas, as rodovias, os rios, etc.

ObjetivosEste trabalho tenta trazer uma visão geral acerca das estruturas espaciais e suas aplicações, dando preferência para trabalhos científicos mais recentes, ou seja, tenta mostrar oque tem sido feito de novo na área.

Organização da monografiaEsta monografia está dividida em quatro capítulos. No capítulo 2 são apresentados os conceitos de estruturas espaciais e alguns exemplos. No capítulo 3 são descritos alguns exemplos de problemas em que são aplicadas tais estruturas. Por fim, no capítulo 4 são apresentas as conclusões deste trabalho.
Capítulo
2
Exemplos deestruturasIntroduçãoAs Estruturas de Dados Espaciais surgiram da necessidade de se representar dados espaciais como por exemplo cidades, ruas, rios, estradas, países, estados, partes de um sistema do tipo Computer-Aided Design (CAD). Além disso, alguns problemas bastante específicos clamam por tais estruturas, como pode ser visto no Capítulo 3.
Uma das maneiras de se representar dados espaciais éfazendo uso de estruturas hierárquicas. Um exemplo típico de uma estrutura desse tipo é a árvore, uma vez que seus elementos tem uma relação de “parentesco” entre si. Segundo (SAMET, 1990), as estruturas hierárquicas são úteis pois permitem facilmente trabalhar com apenas um subconjunto dos dados, facilitando a aplicação de operações sobre conjuntos. Além disso, constituem uma abstração clara eeficiente, de fácil implementação.
Existem diversas estruturas hierárquicas, contudo neste trabalho será dado foco a apenas aquelas utilizadas para se representar dados espaciais, com um certo destaque para as quadtrees, as octrees, as k-d-trees e as BSP-trees, que serão melhor detalhadas nas seções deste capítulo.

Quadtrees De acordo com (SAMET, 1990), O termo quadtree, na verdade, descreve uma...
tracking img