## Douglas-Peucker Algorithm implementation in C#

Douglas-Peucker algorithm is an error bounded sequence simplication. It is used for compressing trajectory, roadnetwork, etc. It's main idea can be shown as the following picture [1].

I implement the Douglas-Peucker algorithm using C#.

Here is my code. (Github: https://github.com/IrisLoveLeo/DouglasPeucker )

```using System;
using System.Collections.Generic;
using System.Linq;

namespace Statistics
{
public class DouglasPeucker
{
private List<Point> _pointsList;
private double _errorBound; // degree
public DouglasPeucker(List<Point> pointsList, double errorBound)
{
_pointsList = new List<Point>();
if (pointsList != null)
{
Point last = pointsList.First();

for (int i = 1; i < pointsList.Count; i++)
{
if (!last.Equals(pointsList[i]))
{
last = pointsList[i];
}
else
{
Console.WriteLine("丢弃相同的点：" + last);
}
}
}
_errorBound = errorBound;
}

public List<Point> Compress()
{
if (_pointsList == null || _pointsList.Count <= 2)
{
return _pointsList;
}

List<Point> result = CompressHelper(_pointsList);

return result;
}

private List<Point> CompressHelper(List<Point> pointsList)
{
if (pointsList.Count < 2)
{
return pointsList;
}

List<Point> result = new List<Point>();

// 有可能是polygon
if (pointsList.First().Equals(pointsList.Last()))
{
var r1 = CompressHelper(pointsList.GetRange(0, pointsList.Count / 2));
var r2 = CompressHelper(pointsList.GetRange(pointsList.Count / 2, pointsList.Count - pointsList.Count / 2));
return result;
}

Line line = new Line() { p1 = pointsList.First(), p2 = pointsList.Last() };

double maxDistance = 0;
int maxIndex = 0;

for (int i = 1; i < pointsList.Count - 1; i++)
{
var distance = Distance(pointsList[i], line);
if (distance > maxDistance)
{
maxDistance = distance;
maxIndex = i;
}
}

if (maxDistance <= _errorBound)
{
}
else
{
var r1 = CompressHelper(pointsList.GetRange(0, maxIndex));
var r2 = CompressHelper(pointsList.GetRange(maxIndex + 1, pointsList.Count - maxIndex - 1));
}

return result;
}

private double Distance(Point p, Line line)
{
var p1 = line.p1;
var p2 = line.p2;
return Math.Abs(
((p2.Lng - p1.Lng) * p.Lat + (p1.Lat - p2.Lat) * p.Lng + (p1.Lng - p2.Lng) * p1.Lat + (p2.Lat - p1.Lat) * p1.Lng) /
Math.Sqrt((p2.Lng - p1.Lng) * (p2.Lng - p1.Lng) + (p1.Lat - p2.Lat) * (p1.Lat - p2.Lat))
);
}
}

public class Point
{
public double Lat { set; get; }
public double Lng { set; get; }
public bool Equals(Point p)
{
return Lat == p.Lat && Lng == p.Lng;
}
override
public string ToString()
{
return "[" + Lat + "," + Lng + "]";
}
}

class Line
{
public Point p1 { set; get; }
public Point p2 { set; get; }
}
}```

Here is the effect of the DP on road network compress.

Before Compress:

After Compress:

The road network file size has been reduced to half.

[1] Lin X, Ma S, Zhang H, et al. One-pass error bounded trajectory simplification[J]. Proceedings of the VLDB Endowment, 2017, 10(7): 841-852.