Greedy Cuts: An advancing front terrain triangulation algorithm

Cláudio T. Silva, Joseph S.B. Mitchell

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We apply an advancing front technique to the problem of simplification of dense digitized terrain models. While most simplification algorithms have been based on either incremental refinement or decimation techniques, our Greedy-Cuts algorithm uses a simple triangulation-growth procedure. We improve on our earlier advancing-front technique, which was not able to backtrack in its triangulation decisions, resulting in triangulations that may have low quality. The new algorithm we propose overcomes this shortcoming by maintaining two "fronts", a real front and a virtual front, that bound between them a region of the terrain that has only a tentative triangulation. By allowing simple local operations (edge collapses and edge flips) in the tentative triangulation, we are able to avoid many of the artifacts of the earlier advancing-front technique, while not significantly affecting memory usage. GcTin, our terrain triangulation tool, is publicly available for research purposes. The original version of GcTin has been in use at several commercial and non-commercial sites since 1995. The new algorithms described here are integrated in the latest release and result in substantially improved triangulations.

Original languageEnglish (US)
Title of host publicationProceedings of the 6th ACM International Symposium on Advances in Geographic Information Systems, GIS 1998
PublisherAssociation for Computing Machinery
Pages137-144
Number of pages8
ISBN (Electronic)1581131151
DOIs
StatePublished - Nov 1 1998
Event6th ACM International Symposium on Advances in Geographic Information Systems, GIS 1998 - Washington, United States
Duration: Nov 2 1998Nov 7 1998

Publication series

NameGIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
VolumePart F129244

Other

Other6th ACM International Symposium on Advances in Geographic Information Systems, GIS 1998
CountryUnited States
CityWashington
Period11/2/9811/7/98

ASJC Scopus subject areas

  • Earth-Surface Processes
  • Computer Science Applications
  • Modeling and Simulation
  • Computer Graphics and Computer-Aided Design
  • Information Systems

Fingerprint Dive into the research topics of 'Greedy Cuts: An advancing front terrain triangulation algorithm'. Together they form a unique fingerprint.

  • Cite this

    Silva, C. T., & Mitchell, J. S. B. (1998). Greedy Cuts: An advancing front terrain triangulation algorithm. In Proceedings of the 6th ACM International Symposium on Advances in Geographic Information Systems, GIS 1998 (pp. 137-144). (GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems; Vol. Part F129244). Association for Computing Machinery. https://doi.org/10.1145/288692.288717