{"id":220,"date":"2009-03-15T00:00:40","date_gmt":"2009-03-15T07:00:40","guid":{"rendered":"https:\/\/actionsnippet.com\/?p=965"},"modified":"2009-03-15T00:00:40","modified_gmt":"2009-03-15T07:00:40","slug":"bezier-intersections-not-a-snippet","status":"publish","type":"post","link":"https:\/\/actionsnippet.com\/?p=220","title":{"rendered":"Bezier Intersections (not a snippet)"},"content":{"rendered":"<pre class=\"brush: as3; title: ; notranslate\" title=\"\">\r\nvar resolution:Number = .03;\r\nvar pointNum:int = Math.ceil(1 \/ resolution);\r\n\r\nvar bezA:Array = new Array();\r\npopulateArray(bezA);\r\nvar a:Sprite = dot(100, 200);\r\nvar b:Sprite = dot(200, 100);\r\nvar c:Sprite = dot(300, 200);\r\n\r\nvar bezB:Array = new Array();\r\npopulateArray(bezB);\r\nvar d:Sprite = dot(300, 100, 0xCCCC00);\r\nvar e:Sprite = dot(120, 130, 0xCCCC00);\r\nvar f:Sprite = dot(200, 300, 0xCCCC00);\r\n\r\naddEventListener(Event.ENTER_FRAME, onLoop);\r\nfunction onLoop(evt:Event):void {\r\n      with(graphics){\r\n\t\t  clear();\r\n\t\t  lineStyle(0, 0x000000);\r\n\t   \r\n\t      \/\/ calc and draw bezier points\r\n\t\t  drawBezier(bezA, a, b, c);\r\n\t\t  drawBezier(bezB, d, e, f);\r\n\t\t  \r\n\t\t  \/\/ calc collisions\r\n\t\t  var intersections:Array = calculateIntersection(bezA, bezB);\r\n\t\t  \r\n\t\t   \/\/ draw collisions\r\n\t\t   beginFill(0xFF0000);\r\n\t\t   if (intersections.length &gt; 0){\r\n\t\t\t\tfor (var i:int = 0; i&lt; intersections.length; i++){\r\n\t\t\t\t\tdrawCircle(intersections&#x5B;i].x, intersections&#x5B;i].y, 3);\r\n\t\t\t\t}\r\n\t\t   }\r\n\t\t   endFill();\r\n\t }\r\n}\r\n\r\nfunction populateArray(a:Array):void {\r\n\tfor (var i:int = 0; i&lt;pointNum; i++){\r\n\t\ta.push(new Point());\r\n\t}\r\n}\r\n\r\nfunction drawBezier(bez:Array, a:Sprite, b:Sprite, c:Sprite):void{\r\n\t with(graphics){\r\n\t\t bezier(bez, a.x, a.y, b.x, b.y, c.x, c.y);\r\n\t\t var leng:Number = bez.length; \r\n\t\t moveTo(bez&#x5B;0].x, bez&#x5B;0].y);\r\n\t\t for (var i:int = 1; i&lt;leng; i++){\r\n\t\t\t lineTo(bez&#x5B;i].x, bez&#x5B;i].y);\r\n\t\t }\r\n\t }\r\n}\r\n\r\nfunction bezier(bez:Array, x1:Number, y1:Number, x2:Number, y2:Number, x3:Number, y3:Number):void {\r\n\t\t\tvar b:Number, a2:Number, ab2:Number, b2:Number;\r\n\t\t\tvar pnt:Point;\r\n\t\t\tvar inc:int = 0;\r\n\t\t\tfor (var a:Number = 0; a &lt;=1; a+=resolution) {\r\n\t\t\t\tb= 1 - a;\r\n\t\t\t\ta2 = a * a;\r\n\t\t\t\tab2 = a * b * 2;\r\n\t\t\t\tb2 = b * b;\r\n\t\t\t\tpnt = bez&#x5B;inc];\r\n\t\t\t\tpnt.x = a2 * x1 + ab2 * x2  + b2 * x3;\r\n\t\t\t\tpnt.y = a2 * y1 + ab2 * y2 + b2 * y3;      \r\n\t\t\t\tinc++;\r\n\t\t\t}\r\n}\r\n\r\nfunction calculateIntersection(bezA:Array, bezB:Array):Array {\r\n\tvar intersections:Array = new Array();\r\n\tvar ip:Point;\r\n\tvar aLength:int = bezA.length;\r\n\tvar bLength:int = bezB.length;\r\n\tvar p1:Point, p2:Point, p3:Point, p4:Point;\r\n\t\r\n\t\/\/ compare all line segments and check for \r\n\t\/\/ intersections\r\n\tfor (var i:int = 1; i&lt;aLength; i++){\r\n\t\tp1 = bezA&#x5B;i - 1];\r\n\t\tp2 = bezA&#x5B;i];\r\n\t\tfor (var j:int = 1; j&lt;bLength; j++){\r\n\t\t\tp3 = bezB&#x5B;j - 1];\r\n\t\t    p4 = bezB&#x5B;j];\r\n\t\t\tip = intersection(p1, p2, p3, p4);\r\n\t\t\tif (ip){\r\n\t\t\t\tintersections.push(ip.clone());\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\treturn intersections;\r\n}\r\n\r\nvar ip:Point = new Point();\r\n\r\nfunction intersection(p1:Point, p2:Point, p3:Point, p4:Point):Point {\r\n\t \r\n\tvar nx:Number, ny:Number, dn:Number;\r\n\tvar x4_x3:Number = p4.x - p3.x;\r\n\tvar pre2:Number = p4.y - p3.y;\r\n\tvar pre3:Number = p2.x - p1.x;\r\n\tvar pre4:Number = p2.y - p1.y;\r\n\tvar pre5:Number = p1.y - p3.y;\r\n\tvar pre6:Number = p1.x - p3.x;\r\n\t\r\n\tnx = x4_x3 * pre5 - pre2 * pre6;\r\n\tny = pre3 * pre5 - pre4 * pre6;\r\n\tdn = pre2 * pre3 - x4_x3 * pre4;\r\n\t\r\n\tif (dn == 0){\r\n\t\treturn null\r\n\t}\r\n\tnx \/= dn;\r\n\tny \/= dn;\r\n    \/\/ has intersection\r\n\tif(nx &gt;= 0 &amp;&amp; nx &lt;= 1 &amp;&amp; ny &gt;= 0 &amp;&amp; ny &lt;= 1){\r\n\t\tny = p1.y + nx * pre4;\r\n\t\tnx = p1.x + nx * pre3;\r\n\t\tip.x = nx;\r\n\t\tip.y = ny;\r\n    }else{\r\n\t\t return null;\r\n\t}\r\n\treturn ip\r\n}\r\n\r\n\/\/ draggable dot\r\nfunction dot(xp:Number, yp:Number, col:uint = 0x507399, noDrag:Boolean = false):Sprite {\r\n\tvar s:Sprite = Sprite(addChild(new Sprite));\r\n\ts.x = xp;\r\n\ts.y = yp;\r\n\twith(s.graphics) beginFill(col), drawCircle(0,0,5);\r\n\tif (!noDrag){\r\n\t\ts.buttonMode = true;\r\n\t   s.addEventListener(MouseEvent.MOUSE_DOWN, onDrag);\r\n\t}\r\n\treturn s;\r\n}\r\nfunction onDrag(evt:MouseEvent):void {\r\n\tevt.currentTarget.startDrag()\r\n}\r\n\r\nstage.addEventListener(MouseEvent.MOUSE_UP, onUp);\r\nfunction onUp(evt:MouseEvent):void{\r\n\tstopDrag();\r\n}\r\n<\/pre>\n<p>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:<\/p>\n<p><a data-asruffle-linked=\"true\" href=\"http:\/\/www.actionsnippet.com\/swfs\/bezier_intersect.html\"  target=\"blank\">Bezier Intersection Demo<\/a> <span class=\"asruffle-link\" data-swf=\"{&quot;url&quot;:&quot;https:\\\/\\\/actionsnippet.com\\\/swfs\\\/bezier_intersect.swf&quot;,&quot;title&quot;:&quot;bezier intersect&quot;,&quot;width&quot;:550,&quot;height&quot;:400,&quot;missing&quot;:false,&quot;allowScriptAccess&quot;:false,&quot;backgroundColor&quot;:&quot;#ffffff&quot;}\"><button type=\"button\" hidden aria-expanded=\"false\">Play demo<span class=\"screen-reader-text\">: bezier intersect<\/span><\/button><\/span><\/p>\n<p>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)&#8230; 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. <\/p>\n<p>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&#8217;t recommend this approach if your trying to create a complex vector drawing tool with boolean vector operations etc&#8230;<\/p>\n<p>It&#8217;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:<\/p>\n<p><a href=\"http:\/\/tog.acm.org\/GraphicsGems\/gemsiv\/curve_isect\/\" target=\"blank\">http:\/\/tog.acm.org\/GraphicsGems\/gemsiv\/curve_isect\/<\/a><\/p>\n<p>it&#8217;s been awhile, but I believe this website also contains information related to this topic:<\/p>\n<p><a href=\"http:\/\/algorithmist.wordpress.com\/\" target=\"blank\">http:\/\/algorithmist.wordpress.com\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>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); [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[30,121],"tags":[3,4],"class_list":["post-220","post","type-post","status-publish","format-standard","hentry","category-bezier","category-math","tag-actionscript","tag-flash"],"_links":{"self":[{"href":"https:\/\/actionsnippet.com\/index.php?rest_route=\/wp\/v2\/posts\/220","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/actionsnippet.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/actionsnippet.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/actionsnippet.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/actionsnippet.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=220"}],"version-history":[{"count":0,"href":"https:\/\/actionsnippet.com\/index.php?rest_route=\/wp\/v2\/posts\/220\/revisions"}],"wp:attachment":[{"href":"https:\/\/actionsnippet.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=220"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/actionsnippet.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=220"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/actionsnippet.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=220"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}