Efficient methods for Isoline extraction from a TIN |
| |
Authors: | Marc Van Kreveld |
| |
Institution: | Department of Computer Science , Utrecht University , P.O. Box 80.089, 3508, TB, Utrecht, the Netherlands E-mail: email: marc@cs.ruu.nl. |
| |
Abstract: | Abstract A data structure is presented to store a triangulated irregular network digital elevation model, from which isolines (contour lines) can be extracted very efficiently. If the network is based on n points, then for any elevation, the isolines can be obtained in O (logn + k) query time, where k is the number of line segments that form the isolines. This compares favourably with O(n) time by straightforward computation. When a structured representation of the isolines is needed, the same query time applies. For a fully topological representation (with adjacency), the query requires additional O(c log c) or O(c log logo) time, where c is the number of connected components of isolines. In all three cases, the required data structure has only linear size. |
| |
Keywords: | |
|
|