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

Autor(es)

Shin-Ting Wu ^[1] ; Adler C. G. da Silva ^[2] ; Mercedes R. G. Márquez ^[3]

Afiliação do(s) autor(es)

^[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

• Tipo de documento: Artigo Científico
• Fonte: Journal of the Brazilian Computer Society; v. 9, n. 3, p. 67-84, 2004-04-00.

Resumo

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)

• Processo FAPESP: 00/10913-3 - Reconstrucao de um modelo "3d" a partir de multiplas imagens de profundidade.
• Beneficiário: Mercedes Rocio Gonzales Marquez
• Modalidade de apoio: Bolsas no Brasil - Doutorado