13,250,029 members (65,654 online)
alternative version

Stats

96.4K views
55 bookmarked
Posted 25 May 2007

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.

```/// <summary>
/// Uses the Douglas Peucker algorithm to reduce the number of points.
/// </summary>
/// <param name="Points">The points.</param>
/// <param name="Tolerance">The tolerance.</param>
/// <returns></returns>
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;
}

/// <summary>
/// Douglases the peucker reduction.
/// </summary>
/// <param name="points">The points.</param>
/// <param name="firstPoint">The first point.</param>
/// <param name="lastPoint">The last point.</param>
/// <param name="tolerance">The tolerance.</param>
/// <param name="pointIndexsToKeep">The point index to keep.</param>
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);
}
}

/// <summary>
/// The distance of a point from a line made from point1 and point2.
/// </summary>
/// <param name="pt1">The PT1.</param>
/// <param name="pt2">The PT2.</param>
/// <param name="p">The p.</param>
/// <returns></returns>
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 nowadays 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...

 First Prev Next
 Re: rejecting recursion + distance calc acceleration TerrySpiderman21-Mar-17 3:05 TerrySpiderman 21-Mar-17 3:05
 to save stack memory with great amount of points and tolerance near zero i prefer to reject recursion adevder18-Feb-17 1:22 adevder 18-Feb-17 1:22
 Nice veen_rp18-Apr-16 19:41 veen_rp 18-Apr-16 19:41
 Nice concise code. Here's my VB.NET conversion to whom it may concern: ```Public Function GetSimplifyDouglasPeucker(points As List(Of PointD), tolerance As Double) As List(Of PointD) If points Is Nothing OrElse points.Count < 3 Then Return points 'nothing to do Dim pi1 As Integer = 0 Dim pi2 As Integer = points.Count-1 Dim nli As New List(Of Integer) nli.Add(pi1) nli.Add(pi2) 'first and last point cannot be the same While points(pi1).IsCoincident(points(pi2)) pi2 -= 1 End While recurseDouglasPeuckerTrimming(points,pi1,pi2,tolerance,nli) Dim nl As New List(Of PointD) nli.Sort() For Each idx As Integer In nli nl.Add(points(idx)) Next Return nl End Function   Private Sub recurseDouglasPeuckerTrimming(points As List(Of PointD), firstpoint As Integer, lastpoint As Integer, tolerance As Double, ByRef pIndexKeep As List(Of Integer)) Dim maxDist As Double = 0 Dim idxFarthest As Integer = 0 Dim distance As Double = 0 For i As Integer = firstpoint To lastpoint-1 distance = GetTriangleHeight(points(firstPoint),points(lastPoint),points(i)) If distance > maxDist Then maxDist = distance idxFarthest = i End If Next If maxDist > tolerance AndAlso idxFarthest <> 0 Then 'Add the largest point that exceeds the tolerance pIndexKeep.Add(idxFarthest) 'recurse recurseDouglasPeuckerTrimming(points,firstpoint,idxFarthest,tolerance,pIndexKeep) recurseDouglasPeuckerTrimming(points,idxFarthest,lastpoint,tolerance,pIndexKeep) End If End Sub   Public Function GetTriangleArea(base1 As PointD, base2 As PointD, apex As PointD) As Double Try Return Math.Abs(.5*(base1.X*base2.Y + base2.X*apex.Y + apex.X*base1.Y - base2.X*base1.Y - apex.X*base2.Y - base1.X*apex.Y)) Catch Return Double.NaN End Try End Function   Public Function GetTriangleBase(base1 As PointD, base2 As PointD, apex As PointD) As Double Try Return ((base1.X-base2.X)^2 + (base1.Y-base2.Y)^2)^0.5 Catch Return Double.NaN End Try End Function   Public Function GetTriangleHeight(base1 As PointD, base2 As PointD, apex As PointD) As Double Return GetTriangleArea(base1,base2,apex)/GetTriangleBase(base1,base2,apex)*2 End Function```
 If (first = last) Bug! Giovani Luigi14-Dec-15 12:44 Giovani Luigi 14-Dec-15 12:44
 DouglasPeuckerN() conversion? cbordeman11-Dec-15 17:42 cbordeman 11-Dec-15 17:42
 Re: DouglasPeuckerN() conversion? lorsco0127-Apr-17 7:44 lorsco01 27-Apr-17 7:44
 Useful Dineshkumar_MCA22-Apr-15 2:18 Dineshkumar_MCA 22-Apr-15 2:18
 BUG tolerance Member 1017584518-Feb-15 2:08 Member 10175845 18-Feb-15 2:08
 Thanks + pruned code Stoyan Haralampiev23-Oct-14 3:30 Stoyan Haralampiev 23-Oct-14 3:30
 Using this algorithm on data from database Saket Surya2-Jun-14 3:38 Saket Surya 2-Jun-14 3:38
 Point projected on the line but behind the segment? Bug? Sergiy Tkachuk25-Mar-14 14:31 Sergiy Tkachuk 25-Mar-14 14:31
 About Tolerance kamlesh Prajapati8-Jan-14 23:55 kamlesh Prajapati 8-Jan-14 23:55
 Why do you create your own Point? leiyangge3-Jan-14 22:37 leiyangge 3-Jan-14 22:37
 License Diego Catalano14-Dec-13 2:42 Diego Catalano 14-Dec-13 2:42
 1 bug, + 1 potential bug gyuri1023-Apr-12 23:45 gyuri10 23-Apr-12 23:45
 Re: 1 bug, + 1 potential bug tplokas26-Mar-13 14:46 tplokas 26-Mar-13 14:46
 Useful,Thanks! masy19112-Mar-12 23:43 masy191 12-Mar-12 23:43
 Great Job! cdrake19-Dec-11 8:32 cdrake 19-Dec-11 8:32
 how calculate an epsilon value unravel-the-sky23-May-11 6:52 unravel-the-sky 23-May-11 6:52
 Some Issues with your implementation matthew minke15-Jul-10 11:57 matthew minke 15-Jul-10 11:57
 Very useful thanks - Point number reduction (Max Distance relevant tolerance) [modified] kamyk3-Mar-10 23:05 kamyk 3-Mar-10 23:05
 Very useful thanks dylanhayes17-Nov-09 2:35 dylanhayes 17-Nov-09 2:35
 Thanks! Member 337866727-Mar-09 10:28 Member 3378667 27-Mar-09 10:28
 And other functions from Plot Graphic Library? agorby28-Apr-08 3:28 agorby 28-Apr-08 3:28
 perpendicular Alex Bespalov22-Dec-07 21:23 Alex Bespalov 22-Dec-07 21:23
 perpendicular Alex Bespalov22-Dec-07 21:21 Alex Bespalov 22-Dec-07 21:21
 Do you know offhand if the result of this algorithm is the same/different.... sherifffruitfly6-Jun-07 12:28 sherifffruitfly 6-Jun-07 12:28
 Re: Do you know offhand if the result of this algorithm is the same/different.... CraigSelbert6-Jun-07 16:27 CraigSelbert 6-Jun-07 16:27
 Code question DocJim4-Jun-07 9:46 DocJim 4-Jun-07 9:46
 Re: Code question CraigSelbert6-Jun-07 9:30 CraigSelbert 6-Jun-07 9:30
 Neat...Yeah...New algorithm jconwell25-May-07 5:50 jconwell 25-May-07 5:50
 Re: Neat...Yeah...New algorithm CraigSelbert25-May-07 16:40 CraigSelbert 25-May-07 16:40
 Take a look here D_Guidi25-May-07 4:32 D_Guidi 25-May-07 4:32
 Re: Take a look here CraigSelbert25-May-07 16:49 CraigSelbert 25-May-07 16:49
 Last Visit: 31-Dec-99 19:00     Last Update: 19-Nov-17 11:56 Refresh 1