Bezier Intersections (not a snippet)

var resolution:Number = .03;
var pointNum:int = Math.ceil(1 / resolution);

var bezA:Array = new Array();
populateArray(bezA);
var a:Sprite = dot(100, 200);
var b:Sprite = dot(200, 100);
var c:Sprite = dot(300, 200);

var bezB:Array = new Array();
populateArray(bezB);
var d:Sprite = dot(300, 100, 0xCCCC00);
var e:Sprite = dot(120, 130, 0xCCCC00);
var f:Sprite = dot(200, 300, 0xCCCC00);

addEventListener(Event.ENTER_FRAME, onLoop);
function onLoop(evt:Event):void {
      with(graphics){
		  clear();
		  lineStyle(0, 0x000000);
	   
	      // calc and draw bezier points
		  drawBezier(bezA, a, b, c);
		  drawBezier(bezB, d, e, f);
		  
		  // calc collisions
		  var intersections:Array = calculateIntersection(bezA, bezB);
		  
		   // draw collisions
		   beginFill(0xFF0000);
		   if (intersections.length > 0){
				for (var i:int = 0; i< intersections.length; i++){
					drawCircle(intersections[i].x, intersections[i].y, 3);
				}
		   }
		   endFill();
	 }
}

function populateArray(a:Array):void {
	for (var i:int = 0; i<pointNum; i++){
		a.push(new Point());
	}
}

function drawBezier(bez:Array, a:Sprite, b:Sprite, c:Sprite):void{
	 with(graphics){
		 bezier(bez, a.x, a.y, b.x, b.y, c.x, c.y);
		 var leng:Number = bez.length; 
		 moveTo(bez[0].x, bez[0].y);
		 for (var i:int = 1; i<leng; i++){
			 lineTo(bez[i].x, bez[i].y);
		 }
	 }
}

function bezier(bez:Array, x1:Number, y1:Number, x2:Number, y2:Number, x3:Number, y3:Number):void {
			var b:Number, a2:Number, ab2:Number, b2:Number;
			var pnt:Point;
			var inc:int = 0;
			for (var a:Number = 0; a <=1; a+=resolution) {
				b= 1 - a;
				a2 = a * a;
				ab2 = a * b * 2;
				b2 = b * b;
				pnt = bez[inc];
				pnt.x = a2 * x1 + ab2 * x2  + b2 * x3;
				pnt.y = a2 * y1 + ab2 * y2 + b2 * y3;      
				inc++;
			}
}

function calculateIntersection(bezA:Array, bezB:Array):Array {
	var intersections:Array = new Array();
	var ip:Point;
	var aLength:int = bezA.length;
	var bLength:int = bezB.length;
	var p1:Point, p2:Point, p3:Point, p4:Point;
	
	// compare all line segments and check for 
	// intersections
	for (var i:int = 1; i<aLength; i++){
		p1 = bezA[i - 1];
		p2 = bezA[i];
		for (var j:int = 1; j<bLength; j++){
			p3 = bezB[j - 1];
		    p4 = bezB[j];
			ip = intersection(p1, p2, p3, p4);
			if (ip){
				intersections.push(ip.clone());
			}
		}
	}
	return intersections;
}

var ip:Point = new Point();

function intersection(p1:Point, p2:Point, p3:Point, p4:Point):Point {
	 
	var nx:Number, ny:Number, dn:Number;
	var x4_x3:Number = p4.x - p3.x;
	var pre2:Number = p4.y - p3.y;
	var pre3:Number = p2.x - p1.x;
	var pre4:Number = p2.y - p1.y;
	var pre5:Number = p1.y - p3.y;
	var pre6:Number = p1.x - p3.x;
	
	nx = x4_x3 * pre5 - pre2 * pre6;
	ny = pre3 * pre5 - pre4 * pre6;
	dn = pre2 * pre3 - x4_x3 * pre4;
	
	if (dn == 0){
		return null
	}
	nx /= dn;
	ny /= dn;
    // has intersection
	if(nx >= 0 && nx <= 1 && ny >= 0 && ny <= 1){
		ny = p1.y + nx * pre4;
		nx = p1.x + nx * pre3;
		ip.x = nx;
		ip.y = ny;
    }else{
		 return null;
	}
	return ip
}

// draggable dot
function dot(xp:Number, yp:Number, col:uint = 0x507399, noDrag:Boolean = false):Sprite {
	var s:Sprite = Sprite(addChild(new Sprite));
	s.x = xp;
	s.y = yp;
	with(s.graphics) beginFill(col), drawCircle(0,0,5);
	if (!noDrag){
		s.buttonMode = true;
	   s.addEventListener(MouseEvent.MOUSE_DOWN, onDrag);
	}
	return s;
}
function onDrag(evt:MouseEvent):void {
	evt.currentTarget.startDrag()
}

stage.addEventListener(MouseEvent.MOUSE_UP, onUp);
function onUp(evt:MouseEvent):void{
	stopDrag();
}

This is not a snippet, but it uses some functions that could be considered snippets on their own. Take a look at the swf here:

Bezier Intersection Demo

This demo show a brute force method for getting the coordinates of all intersections between two given quadtratic bezier curves. The approach is pretty simple, each bezier is actually made up of a series of line segments. The resolution variable determines how many line segments make up one bezier curve. By default I use a resolution of 0.03 (~34 lines)… the higher the resolution decimal value, the fewer the number of line segments. I then use a slight variation on yesterdays line segment intersection function to test all existing line segments for intersections.

This is a brute for approach with lots of room for improvement. But in the scenario that you only need to check a few bezier curves for intersection this approach works quite nicely. I don’t recommend this approach if your trying to create a complex vector drawing tool with boolean vector operations etc…

It’s easy to get an idea of the different approaches to this problem with a little googling. One example I found is from Graphics Gems:

http://tog.acm.org/GraphicsGems/gemsiv/curve_isect/

it’s been awhile, but I believe this website also contains information related to this topic:

http://algorithmist.wordpress.com/