A C# Implementation of Douglas-Peucker Line Approximation Algorithm

, 6 Jun 2007 CPOL
 Rate this:
Please Sign up or sign in to vote.
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
pointIndexsToKeep.Add(firstPoint);
pointIndexsToKeep.Add(lastPoint);

//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)
{
returnPoints.Add(Points[index]);
}

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
pointIndexsToKeep.Add(indexFarthest);

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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Web Developer
United States
No Biography provided

Comments and Discussions

 First PrevNext
 Thanks + pruned code Stoyan Haralampiev 23-Oct-14 3:30
 Using this algorithm on data from database Saket Surya 2-Jun-14 3:38
 I want to use this algorithm to reduce data points on a plot where data is fetched from database to plot. Can someone give an efficient way to do this? My table has records in millions, and I would like to fetch only a few thousand to plot the chart.
 About Tolerance kamlesh Prajapati 8-Jan-14 23:55
 Why do you create your own Point? leiyangge 3-Jan-14 22:37
 License Diego Catalano 14-Dec-13 2:42
 1 bug, + 1 potential bug [modified] gyuri10 23-Apr-12 23:45
 Re: 1 bug, + 1 potential bug tplokas 26-Mar-13 14:46
 Useful,Thanks! masy191 12-Mar-12 23:43
 Great Job! cdrake 19-Dec-11 8:32
 how calculate an epsilon value unravel-the-sky 23-May-11 6:52
 Some Issues with your implementation matthew minke 15-Jul-10 11:57
 Very useful thanks dylanhayes 17-Nov-09 2:35
 Thanks! Member 3378667 27-Mar-09 10:28
 And other functions from Plot Graphic Library? agorby 28-Apr-08 3:28
 perpendicular Alex Bespalov 22-Dec-07 21:23
 perpendicular Alex Bespalov 22-Dec-07 21:21
 Code question DocJim 4-Jun-07 9:46
 Re: Code question CraigSelbert 6-Jun-07 9:30
 Neat...Yeah...New algorithm jconwell 25-May-07 5:50
 Re: Neat...Yeah...New algorithm CraigSelbert 25-May-07 16:40
 Take a look here D_Guidi 25-May-07 4:32
 Last Visit: 31-Dec-99 19:00     Last Update: 25-Dec-14 23:10 Refresh 12 Next »

General    News    Suggestion    Question    Bug    Answer    Joke    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.141223.1 | Last Updated 6 Jun 2007
Article Copyright 2007 by CraigSelbert
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid