Douglas Peucker Reduction

Monkey Forums/Monkey Code/Douglas Peucker Reduction

CopperCircle(Posted 2012) [#1]
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