Douglas - Peucker line simplification
simplifying a polyline with the Douglas Peucker algorithm.
/**
* Copyright nicoptere ( http://wonderfl.net/user/nicoptere )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/nOo3
*/
package
{
import com.bit101.components.HUISlider;
import flash.display.Sprite;
import flash.display.StageAlign;
import flash.display.StageScaleMode;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.geom.Point;
/**
* @author Nicolas Barradeau
* http://en.nicoptere.net
source http://www.codeproject.com/Articles/18936/A-C-Implementation-of-Douglas-Peucker-Line-Approxi
*/
public class DouglasPeucker extends Sprite
{
private var strokes:Vector.<Stroke>;
private var stroke:Stroke;
private var mouseDown:Boolean;
private var toleranceSlider:HUISlider;
public function DouglasPeucker()
{
stage.scaleMode = StageScaleMode.NO_SCALE;
stage.align = StageAlign.TOP_LEFT;
stage.frameRate = 60;
toleranceSlider = new HUISlider( this, 10, 10, 'tolerance' );
toleranceSlider.minimum = 1;
toleranceSlider.value = 10;
strokes = new Vector.<Stroke>();
stage.addEventListener( MouseEvent.MOUSE_DOWN, onMouseHandler );
stage.addEventListener( MouseEvent.MOUSE_MOVE, onMouseHandler );
stage.addEventListener( MouseEvent.MOUSE_UP, onMouseHandler );
addEventListener( Event.ENTER_FRAME, onEnterFrameHandler );
}
private function onMouseHandler(e:MouseEvent):void
{
if ( e.target != stage ) return;
switch( e.type )
{
case MouseEvent.MOUSE_DOWN:
mouseDown = true;
stroke = new Stroke();
strokes.push( stroke );
break;
case MouseEvent.MOUSE_MOVE:
if ( mouseDown )
{
stroke.add( new Point( mouseX, mouseY ));
}
break;
case MouseEvent.MOUSE_UP:
mouseDown = false;
break;
}
}
private function onEnterFrameHandler(e:Event):void
{
graphics.clear();
graphics.beginFill( 0x333333 );
graphics.drawRect( 0, 0, stage.stageWidth, stage.stageHeight );
graphics.endFill();
for each (var item:Stroke in strokes )
{
graphics.lineStyle( 1, 0x888888 );
item.render( graphics );
graphics.lineStyle( 0, 0x00CC00 );
item.renderOptimized( graphics, toleranceSlider.value );
}
}
/***************************************************************************************
DOUGLAS PEUCKER SIMPLIFICATION
***************************************************************************************/
static public function compute( points:Vector.<Point>, tolerance:Number ):Vector.<Point>
{
if ( points == null || points.length < 3)
return points;
var firstPoint:uint = 0;
var lastPoint:uint = points.length - 1;
var pointIndexsToKeep:Vector.<uint> = Vector.<uint>( [ firstPoint, lastPoint ] );
//The first and the last point cannot be the same
while ( points[ firstPoint ].equals( points[ lastPoint ] ) )
{
lastPoint--;
}
reduce( points, firstPoint, lastPoint, tolerance, pointIndexsToKeep );
var returnPoints:Vector.<Point> = new Vector.<Point>();
pointIndexsToKeep.sort( numericSort );
for each( var index:uint in pointIndexsToKeep )
{
returnPoints.push( points[ index ] );
}
return returnPoints;
}
static private function numericSort( a:uint, b:uint ):int
{
return a < b ? -1 : 1;
}
/// Douglases the peucker reduction.
static private function reduce( points:Vector.<Point>, firstPoint:uint, lastPoint:uint, tolerance:Number, pointIndexsToKeep:Vector.<uint> ):void
{
var maxDistance:Number = 0;
var indexFarthest:uint = 0;
for ( var index:uint = firstPoint; index < lastPoint; index++ )
{
var distance:Number = 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.push( indexFarthest );
reduce(points, firstPoint, indexFarthest, tolerance, pointIndexsToKeep);
reduce(points, indexFarthest, lastPoint, tolerance, pointIndexsToKeep);
}
}
/// The distance of a point from a line made from point1 and point2.
static public function perpendicularDistance( point1:Point, point2:Point, point:Point):Number
{
//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
var area:Number = 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 ) );
var bottom:Number = Math.sqrt( Math.pow( point1.x - point2.x, 2) + Math.pow( point1.y - point2.y, 2 ) );
var height:Number = area / bottom * 2;
return height;
}
}
}
import flash.display.Graphics;
import flash.geom.Point;
internal class Stroke
{
private var _points:Vector.<Point>;
private var optimized:Vector.<Point>;
public function Stroke()
{
points = new Vector.<Point>();
}
public function add( p:Point ):void
{
points.push( p );
}
public function render( g:Graphics ):void
{
if ( points.length == 0 ) return;
g.moveTo( points[ 0 ].x, points[ 0 ].y );
for each (var item:Point in points )
{
g.lineTo( item.x, item.y );
}
}
public function renderOptimized( g:Graphics, tolerance:Number = 10 ):void
{
if ( points.length < 3 ) return;
optimized = DouglasPeucker.compute( points, tolerance );
g.moveTo( optimized[ 0 ].x, optimized[ 0 ].y );
for each (var item:Point in optimized )
{
g.lineTo( item.x, item.y );
}
}
public function get points():Vector.<Point>
{
return _points;
}
public function set points(value:Vector.<Point>):void
{
_points = value;
}
}