The Sausage of Local Convex Hulls of a Curve and the Douglas-Peucker Algorithm
François Normant, Axel van de Walle · Cartographica The International Journal for Geographic Information and Geovisualization · 1996
We investigate the problem of the simplification of a curve from a geometrical and fractal viewpoint. We consider that the best methods are those that keep an estimated value of the fractal dimension constant, before and after simplification, and that consider local details during processing. We propose here both a simplification method and a simplification criterion, based on a new algorithm for computing the fractal dimension introduced by Tricot (1994). We cover the curve with overlapping convex sets of constant breadth (the ϵ-sausage of convex structuring elements) and retain the points of the original curve that lie on the boundary of this covering set. This algorithm is both accurate and universal, and does not imply the need to make any arbitrary hypotheses regarding the structure of the curve. We will show experimentally that the well-known Douglas-Peucker method shares some very interesting geometrical properties with this algorithm and thus has the ability to preserve the fractal dimension when evaluated with a lower cutoff equal to the threshold distance.