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

developer/sdksamples/polylinesimplification.txt ยท Last modified: 2020/08/14 (external edit)