A New Variant of Douglas–Peucker Algorithm (1/4) [Introduction]

The Ramer-Douglas-Peucker is a polyline simplification algorithm that uses a point-to-edge (point-to-line) distance tolerance “Epsilon”. The algorithm starts with a crude simplification that is the single edge (line) joining the first and last vertices (points) of the original polyline (polyline needed to be simplified). There is a variant of this algorithm already that allows it to produce a polyline with a fixed number of vertices “N”.

From software points of view, sometimes it’s preferred to have a fixed-size array to store a polyline vertices. Thus, the variant version of the Douglas-Peucker algorithm, that produces a fixed number of vertices “N”, is more convenient. However, from applications point of view, it doesn’t make sense to describe a simple polyline (rectangular area for example) with the same number of vertices that describe a complex-shaped one. This is why I’ve introduced my own version of the Douglas-Peucker algorithm, which I call a “Regularized” version.

My modified algorithm takes two pieces of data as inputs. The first is a predefined maximum number of vertices "N". The second is a tolerance "Epsilon". The algorithm returns n ≤ N vertices; it excludes the vertices that over-fit according to the predefined tolerance "Epsilon”. Those are the vertices that would have not been selected using the original Douglas-Peucker algorithm if it runs using the given "epsilon". A sample results of my variant of the Douglas–Peucker algorithm are shown in the coming table.

(A) N=50 , Epsilon=1.5 :	(B) N=50 , Epsilon=1.0 :
(C) N=100 , Epsilon=1.5 :	(D) N=10 , Epsilon=1.5 :

In the previous table, polyline (B) contains more vertices than polyline (A), because decreasing Epsilon allows more vertices to produce max edge distances higher than Epsilon, while these points still produce a polyline with number of vertices less than N. The resulted polyline in (C) is the same as (A), because increasing N, while having the same Epsilon will not produce new vertices that fits that Epsilon. Polyline in (D) contains fewer vertices than the polyline in (A), because the number of vertices in polyline (A) is greater than the N in (D).

In a coming posts, I will post the algorithms and MATLAB implementations for the three configurations:
- Original Douglas-Peucker algorithm.
- Variant of Douglas-Peucker algorithm (fixed number of simplified vertices "N").
- My Variant of Douglas-Peucker algorithm (with "N" and a tolerance "Epsilon").