Closest Point Bezier Curve

<<< DIRTY GEOMETRY >>>

Computes the closest point to a bezier curve

@author Andre Michelle

forked:5
favorite:34
lines:236
license : see code comments
modified : 2009-11-13 23:35:38

Embed: Tweet

package  
{
	import flash.events.MouseEvent;
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.geom.Point;
	import flash.text.TextField;
	import flash.text.TextFieldAutoSize;
	import flash.text.TextFormat;

/**
	 * <<< DIRTY GEOMETRY >>>
	 * 
	 * Computes the closest point to a bezier curve
	 * 
	 * @author Andre Michelle
	 */
	[SWF(width='465',height='490',frameRate='50',backgroundColor='0x202020')]
	public class BezierClosestPoint extends Sprite 
	{
		private const point: Point = new Point();
		
		private const pointA: AnchorPoint = new AnchorPoint();
		private const pointB: AnchorPoint = new AnchorPoint();
		private const pointC: AnchorPoint = new AnchorPoint();
		private const pointD: AnchorPoint = new AnchorPoint();

private const EPSILON: Number = 1e-8;
		private const R: Vector.<Number> = new Vector.<Number>( 3, true );
		
		private const textField: TextField = new TextField();
		
		private var dragAnchor: AnchorPoint;

public function BezierClosestPoint()
		{
			pointA.x = 140.0;
			pointA.y = 140.0;
			addChild( pointA );

pointB.x = 300;
			pointB.y = 300;
			addChild( pointB );

pointC.x = 200;
			pointC.y = 320;
			addChild( pointC );

pointD.x = 120;
			pointD.y = 300;
			addChild( pointD );
			
			textField.mouseEnabled = false;
			textField.selectable = false;
			textField.autoSize = TextFieldAutoSize.LEFT;
			textField.defaultTextFormat = new TextFormat( 'Arial', 10, 0x999999 );
			addChild( textField );

addEventListener( Event.ENTER_FRAME, enterFrame );
			addEventListener( MouseEvent.MOUSE_DOWN, mouseDown );
			addEventListener( MouseEvent.MOUSE_UP, mouseUp );
		}
		
		private function mouseDown( event: MouseEvent ): void
		{
			dragAnchor = event.target as AnchorPoint;
		}

private function mouseUp( event: MouseEvent ): void
		{
			dragAnchor = null;
		}

private function enterFrame( event: Event ): void
		{
			if( dragAnchor == pointA )
			{
				pointA.x = mouseX;
				pointA.y = mouseY;
			}
			else
			if( dragAnchor == pointB )
			{
				pointB.x = mouseX;
				pointB.y = mouseY;
			}
			else
			if( dragAnchor == pointC )
			{
				pointC.x = mouseX;
				pointC.y = mouseY;
			}
			else
			if( dragAnchor == pointD )
			{
				pointD.x = mouseX;
				pointD.y = mouseY;
			}
			
			var x0: Number = pointA.x;
			var y0: Number = pointA.y;
			var x1: Number = pointC.x;
			var y1: Number = pointC.y;
			var x2: Number = pointB.x;
			var y2: Number = pointB.y;

graphics.clear();
			graphics.lineStyle( 0, 0xFF9900 );
			graphics.moveTo( x0, y0 );
			graphics.curveTo( x1, y1, x2, y2 );
			
			point.x = pointD.x;
			point.y = pointD.y;

var distance: Number = getClosestPoint( x0, y0, x1, y1, x2, y2, point );
			
			textField.text = 'Distance to bezier: ' + distance.toFixed( 2 );

graphics.lineStyle( 0, 0x777777 );
			graphics.moveTo( pointD.x, pointD.y );
			graphics.lineTo( point.x, point.y );
		}

private function getClosestPoint( x0: Number, y0: Number, x1: Number, y1: Number, x2: Number, y2: Number, point: Point ): Number
		{
			var ax: Number;
			var ay: Number;
			var dx: Number;
			var dy: Number;
			var px: Number = point.x;
			var py: Number = point.y;
			var dd: Number = Number.MAX_VALUE;

var t: Number;

var i: int = 0;
			var n: int = getClosestT( x0, y0, x1, y1, x2, y2, px, py );

for( ; i < n ; ++i )
			{
				t = R[i];

if( t <= 0.0 )
				{
					ax = x0;
					ay = y0;
				}
				else
				if( t >= 1.0 )
				{
					ax = x2;
					ay = y2;
				}
				else
				{
					ax = eval( x0, x1, x2, t );
					ay = eval( y0, y1, y2, t );
				}

dx = px - ax;
				dy = py - ay;

if( dx * dx + dy * dy < dd )
				{
					point.x = ax;
					point.y = ay;

dd = dx * dx + dy * dy;
				}
			}

return Math.sqrt( dd );
		}
		
		private function eval( v0: Number, v1: Number, v2: Number, t: Number ): Number
		{
			var t1: Number = 1.0 - t;

return v0 * t1 * t1 + v1 * 2.0 * t1 * t + v2 * t * t;
		}
		
		private function getClosestT( x0: Number, y0: Number, x1: Number, y1: Number, x2: Number, y2: Number, px: Number, py: Number ): int 
		{
			var dx: Number = x0 - px;
			var dy: Number = y0 - py;

var ex: Number = x0 - 2.0 * x1 + x2;
			var ey: Number = y0 - 2.0 * y1 + y2;
			var fx: Number = 2.0 * x1 - 2.0 * x0;
			var fy: Number = 2.0 * y1 - 2.0 * y0;

var d: Number = 2.0 * ( ex * ex + ey * ey );

var a: Number;
			var b: Number;
			
			var u: Number;
			var v: Number;
			var w: Number;
			
			var p: Number;
			var q: Number;
			var r: Number;
			var x: Number;

if( 0.0 == d )
			{
				b = ( fx * fx + fy * fy ) + 2.0 * ( dx * ex + dy * ey );

if( b < 0.0 )
				{
					if( -b > EPSILON )
						return 0;
				}
				else
				if( b < EPSILON )
					return 0;

R[ 0 ] = -( fx * dx + fy * dy ) / b;
				return 1;
			}
			else
			{
				var dInv: Number = 1.0 / d;

a = 3.0 * ( fx * ex + fy * ey ) * dInv;
				b = ( ( fx * fx + fy * fy ) + 2.0 * ( dx * ex + dy * ey ) ) * dInv;
				p = -a * a * 0.33333333333 + b;
				q = a * a * a * 0.074074074074074 - a * b * 0.33333333333 + ( fx * dx + fy * dy ) * dInv;
				r = q * q * 0.25 + p * p * p * 0.037037037037037;

if( r >= 0.0 ) 
				{
					r = Math.sqrt( r );
					x = sqrt3( -q * 0.5 + r ) + sqrt3( -q * 0.5 - r ) - a * 0.33333333333;
				}
				else
				{
					x = 2.0 * Math.sqrt( -p * 0.33333333333 ) * Math.cos( Math.atan2( Math.sqrt( -r ), -q * 0.5 ) * 0.33333333333 ) - a * 0.33333333333;
				}

u = x + a;
				v = x * x + a * x + b;
				w = u * u - 4.0 * v;

if( w < 0.0 )
				{
					R[ 0 ] = x;
					return 1;
				}

if( w > 0.0 )
				{
					w = Math.sqrt( w );
					
					R[ 0 ] = x;
					R[ 1 ] = -( u + w ) * 0.5;
					R[ 2 ] =  ( w - u ) * 0.5;
					return 3;
				}

R[ 0 ] = x;
				R[ 1 ] = -u * 0.5;
				return 2;
			}
		}

private function sqrt3( x: Number ): Number 
		{
			if( x > 0.0 ) 
				return Math.pow( x, 0.33333333333 );
			else
			if( x < 0.0 ) 
				return -Math.pow( -x, 0.33333333333 );

return 0.0;
		}
	}
}

import flash.display.Sprite;

class AnchorPoint extends Sprite
{
	public function AnchorPoint()
	{
		graphics.beginFill( 0xFFFFFF, 0.1 );
		graphics.drawCircle( 0.0, 0.0, 8.0 );
		graphics.endFill();

graphics.beginFill( 0xFFFFFF, 0.8 );
		graphics.drawCircle( 0.0, 0.0, 2.0 );
		graphics.endFill();
	}
}

Code Fullscreen

Preview Fullscreen