Advanced search
Start date
Betweenand
Related content
(Reference retrieved automatically from SciELO through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

The Douglas-peucker algorithm: sufficiency conditions for non-self-intersections

Full text
Author(s):
Shin-Ting Wu [1] ; Adler C. G. da Silva [2] ; Mercedes R. G. Márquez [3]
Total Authors: 3
Affiliation:
[1] Universidade Estadual de Campinas. Faculdade de Engenharia Elétrica e Computação. Departamento de Engenharia de Computação e Automação Industrial
[2] Universidade Estadual de Campinas. Faculdade de Engenharia Elétrica e Computação. Departamento de Engenharia de Computação e Automação Industrial
[3] Universidade Estadual de Campinas. Faculdade de Engenharia Elétrica e Computação. Departamento de Engenharia de Computação e Automação Industrial
Total Affiliations: 3
Document type: Journal article
Source: Journal of the Brazilian Computer Society; v. 9, n. 3, p. 67-84, 2004-04-00.
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. (AU)