# Bezier Intersections (not a snippet)

Actionscript:
1. var resolution:Number = .03;
2. var pointNum:int = Math.ceil(1 / resolution);
3.
4. var bezA:Array = new Array();
5. populateArray(bezA);
6. var a:Sprite = dot(100, 200);
7. var b:Sprite = dot(200, 100);
8. var c:Sprite = dot(300, 200);
9.
10. var bezB:Array = new Array();
11. populateArray(bezB);
12. var d:Sprite = dot(300, 100, 0xCCCC00);
13. var e:Sprite = dot(120, 130, 0xCCCC00);
14. var f:Sprite = dot(200, 300, 0xCCCC00);
15.
17. function onLoop(evt:Event):void {
18.       with(graphics){
19.           clear();
20.           lineStyle(0, 0x000000);
21.
22.           // calc and draw bezier points
23.           drawBezier(bezA, a, b, c);
24.           drawBezier(bezB, d, e, f);
25.
26.           // calc collisions
27.           var intersections:Array = calculateIntersection(bezA, bezB);
28.
29.            // draw collisions
30.            beginFill(0xFF0000);
31.            if (intersections.length> 0){
32.                 for (var i:int = 0; i<intersections.length; i++){
33.                     drawCircle(intersections[i].x, intersections[i].y, 3);
34.                 }
35.            }
36.            endFill();
37.      }
38. }
39.
40. function populateArray(a:Array):void {
41.     for (var i:int = 0; i<pointNum; i++){
42.         a.push(new Point());
43.     }
44. }
45.
46. function drawBezier(bez:Array, a:Sprite, b:Sprite, c:Sprite):void{
47.      with(graphics){
48.          bezier(bez, a.x, a.y, b.x, b.y, c.x, c.y);
49.          var leng:Number = bez.length;
50.          moveTo(bez.x, bez.y);
51.          for (var i:int = 1; i<leng; i++){
52.              lineTo(bez[i].x, bez[i].y);
53.          }
54.      }
55. }
56.
57. function bezier(bez:Array, x1:Number, y1:Number, x2:Number, y2:Number, x3:Number, y3:Number):void {
58.             var b:Number, a2:Number, ab2:Number, b2:Number;
59.             var pnt:Point;
60.             var inc:int = 0;
61.             for (var a:Number = 0; a <=1; a+=resolution) {
62.                 b= 1 - a;
63.                 a2 = a * a;
64.                 ab2 = a * b * 2;
65.                 b2 = b * b;
66.                 pnt = bez[inc];
67.                 pnt.x = a2 * x1 + ab2 * x2  + b2 * x3;
68.                 pnt.y = a2 * y1 + ab2 * y2 + b2 * y3;
69.                 inc++;
70.             }
71. }
72.
73. function calculateIntersection(bezA:Array, bezB:Array):Array {
74.     var intersections:Array = new Array();
75.     var ip:Point;
76.     var aLength:int = bezA.length;
77.     var bLength:int = bezB.length;
78.     var p1:Point, p2:Point, p3:Point, p4:Point;
79.
80.     // compare all line segments and check for
81.     // intersections
82.     for (var i:int = 1; i<aLength; i++){
83.         p1 = bezA[i - 1];
84.         p2 = bezA[i];
85.         for (var j:int = 1; j<bLength; j++){
86.             p3 = bezB[j - 1];
87.             p4 = bezB[j];
88.             ip = intersection(p1, p2, p3, p4);
89.             if (ip){
90.                 intersections.push(ip.clone());
91.             }
92.         }
93.     }
94.     return intersections;
95. }
96.
97. var ip:Point = new Point();
98.
99. function intersection(p1:Point, p2:Point, p3:Point, p4:Point):Point {
100.
101.     var nx:Number, ny:Number, dn:Number;
102.     var x4_x3:Number = p4.x - p3.x;
103.     var pre2:Number = p4.y - p3.y;
104.     var pre3:Number = p2.x - p1.x;
105.     var pre4:Number = p2.y - p1.y;
106.     var pre5:Number = p1.y - p3.y;
107.     var pre6:Number = p1.x - p3.x;
108.
109.     nx = x4_x3 * pre5 - pre2 * pre6;
110.     ny = pre3 * pre5 - pre4 * pre6;
111.     dn = pre2 * pre3 - x4_x3 * pre4;
112.
113.     if (dn == 0){
114.         return null
115.     }
116.     nx /= dn;
117.     ny /= dn;
118.     // has intersection
119.     if(nx>= 0 && nx <= 1 && ny>= 0 && ny <= 1){
120.         ny = p1.y + nx * pre4;
121.         nx = p1.x + nx * pre3;
122.         ip.x = nx;
123.         ip.y = ny;
124.     }else{
125.          return null;
126.     }
127.     return ip
128. }
129.
130. // draggable dot
131. function dot(xp:Number, yp:Number, col:uint = 0x507399, noDrag:Boolean = false):Sprite {
132.     var s:Sprite = Sprite(addChild(new Sprite));
133.     s.x = xp;
134.     s.y = yp;
135.     with(s.graphics) beginFill(col), drawCircle(0,0,5);
136.     if (!noDrag){
137.         s.buttonMode = true;
139.     }
140.     return s;
141. }
142. function onDrag(evt:MouseEvent):void {
143.     evt.currentTarget.startDrag()
144. }
145.
147. function onUp(evt:MouseEvent):void{
148.     stopDrag();
149. }

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/