An improved spatial contour tree constructed method

Yi Zheng, Ling Zhang, Éric Guilbert, Yi LongProceedings of the ICA 2018 · DOI

Abstract

Contours are essential data for delineating landforms on maps. A contour tree provides an object-oriented description of landforms and can be used to enrich topological information. Traditional contour trees store topological relationships in a hierarchical structure, identifying eminences and depressions as sets of nested contours. This research proposes an improved "spatial contour tree" that incorporates both topological and geometric information. Regarded as a 3D terrain skeleton, it is established based on spatial nodes of contours containing latitude, longitude, and elevation data. The spatial contour tree is built by connecting spatial nodes from low to high elevation for positive landforms, and from high to low elevation for negative landforms. The connections provide real distance and direction as 3D Euclidean vectors. This paper tests the construction method and demonstrates how the resulting hierarchical structure can distinguish landforms and assist in contour generalization while considering geographic characteristics.

TL;DR

This research introduces the "spatial contour tree," an evolution of traditional contour trees that integrates 3D geometric data (latitude, longitude, and elevation) with topological relationships. By treating the tree as a 3D terrain skeleton, the authors provide a robust framework for automated map generalization and quantitative terrain analysis.

The Challenge: Beyond Topology

In cartography and GIS, contour trees are standard tools for representing the hierarchy of landforms—showing how peaks and depressions are nested within one another. However, traditional contour trees are purely topological; they indicate that a peak exists within a certain contour, but lack information on where it is located or the steepness of the slope between levels.

This lack of spatial context hinders automated tasks like map generalization. Without geometric data, algorithms cannot easily distinguish between a significant mountain ridge and a minor feature that should be removed to reduce visual clutter. The authors bridge this gap by embedding 3D Euclidean vectors into the tree structure.

Methodology: Constructing the Spatial Tree

The authors propose a multi-step process to build a spatial contour tree:

  1. Node Determination: Traditionally, the "center" of a contour is its centroid. However, for irregular shapes, the centroid might fall outside the contour. To fix this, the authors use the geometric center of the largest triangle within a Delaunay Triangulated Irregular Network (DTIN) generated inside the contour, ensuring the node remains within the landform.
  2. Tree Construction: Contours are sorted by elevation. For positive landforms (mountains), nodes are connected from low to high elevation; for negative landforms (depressions), they go high to low.
  3. Data Enrichment: Each node is assigned a type (Common, Branch, or Ending) based on its "out-degree" (number of sub-nodes).
  4. 3D Edges: Unlike traditional trees, these edges are treated as 3D vectors storing length (real-world distance), vertical angle (slope), and horizontal direction (azimuth).
Evolution from 2D contours to hierarchical tree structures.

Key Insights: The Terrain Skeleton

The spatial contour tree acts as a "skeleton" inside the terrain, allowing researchers to visualize the internal structure of a mountain range much like a medical X-ray.

3D visualization of the spatial contour tree acting as a terrain skeleton.
  • Quantifying Importance: The vertical angle (AngleV) of a branch edge serves as a proxy for geographical importance. A steep angle indicates a prominent feature, while a shallow angle suggests a minor feature suitable for removal during map simplification.
  • Branching as Complexity: Branch nodes represent points where a landform splits into multiple units. Analyzing the "out-degree" of these nodes allows for the quantification of landscape complexity.

Experimental Results

The method was tested using a 1:10,000 topographic dataset of Lushan Mountain, China, covering 138 contours across an elevation range of 1120m to 1150m. The system was implemented using ArcGIS Runtime SDK for .NET.

The researchers successfully generated a 3D representation where every node and edge contained precise geo-information. By identifying edges with low vertical angles, they demonstrated a preliminary automated generalization, "cleaning" the map by preserving main mountain features while removing minor geographical units.

Limitations and Future Work

As preliminary work, the authors identify several areas for future development:

  • Refining Generalization: Moving beyond simple sub-tree removal to incorporate complex operators like merging adjacent contours.
  • Node Logic: Further verification of the "largest triangle center" logic across diverse landform types.
  • Broader Application: Extending the model into full terrain simulation and advanced landform element classification (e.g., automatically identifying ridges and valleys).

Summary updated

Abstract

Contours are important data to delineate the landform on a map. A contour tree provides an object-oriented description of landforms and can be used to enrich the topological information. The traditional contour tree is used to store topological relationships between contours in a hierarchical structure and allows for the identification of eminences and depressions as sets of nested contours. This research proposes an improved contour tree so-called spatial contour tree that contains not only the topological but also the geometric information. It can be regarded as a terrain skeleton in 3-dimention, and it is established based on the spatial nodes of contours which have the latitude, longitude and elevation information. The spatial contour tree is built by connecting spatial nodes from low to high elevation for a positive landform, and from high to low elevation for a negative landform to form a hierarchical structure. The connection between two spatial nodes can provide the real distance and direction as a Euclidean vector in 3-dimention. In this paper, the construction method is tested in the experiment, and the results are discussed. The proposed hierarchical structure is in 3-demintion and can show the skeleton inside a terrain. The structure, where all nodes have geo-information, can be used to distinguish different landforms and applied for contour generalization with consideration of geographic characteristics.
BibTeX
@inproceedings{zheng2018improved,
  author = {Yi Zheng and Ling Zhang and Éric Guilbert and Yi Long},
  title = {{An improved spatial contour tree constructed method}},
  booktitle = {Proceedings of the ICA},
  year = {2018},
  doi = {10.5194/ica-proc-1-128-2018},
}

Loading related content...

Figure