# .NET

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

## Introduction

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

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