Computer Graphics & A Digital Terrain Simplification Algorithm with a Partitioning Method 


Vol. 7,  No. 3, pp. 935-942, Mar.  2000
10.3745/KIPSTE.2000.7.3.935


PDF
  Abstract

In this paper we introduce a fast simplification algorithm for terrain height fields to produce a triangulated irregular network, based on the greedy insertion algorithm in [1, 4, 5]. Our algorithm partitions a terrain height data into rectangular blocks with the same size and simplifies blocks one by one with the greedy insertion algorithm. Our algorithm references only to the points and the triangles within each current block for adding a point into the triangulation. Therefore, the algorithm runs faster than the greedy insertion algorithm, which references all input points and triangles in the terrain. Our experiment shows that partitioning method runs from 4 to more than 20 times faster, and it approximates test height fields as accurately as the greedy insertion algorithms. Most greedy insertion algorithms suffer from elongated triangles that usually appear near the boundaries. However, we insert the four corner points into each block to produce the base triangulation of the block before the point addition step begins so that elongated triangles could not appear in the simplified terrain.

  Statistics
  Cite this article

[IEEE Style]

Y. S. Kang, W. C. Park, S. B. Yang, "Computer Graphics & A Digital Terrain Simplification Algorithm with a Partitioning Method," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 7, no. 3, pp. 935-942, 2000. DOI: 10.3745/KIPSTE.2000.7.3.935.

[ACM Style]

Yoon Sig Kang, Woo Chan Park, and Sung Bong Yang. 2000. Computer Graphics & A Digital Terrain Simplification Algorithm with a Partitioning Method. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 7, 3, (2000), 935-942. DOI: 10.3745/KIPSTE.2000.7.3.935.

Forms

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)

Old Journals

Indexing

All publications of TKIPS is indexed in DOI, EBSCO, Google Scholar, Crossref, and CrossCheck.

TKIPS is also selected as the Journal for Accreditation by NRF (National Research Foundation of Korea).

Related Journals