Site Tools

How to: Simplify Polylines


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:


Main Function

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
    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))
    Return nPath
End Function

Recursive component

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
    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

developer/sdksamples/polylinesimplification.txt ยท Last modified: 2016/01/12 by sandy