Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: The Douglas-peucker algorithm: sufficiency conditions for non-self-intersections
Author: Wu, Shin-Ting
Silva, Adler C. G. da
Márquez, Mercedes R. G.
Abstract: The classic Douglas-Peucker line-simplification algorithm is recognized as the one that delivers the best perceptual representations of the original lines. It may, however, produce simplified polyline that is not topologically equivalent to the original one consisting of all vertex samples. On the basis of properties of the polyline hulls, Saalfeld devised a simple rule for detecting topological inconsistencies and proposed to solve them by carrying additional refinements. In this paper, we present an alternative form for the classic Douglas-Peucker to produce a simplified polyline which is homeomorphic to the original one. Our modified Douglas-Peucker algorithm is based on two propositions: (1) when an original polyline is star-shaped, its simplification from the Douglas-Peucker procedure cannot self-intersect; and (2) for any polyline, two of its star-shaped sub-polylines may only intersect if there is a vertex of one simplified sub-polyline inside the other's corresponding region.
Subject: Topological Consistency
Line Simplification
Douglas-Peucker Algorithm
Editor: Sociedade Brasileira de Computação
Rights: aberto
Identifier DOI: 10.1590/S0104-65002004000100006
Date Issue: 1-Apr-2004
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

Files in This Item:
File Description SizeFormat 
S0104-65002004000100006.pdf367.74 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.