Used for taking an array of points, such as in a polygon, and reducing the number of points (e.g. simplifying the polygon). Could also use to simplify any sort of line made of points, say for paths or gestures or something like that.
Ported from http://karthaus.nl/rdp/ and a bit of Wikipedia. That link also has a nifty demo of the algorithm. Adjust epsilon to get different degrees of optimization.
Assumes you have a Vector or Point class with .X and .Y in it.
Function DouglasPeucker:Vector[] (pointList:Vector[], epsilon:Float)
' implemented as a port from here: http://karthaus.nl/rdp/
Local dmax:Float = 0
Local index:Int = -1
Local endPoint:Int = pointList.Length - 1
If pointList.Length < 3
Return pointList
EndIf
For Local i = 1 Until endPoint
Local d:Float = findPerpendicularDistance(pointList[i], pointList[0], pointList[endPoint])
If (d > dmax)
index = i
dmax = d
EndIf
Next
Local resultList:Vector[]
If (dmax > epsilon)
' recurse
Local results1:Vector[] = DouglasPeucker(pointList[ .. index + 1], epsilon)
Local results2:Vector[] = DouglasPeucker(pointList[index ..], epsilon)
' build the results list
resultList = Concat(results1, results2)
Else
resultList =[pointList[0], pointList[endPoint]]
EndIf
Return resultList
End
Function Concat:Vector[] (arr1:Vector[], arr2:Vector[])
Local offset:Int = arr1.Length - 1
arr1 = arr1.Resize(offset + arr2.Length)
For Local i = 0 Until arr2.Length
arr1[i + offset] = arr2[i]
Next
Return arr1
End
Function findPerpendicularDistance:Float(p:Vector, p1:Vector, p2:Vector)
Local result:Float
Local slope:Float
Local intercept:Float
If (p1.X = p2.X)
result = Abs(p.X - p1.X)
Else
slope = (p2.Y - p1.Y) / (p2.X - p1.X)
intercept = p1.Y - (slope * p1.X)
result = Abs(slope * p.X - p.Y + intercept) / Sqrt(Pow(slope, 2) + 1)
EndIf
Return Abs(result)
End
| 
