Brussels / 31 January & 1 February 2015


Douglas-Peucker updated

or do you want to reduce your data

Douglas-Peucker from the early '70 delivers excellent quality, but requests to have a polyline from start to end before reduction can start. In this modified algorithm there is no need to store all points, or to wait until the end of the polyline happens.

For embedded system it is not practical to have to store all points of a polyline before being able to reduce the number of points. The modified algorithm describes a way to decide on the go which points are essentials (and need to be stored). With the Douglas_Peucker two criteria can be used : the maximum number of points to retain, or the maximum error tolerated. In the modified algorithm only the max error tolerated can be being. Because the algorithm cannot predict the future length of the polyline, it's not possible to apply the maximum number of points. Examples shown contains 2D and 3D cases, in comparison with the Douglas-Peucker algorithm. A brief description will introduce the same concept of the modified algorithm in time related measurements.


Photo of Stephane Winnepenninckx Stephane Winnepenninckx