Go to top

# A C# Implementation of Douglas-Peucker Line Approximation Algorithm

, 6 Jun 2007
 Rate this:
DP Line approximation algorithm is a well-known method to approximate 2D lines. It is quite fast, O(nlog_2(n)) for a n-points line and can drastically compress a data curve. Here, a fully OOP implementation is given.

## Introduction

I have found multiple implementations of the Douglas-Peucker algorithm but not in any .NET language, so I decided to port it over. Jonathan de Halleux has a wonderful explanation here.

## Background

I needed to reduce polygons size to display on a map based on zoom levels.

## Using the Code

The code included is complete and should run out of the box in Visual Studio 2005.
If it does not, please let me know.

/// <span class="code-SummaryComment"><summary></span>
/// Uses the Douglas Peucker algorithm to reduce the number of points.
/// <span class="code-SummaryComment"></summary></span>
/// <span class="code-SummaryComment"><param name="Points">The points.</param></span>
/// <span class="code-SummaryComment"><param name="Tolerance">The tolerance.</param></span>
/// <span class="code-SummaryComment"><returns></returns></span>
public static List<Point> DouglasPeuckerReduction
(List<Point> Points, Double Tolerance)
{
if (Points == null || Points.Count < 3)
return Points;

Int32 firstPoint = 0;
Int32 lastPoint = Points.Count - 1;
List<Int32> pointIndexsToKeep = new List<Int32>();

//Add the first and last index to the keepers

//The first and the last point cannot be the same
while (Points[firstPoint].Equals(Points[lastPoint]))
{
lastPoint--;
}

DouglasPeuckerReduction(Points, firstPoint, lastPoint,
Tolerance, ref pointIndexsToKeep);

List<Point> returnPoints = new List<Point>();
pointIndexsToKeep.Sort();
foreach (Int32 index in pointIndexsToKeep)
{
}

return returnPoints;
}

/// <span class="code-SummaryComment"><summary></span>
/// Douglases the peucker reduction.
/// <span class="code-SummaryComment"></summary></span>
/// <span class="code-SummaryComment"><param name="points">The points.</param></span>
/// <span class="code-SummaryComment"><param name="firstPoint">The first point.</param></span>
/// <span class="code-SummaryComment"><param name="lastPoint">The last point.</param></span>
/// <span class="code-SummaryComment"><param name="tolerance">The tolerance.</param></span>
/// <span class="code-SummaryComment"><param name="pointIndexsToKeep">The point index to keep.</param></span>
private static void DouglasPeuckerReduction(List<Point>
points, Int32 firstPoint, Int32 lastPoint, Double tolerance,
ref List<Int32> pointIndexsToKeep)
{
Double maxDistance = 0;
Int32 indexFarthest = 0;

for (Int32 index = firstPoint; index < lastPoint; index++)
{
Double distance = PerpendicularDistance
(points[firstPoint], points[lastPoint], points[index]);
if (distance > maxDistance)
{
maxDistance = distance;
indexFarthest = index;
}
}

if (maxDistance > tolerance && indexFarthest != 0)
{
//Add the largest point that exceeds the tolerance

DouglasPeuckerReduction(points, firstPoint,
indexFarthest, tolerance, ref pointIndexsToKeep);
DouglasPeuckerReduction(points, indexFarthest,
lastPoint, tolerance, ref pointIndexsToKeep);
}
}

/// <span class="code-SummaryComment"><summary></span>
/// The distance of a point from a line made from point1 and point2.
/// <span class="code-SummaryComment"></summary></span>
/// <span class="code-SummaryComment"><param name="pt1">The PT1.</param></span>
/// <span class="code-SummaryComment"><param name="pt2">The PT2.</param></span>
/// <span class="code-SummaryComment"><param name="p">The p.</param></span>
/// <span class="code-SummaryComment"><returns></returns></span>
public static Double PerpendicularDistance
(Point Point1, Point Point2, Point Point)
{
//Area = |(1/2)(x1y2 + x2y3 + x3y1 - x2y1 - x3y2 - x1y3)|   *Area of triangle
//Base = v((x1-x2)²+(x1-x2)²)                               *Base of Triangle*
//Area = .5*Base*H                                          *Solve for height
//Height = Area/.5/Base

Double area = Math.Abs(.5 * (Point1.X * Point2.Y + Point2.X *
Point.Y + Point.X * Point1.Y - Point2.X * Point1.Y - Point.X *
Point2.Y - Point1.X * Point.Y));
Double bottom = Math.Sqrt(Math.Pow(Point1.X - Point2.X, 2) +
Math.Pow(Point1.Y - Point2.Y, 2));
Double height = area / bottom * 2;

return height;

//Another option
//Double A = Point.X - Point1.X;
//Double B = Point.Y - Point1.Y;
//Double C = Point2.X - Point1.X;
//Double D = Point2.Y - Point1.Y;

//Double dot = A * C + B * D;
//Double len_sq = C * C + D * D;
//Double param = dot / len_sq;

//Double xx, yy;

//if (param < 0)
//{
//    xx = Point1.X;
//    yy = Point1.Y;
//}
//else if (param > 1)
//{
//    xx = Point2.X;
//    yy = Point2.Y;
//}
//else
//{
//    xx = Point1.X + param * C;
//    yy = Point1.Y + param * D;
//}

//Double d = DistanceBetweenOn2DPlane(Point, new Point(xx, yy));
}

## Points of Interest

The code is not overly complicated. It was fun to port this algorithm, since all I feel I do now a days is hold business' hands to help them try and solve business problems that there is no consensus on.

• Beta 1

## Share

Web Developer
United States
No Biography provided

## You may also be interested in...

### Why “Good Enough” Isn’t Good Enough Anymore for Software Configuration Management

 First Prev Next
 Using this algorithm on data from database Saket Surya 2-Jun-14 2:38
 About Tolerance kamlesh Prajapati 8-Jan-14 22:55
 Why do you create your own Point? leiyangge 3-Jan-14 21:37
 1 bug, + 1 potential bug [modified] gyuri10 23-Apr-12 22:45
 Re: 1 bug, + 1 potential bug tplokas 26-Mar-13 13:46
 Useful,Thanks! masy191 12-Mar-12 22:43
 Great Job! cdrake 19-Dec-11 7:32
 how calculate an epsilon value unravel-the-sky 23-May-11 5:52
 Some Issues with your implementation matthew minke 15-Jul-10 10:57
 Maybe some god modification ?? check that out   tolerance in % of Maximum distance in plot   private static void DouglasPeuckerReduction(List points, Int32 firstPoint, Int32 lastPoint, Double tolerance, Double recursionMaxDistance, ref List pointIndexsToKeep) { Double maxDistance = 0; Int32 indexFarthest = 0;   List indexError = new List(); // count error for new points - take lower error index   List distanceList = new List();   for (Int32 index = firstPoint; index < lastPoint; index++) { Double distance = PerpendicularDistance(points[firstPoint], points[lastPoint], points[index]); distanceList.Add(distance); if (distance > maxDistance) { maxDistance = distance; indexFarthest = index; } } // check if current recursion distance is greater than passed through args if (maxDistance > recursionMaxDistance) recursionMaxDistance = maxDistance;   // check relevant tolerance to recursionMaxDistance if (maxDistance > (recursionMaxDistance * tolerance) / 100 && indexFarthest != 0) { //Add the largest point that exceeds the tolerance pointIndexsToKeep.Add(indexFarthest); DouglasPeuckerReduction(points, firstPoint, indexFarthest, tolerance, recursionMaxDistance, ref pointIndexsToKeep); DouglasPeuckerReduction(points, indexFarthest, lastPoint, tolerance, recursionMaxDistance, ref pointIndexsToKeep); } }   public static List DouglasPeuckerReduction(this List Points, Double Tolerance) {   if (Points == null || Points.Count < 3) return Points;   Int32 firstPoint = 0; Int32 lastPoint = Points.Count - 1; List pointIndexsToKeep = new List();   //Add the first and last index to the keepers pointIndexsToKeep.Add(firstPoint); pointIndexsToKeep.Add(lastPoint);   //The first and the last point can not be the same while (Points[firstPoint].Equals(Points[lastPoint])) { lastPoint--; } // start Approx with 0 recursionMaxDistance DouglasPeuckerReduction(Points, firstPoint, lastPoint, Tolerance,0, ref pointIndexsToKeep);   List returnPoints = new List(); pointIndexsToKeep.Sort(); foreach (Int32 index in pointIndexsToKeep) { returnPoints.Add(Points[index]); } return returnPoints;modified on Thursday, March 4, 2010 12:32 PM
 Very useful thanks dylanhayes 17-Nov-09 1:35
 Thanks! Member 3378667 27-Mar-09 9:28
 And other functions from Plot Graphic Library? agorby 28-Apr-08 2:28
 perpendicular Alex Bespalov 22-Dec-07 20:23
 perpendicular Alex Bespalov 22-Dec-07 20:21
 Code question DocJim 4-Jun-07 8:46
 Re: Code question CraigSelbert 6-Jun-07 8:30
 Neat...Yeah...New algorithm jconwell 25-May-07 4:50
 Re: Neat...Yeah...New algorithm CraigSelbert 25-May-07 15:40
 Take a look here D_Guidi 25-May-07 3:32
 Re: Take a look here CraigSelbert 25-May-07 15:49
 Last Visit: 31-Dec-99 18:00     Last Update: 22-Sep-14 20:59 Refresh 1