A non-self-intersection Douglas-Peucker Algorithm

Shin-Ting WuMercedes Rocío Gonzales Márquez

The classical Douglas-Peucker line-simplification algorithm is recognized as the one that delivers the best perceptual representations of the original lines. It is used extensively for both computer graphics and geographic information systems. There are two variants of this algorithm, the original O(nm) method, that works in any dimension, and the O(nlogn) one, which only works for simple 2D planar polylines. In the both variants, a self-intersecting simplified line may be yielded if the accepted approximation is not sufficiently fine. Based on star-shaped subsets, we present in this paper yet another O(mn) variant of Douglas-Peucker algorithm which preserves the non-self-intersection property for any predefined tolerance.

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato:
     Mantida por: