Optimized Line Drawing

Many months ago, I developed an algorithm for optimizing line drawings for another project I was doing. The idea is, you are drawing some lines with the mouse. Via an enterFrame or mouseMove, or even a timer or interval, you sample the mouse position and add a point to the array of points, and draw a line through all the points. The problem is that you can wind up with a huge amount of points. Far more than is really needed to display the shape.

One simple way of dealing with this is to check the distance from the most recently sampled point to the last one. If it’s greater than a certain distance, say 10 pixels, then you add the point, if not, you don’t. That helps somewhat, but has a few problems. One, it can make for a bad user experience if the user is trying to draw an accurate line to a particular spot, he or she may not be able to. Two, on particularly curvy drawings, it can come out looking very segmented. And three, on long straight lines, you are still going to get a whole lot of extra points where really you just need the start and end position.

My strategy for dealing with this is to just let the user draw the line and take in every point. Actually, I still use a bit of the distance based algorithm, but keep it at a low distance so it’s not so bad but still does a first pass at optimization. When the mouse is released, it loops through the array of points, comparing the angle between successive pairs of points. If the angle between points A and B and points A and C is within a certain tolerance, it says, OK, those three points are in a straight line, and removes point B. It loops through the whole array of points iteratively until there is no more optimization to be done. I then draws the newly optimized array of points. It sounds pretty intensive, but in practice it’s pretty quick and can do some amazing optimization while still keeping the basic look and feel of what was drawn.

Here’s a demo. Just scribble below, and then move the slider around. I find that a tolerance of .2 to .3 works well for straight, angular drawings. Lower values for more curved drawings.

[kml_flashembed movie=”http://www.bit-101.com/misc/optidraw.swf” height=”400″ width=”550″ /]

This was all done right on the timeline in Flash CS3, so it is not the most polished code. It also makes use of the standard slider component from CS3, on stage with instance name slider, settings: direction=vertical, liveDragging=true, max=1, min=0, snap and tick intervals=.01, value=0. Oh, and a simple text field named pcount.

[as]import flash.geom.Point;
import flash.events.MouseEvent;

var points:Array;
var origPoints:Array = new Array();
stage.addEventListener(MouseEvent.MOUSE_DOWN, onMouseDown);
slider.addEventListener(Event.CHANGE, onChange);

function onMouseDown(event:MouseEvent):void
{
if(event.target != stage) return;
origPoints = new Array();
var p:Point = new Point(mouseX, mouseY);
origPoints.push(p);
graphics.clear();
graphics.lineStyle(1);
graphics.moveTo(p.x, p.y);
drawPoint(p);
stage.addEventListener(MouseEvent.MOUSE_MOVE, onMouseMove);
stage.addEventListener(MouseEvent.MOUSE_UP, onMouseUp);
}

function onMouseUp(event:MouseEvent):void
{
stage.removeEventListener(MouseEvent.MOUSE_MOVE, onMouseMove);
stage.removeEventListener(MouseEvent.MOUSE_UP, onMouseUp);

drawOpt();
}

function drawOpt():void
{
var orig:Number = origPoints.length;
pcount.text = “opt level: ” + slider.value.toString() + “. original: ” + orig + ” points. “;
optimize();
var percent:Number = Math.round(points.length / orig * 10000) / 100;
pcount.appendText(“optimized: ” + points.length + ” points. (” + percent + “%)”);
graphics.clear();
graphics.lineStyle(1);
graphics.moveTo(points[0].x, points[0].y);
for(var i:Number = 1; i < points.length; i++) { graphics.lineTo(points[i].x, points[i].y); drawPoint(points[i]); } } function onMouseMove(event:MouseEvent):void { draw(); } function onChange(event:Event):void { if(origPoints.length <= 0) return; optimize(); drawOpt(); } function draw():void { var p:Point = new Point(mouseX, mouseY); if(distBetween(p, origPoints[origPoints.length-1]) > 10)
{
origPoints.push(p);
graphics.lineTo(p.x, p.y);
drawPoint(p);
}
}

function angleBetween(p0:Point, p1:Point):Number
{
var dx:Number = p1.x – p0.x;
var dy:Number = p1.y – p0.y;
return Math.atan2(dy, dx);
}

function distBetween(p0:Point, p1:Point):Number
{
var dx:Number = p1.x – p0.x;
var dy:Number = p1.y – p0.y;
return Math.sqrt(dx * dx + dy * dy);
}

function drawPoint(p:Point):void
{
graphics.lineStyle(1, 0xff0000);
graphics.moveTo(p.x – 2, p.y – 2);
graphics.lineTo(p.x + 2, p.y + 2);
graphics.moveTo(p.x + 2, p.y – 2);
graphics.lineTo(p.x +- 2, p.y + 2);
graphics.lineStyle(1);
graphics.moveTo(p.x, p.y);
}

function optimize():void
{
points = origPoints.slice();
var optimized:Boolean = false;
while(!optimized)
{
optimized = true;
for(var i:Number = 0; i < points.length - 2; i++) { var p0:Point = points[i]; var p1:Point = points[i + 1]; var p2:Point = points[i + 2]; var angleA:Number = angleBetween(p0, p1); var angleB:Number = angleBetween(p0, p2); var distA:Number = distBetween(p0, p1); var distB:Number = distBetween(p0, p2); if((Math.abs(angleB - angleA) < slider.value) && (distB > distA))
{
optimized = false;
points.splice(i + 1, 1);
}
}
}
if(distBetween(points[0], points[points.length-1]) < 50) { points[points.length - 1] = points[0]; } }[/as] I have no doubt that better algorithms exist for doing these things, as they are already in use in various drawing programs - even right in Flash (the smooth and straighten tools). I already know that this could be optimized and it does some undesirable things - removing some point you wouldn't expect, and leaving others. So consider it experimental. Play with it, improve it, etc.