Click here to Skip to main content
13,250,029 members (65,654 online)
Click here to Skip to main content
Add your own
alternative version

Stats

96.4K views
2.6K downloads
55 bookmarked
Posted 25 May 2007
MIT

A C# Implementation of Douglas-Peucker Line Approximation Algorithm

, 6 Jun 2007
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.

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

History

  • Beta 1

License

This article, along with any associated source code and files, is licensed under The MIT License

Share

About the Author

CraigSelbert
Web Developer
United States United States
No Biography provided

You may also be interested in...

Comments and Discussions

 
Questionrejecting recursion + distance calc acceleration Pin
adevder19-Feb-17 0:12
memberadevder19-Feb-17 0:12 
AnswerRe: rejecting recursion + distance calc acceleration Pin
TerrySpiderman21-Mar-17 3:05
professionalTerrySpiderman21-Mar-17 3:05 
Questionto save stack memory with great amount of points and tolerance near zero i prefer to reject recursion Pin
adevder18-Feb-17 1:22
memberadevder18-Feb-17 1:22 
PraiseNice Pin
veen_rp18-Apr-16 19:41
professionalveen_rp18-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

BugIf (first = last) Bug! Pin
Giovani Luigi14-Dec-15 12:44
memberGiovani Luigi14-Dec-15 12:44 
QuestionDouglasPeuckerN() conversion? Pin
cbordeman11-Dec-15 17:42
membercbordeman11-Dec-15 17:42 
AnswerRe: DouglasPeuckerN() conversion? Pin
lorsco0127-Apr-17 7:44
memberlorsco0127-Apr-17 7:44 
GeneralUseful Pin
Dineshkumar_MCA22-Apr-15 2:18
professionalDineshkumar_MCA22-Apr-15 2:18 
QuestionBUG tolerance Pin
Member 1017584518-Feb-15 2:08
memberMember 1017584518-Feb-15 2:08 
QuestionThanks + pruned code Pin
Stoyan Haralampiev23-Oct-14 3:30
memberStoyan Haralampiev23-Oct-14 3:30 
QuestionUsing this algorithm on data from database Pin
Saket Surya2-Jun-14 3:38
memberSaket Surya2-Jun-14 3:38 
QuestionPoint projected on the line but behind the segment? Bug? Pin
Sergiy Tkachuk25-Mar-14 14:31
memberSergiy Tkachuk25-Mar-14 14:31 
QuestionAbout Tolerance Pin
kamlesh Prajapati8-Jan-14 23:55
groupkamlesh Prajapati8-Jan-14 23:55 
QuestionWhy do you create your own Point? Pin
leiyangge3-Jan-14 22:37
memberleiyangge3-Jan-14 22:37 
QuestionLicense Pin
Diego Catalano14-Dec-13 2:42
memberDiego Catalano14-Dec-13 2:42 
Question1 bug, + 1 potential bug Pin
gyuri1023-Apr-12 23:45
membergyuri1023-Apr-12 23:45 
AnswerRe: 1 bug, + 1 potential bug Pin
tplokas26-Mar-13 14:46
membertplokas26-Mar-13 14:46 
QuestionUseful,Thanks! Pin
masy19112-Mar-12 23:43
membermasy19112-Mar-12 23:43 
QuestionGreat Job! Pin
cdrake19-Dec-11 8:32
membercdrake19-Dec-11 8:32 
Generalhow calculate an epsilon value Pin
unravel-the-sky23-May-11 6:52
memberunravel-the-sky23-May-11 6:52 
GeneralSome Issues with your implementation Pin
matthew minke15-Jul-10 11:57
membermatthew minke15-Jul-10 11:57 
GeneralVery useful thanks - Point number reduction (Max Distance relevant tolerance) [modified] Pin
kamyk3-Mar-10 23:05
memberkamyk3-Mar-10 23:05 
GeneralVery useful thanks Pin
dylanhayes17-Nov-09 2:35
memberdylanhayes17-Nov-09 2:35 
GeneralThanks! Pin
Member 337866727-Mar-09 10:28
memberMember 337866727-Mar-09 10:28 
QuestionAnd other functions from Plot Graphic Library? Pin
agorby28-Apr-08 3:28
memberagorby28-Apr-08 3:28 
Generalperpendicular Pin
Alex Bespalov22-Dec-07 21:23
memberAlex Bespalov22-Dec-07 21:23 
Generalperpendicular Pin
Alex Bespalov22-Dec-07 21:21
memberAlex Bespalov22-Dec-07 21:21 
GeneralDo you know offhand if the result of this algorithm is the same/different.... Pin
sherifffruitfly6-Jun-07 12:28
membersherifffruitfly6-Jun-07 12:28 
GeneralRe: Do you know offhand if the result of this algorithm is the same/different.... Pin
CraigSelbert6-Jun-07 16:27
memberCraigSelbert6-Jun-07 16:27 
GeneralCode question Pin
DocJim4-Jun-07 9:46
memberDocJim4-Jun-07 9:46 
GeneralRe: Code question Pin
CraigSelbert6-Jun-07 9:30
memberCraigSelbert6-Jun-07 9:30 
GeneralNeat...Yeah...New algorithm Pin
jconwell25-May-07 5:50
memberjconwell25-May-07 5:50 
GeneralRe: Neat...Yeah...New algorithm Pin
CraigSelbert25-May-07 16:40
memberCraigSelbert25-May-07 16:40 
GeneralTake a look here Pin
D_Guidi25-May-07 4:32
memberD_Guidi25-May-07 4:32 
GeneralRe: Take a look here Pin
CraigSelbert25-May-07 16:49
memberCraigSelbert25-May-07 16:49 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.171114.1 | Last Updated 6 Jun 2007
Article Copyright 2007 by CraigSelbert
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid