Hi, here is my conversion of a C# Douglas Peucker Reduction, the code is a bit messy but it works and allows you to reduce the number of points in a path.
I am using it with my Box2D level editor to create simplified polys, draw a line with the mouse and use left/right arrow keys to change the Tolerance.
Strict
Import mojo
Global pointIndexsToKeep:IntList = New IntList
Class MyApp Extends App
Field calculateDouglasPeuckerReduction:Bool = False
Field drawingPoints:List<Point> = New List<Point>
Field drawingPoints2:List<Point> = New List<Point>
Field pointLast:Point
Field drawOrigional:Bool
Field drawSimplified:Bool
Field process:Bool
Field reset:Bool
Field lblOriginal:String
Field lblSimplified:String
Field nudTolerance:Float=5.0
Field oldMouseX:Int
Field oldMouseY:Int
Method OnCreate:Int()
SetUpdateRate(60)
Return 0
End Method
Method OnUpdate:Int()
If MouseDown()=0
calculateDouglasPeuckerReduction = True
reset=True
EndIf
If (drawingPoints.Count() > 2 And process=True)
drawOrigional=True
lblOriginal = drawingPoints.Count()
If calculateDouglasPeuckerReduction=True
Local points:List<Point> = DouglasPeuckerReduction(drawingPoints, nudTolerance)
drawingPoints2 = New List<Point>
For Local point:Point = EachIn points
drawingPoints2.AddLast(New Point(Int(point.x), Int(point.y)))
Next
drawSimplified=True
lblSimplified = drawingPoints2.Count()
process=False
Else
drawSimplified=False
EndIf
EndIf
If MouseDown(MOUSE_LEFT)
If reset=True
drawingPoints.Clear()
drawingPoints2.Clear()
pointIndexsToKeep.Clear()
reset=False
EndIf
If oldMouseX<>MouseX() Or oldMouseY<>MouseY()
drawingPoints.AddLast(New Point(MouseX(), MouseY()))
process=True
Else
calculateDouglasPeuckerReduction = False
Endif
oldMouseX=MouseX() ; oldMouseY=MouseY()
EndIf
If KeyHit(KEY_LEFT)
nudTolerance=nudTolerance-0.5
pointIndexsToKeep.Clear()
process=True
EndIf
If KeyHit(KEY_RIGHT)
nudTolerance=nudTolerance+0.5
pointIndexsToKeep.Clear()
process=True
EndIf
Return 0
End Method
Method OnRender:Int()
Cls 64, 96, 160
If drawOrigional=True
SetColor 0,0,0
For Local pointDraw:Point = EachIn drawingPoints
If pointLast<>null
DrawThickLine(pointLast.x, pointLast.y, pointDraw.x, pointDraw.y,5)
EndIf
pointLast=pointDraw
Next
pointLast=null
EndIf
If drawSimplified=True
SetColor 255,0,0
For Local pointDraw:Point = EachIn drawingPoints2
DrawCircle(pointDraw.x, pointDraw.y, 4)
If pointLast<>null
DrawLine(pointLast.x, pointLast.y, pointDraw.x, pointDraw.y)
EndIf
pointLast=pointDraw
Next
pointLast=null
EndIf
SetColor 255,255,255
DrawText("Origional:"+lblOriginal,10,10)
DrawText("Simplified:"+lblSimplified,10,30)
DrawText("Tolerance:"+nudTolerance,10,50)
Return 0
End Method
End Class
Function Main:Int()
New MyApp()
Return 0
End Function
'Draws thick line, rounded ends optional by NoOdle
Function DrawThickLine:Void( x1 : Float, y1 : Float, x2 : Float, y2 : Float, thickness : Float = 2.0, rounded : Bool = False )
Local dx : Float = x2 - x1
Local dy : Float = y2 - y1
Local d : Float = Sqrt( dx * dx + dy * dy )
Local vx : Float = dx / d
Local vy : Float = dy / d
Local nx : Float = vy
Local ny : Float = -vx
Local points : Float[ 8 ]
points[ 0 ] = x1 + ( nx * ( thickness / 2.0 ))
points[ 1 ] = y1 + ( ny * ( thickness / 2.0 ))
points[ 2 ] = x1 + ( -nx * ( thickness / 2.0 ))
points[ 3 ] = y1 + ( -ny * ( thickness / 2.0 ))
points[ 4 ] = x2 + ( -nx * ( thickness / 2.0 ))
points[ 5 ] = y2 + ( -ny * ( thickness / 2.0 ))
points[ 6 ] = x2 + ( nx * ( thickness / 2.0 ))
points[ 7 ] = y2 + ( ny * ( thickness / 2.0 ))
DrawPoly( points )
If rounded = True
DrawEllipse x1, y1, thickness / 2.0, thickness / 2.0
DrawEllipse x2, y2, thickness / 2.0, thickness / 2.0
Endif
End Function
'Create the point class
Class Point
Field x:Float
Field y:Float
Method New(X:Float,Y:Float)
x = X
y = Y
End
Method Equals:Bool(p:Point)
If x = p.x And y = p.y
Return True
Else
Return False
EndIf
End
End
'Uses the Douglas Peucker algorithim to reduce the number of points.
Function DouglasPeuckerReduction:List<Point>(Points:List<Point>, Tolerance:Float)
If (Points=Null Or Points.Count() < 3) Then Return Points
Local firstPoint:Int = 0
Local lastPoint:Int = Points.Count() - 1
'Add the first and last index to the keepers
pointIndexsToKeep.AddLast(firstPoint);
pointIndexsToKeep.AddLast(lastPoint);
'The first and the last point can not be the same
Local arrayPoints:Point[]=Points.ToArray()
While (arrayPoints[firstPoint].Equals(arrayPoints[lastPoint]))
lastPoint=lastPoint-1
Wend
DouglasPeuckerProcess(Points, firstPoint, lastPoint, Tolerance)
Local returnPoints:List<Point> = New List<Point>()
pointIndexsToKeep.Sort()
For Local index:Int = EachIn pointIndexsToKeep
returnPoints.AddLast(arrayPoints[index])
Next
Return returnPoints
End Function
'Douglases the peucker reduction.
Function DouglasPeuckerProcess:Void(points:List<Point>, firstPoint:Int, lastPoint:Int, tolerance:Float)
Local maxDistance:Float = 0
Local indexFarthest:Int = 0
Local arrayPoints:Point[]=points.ToArray()
For Local index:Int = firstPoint To lastPoint-1
Local distance:Float = PerpendicularDistance(arrayPoints[firstPoint], arrayPoints[lastPoint], arrayPoints[index])
If (distance > maxDistance)
maxDistance = distance
indexFarthest = index
Endif
Next
If (maxDistance > tolerance And indexFarthest <> 0)
'Add the largest point that exceeds the tolerance
pointIndexsToKeep.AddLast(indexFarthest)
DouglasPeuckerProcess(points, firstPoint, indexFarthest, tolerance)
DouglasPeuckerProcess(points, indexFarthest, lastPoint, tolerance)
EndIf
End Function
'The distance of a point from a line made from point1 and point2.
Function PerpendicularDistance:Float(Point1:Point, Point2:Point, Point0:Point)
Local area:Float = Abs(0.5 * (Point1.x * Point2.y + Point2.x * Point0.y + Point0.x * Point1.y - Point2.x * Point1.y - Point0.x * Point2.y - Point1.x * Point0.y))
Local bottom:Float = Sqrt(Pow(Point1.x - Point2.x, 2) + Pow(Point1.y - Point2.y, 2))
Local height:Float = area / bottom * 2
Return height
End Function
|
