EFFICIENT METHODS FOR ISOLINE EXTRACTION FROM A TIN

A data structure is presented to store a triangulated irregular networ k 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 (log n + 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 adja cency), the query requires additional O(c log c) or O(c log log n) tim e, where c is the number of connected components of isolines. In all t hree cases, the required data structure has only linear size.