Summary: An implementation of the Douglas~Peucker polyline reduction algorithm

The Douglas~Peucker algorithm simplifies a polyline by removing vertices that do not contribute (sufficiently) to the overall shape. It is a recursive process which finds the most important vertices for every given reduction:

First, the most basic reduction is assumed. A single segment connecting the beginning and end of the original polyline. When the recursion starts, the most significant vertex (the most distant) for this segment is found. When the distance from this vertex to the segment exceeds the reduction tolerance, the segment splits into two sub-segments, each inheriting a subset of the original vertex list:

Each segment continues to subdivide until none of the vertices in the local list are further away than the tolerance value:

Public Shared Function DP_Reduction(ByVal P As OnPolyline, ByVal tolerance As Double) As OnPolyline
    Dim N As Int32 = P.Count() - 1
    If N < 5 Then Return P 
 
    Dim vertex_tag(N) As Boolean 
    vertex_tag(0) = True
    vertex_tag(N) = True
    For i As Int32 = 1 To P.Count() - 2
        vertex_tag(i) = False
    Next
 
    DP_Recursion(P, vertex_tag, tolerance, 0, N)
 
    Dim nPath As New OnPolyline
    nPath.SetCapacity(N + 1)
 
    For i As Int32 = 0 To vertex_tag.GetUpperBound(0)
        If vertex_tag(i) Then nPath.Append(P(i))
    Next
 
    Return nPath
End Function

Private Shared Sub DP_Recursion(ByVal P As OnPolyline, ByVal vertex_tag As Boolean(), _
                                ByVal tolerance As Double, ByVal A As Int32, ByVal B As Int32)
    If (B <= A + 1) Then Return
 
    Dim dp_segment As New OnLine(P(A), P(B))
    Dim max_dist As Double = 0.0
    Dim local_dist As Double
    Dim max_index As Int32 = A
 
    For i As Int32 = A + 1 To B - 1
        local_dist = dp_segment.DistanceTo(P(i))
        If local_dist > max_dist Then
            max_dist = local_dist
            max_index = i
        End If
    Next
 
    If max_dist > tolerance Then
        vertex_tag(max_index) = True
 
        DP_Recursion(P, vertex_tag, tolerance, A, max_index)
        DP_Recursion(P, vertex_tag, tolerance, max_index, B)
    End If
End Function

Contact the author