Orientador: Jorge Stolfi / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-25T10:03:56Z (GMT). No. of bitstreams: 1
Andrade_MarcusViniciusAlvim_D.pdf: 7188017 bytes, checksum: 2bebda4708b2cb122cfd9a807ac2f471 (MD5)
Previous issue date: 1999 / Resumo: Neste trabalho desenvolvemos um conjunto de ferramentas para a representação e manipulação exatas de mapas esféricos (mapas sobre a esfera formados por arcos de círculos, não necessariamente máximos) adequados para a implementação de sistemas de informações geográficas (SIGs). Na primeira parte deste trabalho, descrevemos a estrutura de dados SMC (Spherical Maps by Corners) para representar a topologia de mapas esféricos. Esta estrutura permite a representação de mapas bastante gerais, incluindo arestas ovais (não incidentes a nenhum vértice), vértices isolados (não incidentes a nenhuma aresta), e faces com múltiplas bordas. Definimos também um conjunto de operadores topológicos para construir, percorrer e modificar esta estrutura. Na segunda parte, definimos os círculos racionais, um subconjunto denso dos círculos sobre a esfera S2 que podem ser representados de maneira exata. Baseados neste conceito, definimos representações exatas para pontos e arcos de círculos na esfera, sendo que o conjunto dos pontos representáveis exatamente (os pontos sub-racionais) inclui todos os pontos de interseção entre círculos racionais. Desenvolvemos também algoritmos exatos para as operações geométricas básicas sobre círculos racionais, incluindo interseção, posição relativa, ordenação de pontos sobre um círculo e ordenação de círculos em torno de um ponto. Na terceira parte, baseados nos resultados descritos nas duas partes anteriores, desenvolvemos algoritmos exatos para localização de pontos num mapa esférico, e para sobreposição de dois mapas esféricos. Observamos também que boa parte das operações geométricas usadas em SIGs (por exemplo, interseção de regiões, localização de pontos, extração de detalhes, recortes) podem ser reduzidas a problemas de sobreposição. Finalmente, mostramos que este conjunto de ferramentas é econômico e eficiente o bastante para servir de base para a implementação de SIGs. Todos os algoritmos apresentados neste trabalho foram implementados (em Modula-3) na forma de uma biblioteca genérica para a representação e manipulação exatas de mapas esféricos / Abstract: In this dissertation we develop a tool kit for the exact representation and manipulation of spherical maps (maps on the sphere composed by arcs of circles, not necessarily geodesic ones), suitable for the implementation of geographical information systems (GIS). Firstly, we describe the data structure SMC (spherical maps by corners) which we developed to represent the topology of spherical maps. It allows the representation of fairly general maps, including maps that have oval edges (not incident to any vertex), isolated vertices (not incident to any edge), and faces with multiple borders. We also define a set of topological operators to build, traverse and modify this structure. Secondly, we define the rational circles, a dense subset of circles on the sphere S2 which can be exactly represented. Based on this concept, we develop an exact representation of points, circles and circular arcs on the sphere, such that the set of exactly representable points (sub-rational points) includes all points of intersection of two rational circles. We also develop exact algorithms for basic geometric operations with rational circles, including intersection, relative position, circular ordering of points on rational circles, and circular ordering of circles around a point. Thirdly, we use these tools to develop exact algorithms for point location on spherical maps, and to compute the overlay of two spherical maps. We note that most geometric operations used in GIS (region intersection, point location, feature extraction, clipping etc) can be reduced to map overlay. Finally, we show that the proposed tool kit is economical and efficient enough to be used as the basis for the implementation of a GIS. All algorithms described in this text were implemented (in Modula-3) as a general-purpose library for the exact representation and manipulation of spherical maps / Doutorado / Doutor em Ciência da Computação
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/275823 |
| Date | 25 July 2018 |
| Creators | Andrade, Marcus Vinicius Alvim |
| Contributors | UNIVERSIDADE ESTADUAL DE CAMPINAS, Stolfi, Jorge, 1950-, Gattass, Marcelo, Feofiloff, Paulo, Rezende, Pedro Jussieu de, Souza, Cid Carvalho de |
| Publisher | [s.n.], Universidade Estadual de Campinas. Instituto de Computação, Programa de Pós-Graduação em Ciência da Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | 145p. : il., application/octet-stream |
| Source | reponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0016 seconds