Van Kreveld M., Nievergelt J., Roos T., Widmayer P. (eds.) Algorithmic Foundations of Geographic Information Systems

Van Kreveld M., Nievergelt J., Roos T., Widmayer P. (eds.) Algorithmic Foundations of Geographic Information Systems
  • разное
  • pdf
  • 7.34 МБ
  • добавлен 29.10.2011
Издательство Springer, 1997, -297 pp.

This volume aims to bring together the two lines of research whose interaction promises to have significant practical impact in the near future: the application-oriented discipline of Geographic Information Systems (GIS) and the technical discipline of geometric computation, or in particular, geometric algorithms and spatial data structures. GIS are complex systems consisting of a database part and a spatial data handling part. Spatial data handling in current GIS is less well-developed than the database aspects, and it is in relation to the spatial aspects that geometric algorithms and modeling can stimulate progress in GIS. GIS include many geometry-related problems such as spatial data storage and retrieval, visualization of spatial data, overlay of maps, spatial interpolation, and generalization.
Geometric Algorithms and GIS
Algorithms research has been an integral part of computer science since its beginnings. The goal is to design well-defined procedures that solve well-defined problems, and analyze their efficiency. Numerical algorithms were studied most thoroughly in the first phase of automated computation, and data management algorithms for sorting and searching became prominent in the 1960s. In the second half of the 1970s the systematic study of geometric algorithms gave birth to the discipline known today as computational geometry. The motivation for studying geometric algorithms comes from areas like robotics, computer graphics, automated manufacturing, VLSI design, and GIS.
The collaboration of GIS research and computational geometry has intensified in recent years, for several reasons. Firstly, the availability of geographic data in digital form is increasing rapidly. The acquisition of geographic data and the digitizing of maps are laborious, time-consuming tasks, and without appropriate digital data, GIS cannot operate effectively. Secondly, improved hardware now makes it possible to store and process large amounts of geographic data and to produce high-quality maps on computers. Thirdly, the research community in computational geometry, after having laid the conceptual and technical foundation, has recently shifted its attention toward more practical and more applied solutions.
Collaboration of GIS and Computational Geometry
The time is right for further development of the spatial components of GIS, as a result of joint efforts from computational geometry and GIS. What should such a collaboration look like? Many standard geometric problems and solutions, even those without any explicit reference to geography, are useful to GIS. Storing polygonal subdivisions on primary or background storage for efficient windowing queries is one example. Implementation and testing of data structures and query algorithms reveals their usefulness to GIS. Most of the basic algorithms developed in computational geometry, however, are not directly applicable to GIS. This is because standard geometric problems are often simplified to such an extent that they neglect important requirements of GIS. In addition, many problems arising in GIS have not yet been formalized in sufficient detail for the design of efficient algorithms.
As an example, consider generalization of maps. When the scale of a map is reduced, less information can be shown on the map, so it is necessary to remove or simplify certain objects on the map. However, it is far from clear which objects to remove or simplify. Different cartographers would produce different maps, if they were to generalize a map manually. A first step towards an automated map generalization method is the modeling of what should be generalized, when this is necessary, and how. These modeling questions cannot be answered by someone without cartographic knowledge. On the other hand, computational geometers are trained to abstract a problem into a form that is well defined. The joint knowledge of a cartographer and a geometer can result in a good model, a specification, for automated map generalization. Given such a specification, algorithms can be designed and implemented to compute the desired output.
There are several standard geometric structures and algorithms useful in GIS, with or without some modifications. These include topological data structures like the doubly-connected edge list or quad edge structure, spatial data structures like the quadtree and R-tree, the Voronoi diagram, the Delaunay triangulation., map overlay and buffer computation, and visualization algorithms. Most of these structures and algorithms are also used in other fields like computer graphics and robotics. They are well documented in textbooks or other standard texts.

Introduction to Geometric Computing: From Algorithms to Software
Voronoi Methods in GIS
Digital Elevation Models and TIN Algorithms
Visualization of TINs
Generalization of Spatial Data: Principles and Selected Algorithms
Spatial Data Structures : Concepts and Design Choices
Space Filling Curves versus Random Walks
External-Memory Algorithms with Applications in GIS
Precision and Robustness in Geometric Computations

Смотрите также


Galati S.R. Geographic Information Systems Demystified: A Self-Teaching Guide

Galati S.R. Geographic Information Systems Demystified: A Self-Teaching Guide

  • разное
  • pdf
  • 11.83 МБ
  • добавлен 03.04.2011
Artech House Publishers, 2006. - 302 Pages.

Geographic information systems (GIS) – a central repository of geographic data collected from various sources, including satellites and GPS is emerging as one of the most intriguing and promising high-tech fields. Today, many technical, managerial, engineering, and academic po...
Zogg Jean-Marie. GPS. Essentials of Satellite Navigation. Compendium

Zogg Jean-Marie. GPS. Essentials of Satellite Navigation. Compendium

  • разное
  • pdf
  • 5.78 МБ
  • добавлен 16.10.2010
Theory and Principles of Satellite Navigation.  
Overview of GPS/GNSS Systems and Applications. 
175 pages

Satellite navigation made simple
Coordinate systems
Foundations of satellite technology
GNSS technology: the GPS example
GLONASS, GALILEO and Beidou/Compass
Calculating position
Impr...
Schneider M. Spatial Data Types for Database Systems. Finite Resolution Geometry for Geographic Information Systems

Schneider M. Spatial Data Types for Database Systems. Finite Resolution Geometry for Geographic Information Systems

  • разное
  • pdf
  • 5.46 МБ
  • добавлен 29.10.2011
Издательство Springer, 1997, -282 pp.

Database research in the last decade has focused on developing support for so-called non-standard applications. One important area is the representation of spatial information, needed, for example, in Geographic Information Systems. Database systems extended by capabilities for mana...
Karimi H.A. Universal Navigation on Smartphones

Karimi H.A. Universal Navigation on Smartphones

  • разное
  • pdf
  • 8.12 МБ
  • добавлен 14.08.2011
Springer, 2011. - 157 p.

Universal navigation is accessible primarily through smart phones providing users with navigation information regardless of the environment (i.e., outdoor or indoor). Universal Navigation for Smart Phones provide the most up-to-date navigation technologies and systems for both outdoor and indoor...
Shekar S., Xiong H. (eds.) Encyclopedia of GIS

Shekar S., Xiong H. (eds.) Encyclopedia of GIS

  • разное
  • pdf
  • 30.78 МБ
  • добавлен 19.10.2011
Издательство Springer, 2008, -1391 pp.

The publication of a definitive Encyclopedia of GIS that lays out many of the computer science/mathematics foundations of the field is a major event, the culmination of a half century of development. I was part of the earliest stirrings in the mid-1950s. A small group of geography ...
Нет изображения

Church R.L., Murray A.T. Business site selection, location analysis and GIS

  • разное
  • pdf
  • 8.03 МБ
  • добавлен 27.12.2011
John Wiley & Sons, Inc., 2009. – 314 pages.
Location theory is rooted in the disciplines of geography, engineering, mathematics, and economics. The science of ‘‘where should it be’’ is truly multidisciplinary and continues to be of interest to practitioners and researchers alike representing a variety of ?elds, ranging f...
Desktop GIS: Mapping the Planet with Open Source Tools

Desktop GIS: Mapping the Planet with Open Source Tools

  • разное
  • pdf
  • 9.44 МБ
  • добавлен 22.11.2009
Publisher: Pragmatic Bookshelf Publication: 2008, English ISBN: 9781934356067 Pages: 368

Desktop GIS explores the world of Open Source GIS software and provides a guide to navigate the many options available. Discover what kind of GIS user you are and lay the foundation to evaluate the options and decide what software i...
O'Sullivan D., Unwin D. Geographic Information Analysis

O'Sullivan D., Unwin D. Geographic Information Analysis

  • разное
  • djvu
  • 8.38 МБ
  • добавлен 15.12.2011
Wiley, 2002.- 444 pp. ISBN
9780471211761. First and foremost, this is a geography book! We assume that readers have a basic grounding in statistics, but to be on the safe side we have included a similar appendix outlining the major statistical ideas on which we draw, and similar comments apply.
French Gregory T. Understanding the GPS

French Gregory T. Understanding the GPS

  • разное
  • pdf
  • 11.05 МБ
  • добавлен 07.04.2011
Introduction to GlobalPositioning System: What it is and how it works.
GeoResearch, Inc. 1996. 264 pages.
There is an ever-growing supply of information about the Global Positioning System. Unfortunately, these new (and now, some not so new) documents seem to be located at each end of the comprehension scale: either at t...
John T. Sample, Elias Ioup. Tile-Based Geospatial Information Systems

John T. Sample, Elias Ioup. Tile-Based Geospatial Information Systems

  • разное
  • pdf
  • 5.23 МБ
  • добавлен 06.03.2011
Springer, 2010
Background of Web-Based Mapping Applications
Logical Tile Schemes
Tiled Mapping Clients
Image Processing and Manipulation
Image Tile Creation
Optimization of Tile Creation
Tile Storage
Tile Serving
Map Projections
Tile Creation using Vector Data
Case Study: Tiles from Bl...