Paper Info
Title
Algorithms for Extracting Correct Critical Points and Constructing Topological Graphs from Discrete Geographical Elevation Data
Abstract
Researchers in the fields of computer graphics and geographical information systems GISs have extensively studied the methods of extracting terrain features such as peaks, pits, passes, ridges, and ravines from discrete elevation data. The existing techniques, however, do not guarantee the topological integrity of the extracted features because of their heuristic operations, which results in spurious features. Furthermore, there have been no algorithms for constructing topological graphs such as the surface network and the Reeb graph from the extracted peaks, pits, and passes. This paper presents new algorithms for extracting features and constructing the topological graphs using the features. Our algorithms enable us to extract correct terrain features; i.e., our method extracts the critical points that satisfy the Euler formula, which represents the topological invariant of smooth surfaces. This paper also provides an algorithm that converts the surface network to the Reeb graph for representing contour changes with respect to the height. The discrete elevation data used in this paper is a set of sample points on a terrain surface. Examples are presented to show that the algorithms also appeal to our visual cognition.
Year
DOI
Venue
1995
10.1111/j.1467-8659.1995.cgf143_0181.x
Comput. Graph. Forum
Keywords
Field
DocType
euler formula,critical points,critical point
Topology,Heuristic,Computer science,Terrain,Algorithm,Euler's formula,Invariant (mathematics),Elevation,Computer graphics,Spurious relationship,Reeb graph
Journal
Volume
Issue
ISSN
14
3
0167-7055
Citations 
PageRank 
References 
107
7.01
7
Authors
5
Search Limit
100107
Name
Order
Citations
PageRank
Shigeo Takahashi116815.15
Tetsuya Ikeda21077.01
Yoshihisa Shinagawa31900124.80
Tosiyasu L. Kunii41081291.64
Minoru Ueda51077.35