Applications Of Spatial Data Structures

Applications of Spatial Data Structures

« The quadtree and octree are hierarchical data structures used to represent spatial data. This book shows how these spatial data structures can be applied in computer graphics, image processing, geographic information systems (GIS), and other domains. It illustrates the representation of region data, in particular, both in two dimensions with quadtrees and in three dimensions with octrees. The advantage of hierarchical data structures is their ability to focus on interesting subsets of the data, resulting in more efficient representation and faster execution. Thus, they are particularly convenient for performing set operations. Even where other data structures might perform as efficiently, hierarchical data structures are often preferred for their conceptual clarity and ease of implementation. The author begins with a general introduction to spatial data structures. He continues with explanations of how to convert between quadtrees and other representations, as well as applications such as geometric property computation, image transformations, ray tracing, and image compression. The approach is algorithmic. Each chapter after the introduction contains at least one detailed algorithm, written in pseudo code, to illustrate an application. Each critical step in these algorithms is described with a liberal use of examples. Each chapter also includes a large number of exercices, with solutions provided for many. The book focuses on implementation techniques and the uses of spatial data structures. Readers desiring a more complete introduction to these representations, including fundamental concepts, basic techniques, and a broad range of possible uses, should refer to another book by the same author, The design and analysis of spatial data structures. The introductory material in Applications of spatial data structures makes the book self-contained. Each book contains an extensive bibliography, and the books are cross-referenced. »--Quatrième de couverture.

Applications of Spatial Data Structures

Spatial Databases

The authors explore and explain current techniques for handling the specialised data that describes geographical phenomena in a study that will be of great value to computer scientists and geographers working with spatial databases.