{"id":219,"date":"2009-03-14T00:00:30","date_gmt":"2009-03-14T07:00:30","guid":{"rendered":"https:\/\/actionsnippet.com\/?p=956"},"modified":"2009-03-14T00:00:30","modified_gmt":"2009-03-14T07:00:30","slug":"line-intersection-part-2-optimized","status":"publish","type":"post","link":"https:\/\/actionsnippet.com\/?p=219","title":{"rendered":"Line Intersection Part 2 (optimized)"},"content":{"rendered":"
\r\n\/\/ optimized line to line intersection test:\r\n\/\/ from wikipedia: http:\/\/en.wikipedia.org\/wiki\/Line-line_intersection\r\n\/\/ and http:\/\/local.wasp.uwa.edu.au\/~pbourke\/geometry\/lineline2d\/\r\nvar ip:Point = new Point();\r\n\r\nfunction intersection(p1:Sprite, p2:Sprite, p3:Sprite, p4:Sprite):Point {\r\n\tvar nx:Number, ny:Number, dn:Number;\r\n\tvar x4_x3:Number = p4.x - p3.x;\r\n\tvar y4_y3:Number = p4.y - p3.y;\r\n\tvar x2_x1:Number = p2.x - p1.x;\r\n\tvar y2_y1:Number = p2.y - p1.y;\r\n\tvar x1_x3:Number = p1.x - p3.x;\r\n\tvar y1_y3:Number = p1.y - p3.y;\r\n\t\r\n\tnx = x4_x3 * y1_y3 - y4_y3 * x1_x3;\r\n\tny = x2_x1 * y1_y3 - y2_y1 * x1_x3;\r\n\tdn = y4_y3 * x2_x1 - x4_x3 * y2_y1;\r\n\t\r\n\tnx \/= dn;\r\n\tny \/= dn;\r\n\t\r\n    \/\/ has intersection\r\n\tif(nx >= 0 && nx <= 1 && ny >= 0 && ny <= 1){\r\n\t\tny = p1.y + nx * y2_y1;\r\n\t\tnx = p1.x + nx * x2_x1;\r\n\t\tip.x = nx;\r\n\t\tip.y = ny;\r\n    }else{\r\n\t\t\/\/ no intersection\r\n\t\tip.x = ip.y = -1000;\r\n\t}\r\n\treturn ip\r\n}\r\n\r\n\r\n\/\/\r\n\/\/ test out the function:\r\n\/\/\r\n\r\nstage.frameRate = 30;\r\nvar a:Sprite = dot();\r\na.x = a.y = 100;\r\n\r\nvar b:Sprite = dot();\r\nb.x = b.y = 200;\r\n\r\nvar c:Sprite = dot();\r\nc.x = 200\r\nc.y = 100;\r\n\r\nvar d:Sprite = dot();\r\nd.x = 100\r\nd.y = 200;\r\n\r\nvar inter:Sprite = dot(0xFF0000,true);\r\n\r\naddEventListener(Event.ENTER_FRAME, onLoop);\r\nfunction onLoop(evt:Event):void {\r\n    var p:Point = intersection(a, b, c, d);\r\n\tinter.x = p.x;\r\n\tinter.y = p.y\r\n\t\r\n\twith(graphics){\r\n\t\tclear();\r\n\t\tlineStyle(0,0x000000);\r\n\t\tmoveTo(a.x, a.y);\r\n\t\tlineTo(b.x, b.y);\r\n\t\tmoveTo(c.x, c.y);\r\n\t\tlineTo(d.x,d.y);\r\n\t}\r\n}\r\n\r\n\/\/ draggable dot\r\nfunction dot(col:uint = 0x507399, noDrag:Boolean = false):Sprite {\r\n\tvar s:Sprite = Sprite(addChild(new Sprite));\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
This is a significantly optimized version of yesterdays post. The function intersection() takes four sprites as its arguments. The four arguments could be considered starting points and ending points for two line segments. <\/p>\n
The bottleneck in yesterdays post looked something like this;<\/p>\n
nx = (p1.x * p2.y – p1.y * p2.x) * (p3.x – p4.x) – (p1.x – p2.x) * (p3.x * p4.y – p3.y * p4.x);
\ndn = (p1.x – p2.x) * (p3.y – p4.y) – (p1.y – p2.y) * (p3.x – p4.x);
\nny = (p1.x * p2.y – p1.y * p2.x) * (p3.y – p4.y) – (p1.y – p2.y) * (p3.x * p4.y – p3.y * p4.x);
\nreturn new Point(nx \/dn, ny \/ dn);<\/p>\n
nx and ny are the numerators for two fractions both with dn as their denominator…. after taking a look at this page:<\/p>\n
http:\/\/local.wasp.uwa.edu.au\/~pbourke\/geometry\/lineline2d\/<\/a><\/p>\n
We can simplify things a bit before we start wrapping repetitive math operations up in variables:<\/p>\n
\r\nnx = (p4.x - p3.x) * (p1.y - p3.y) - (p4.y - p3.y) * (p1.x - p3.x);\r\n\/\/ ny = (p2.x - p1.x) * (p1.y - p3.y) - (p2.y - p1.y) * (p1.x - p3.x);\r\ndn = (p4.y - p3.y) * (p2.x - p1.x) - (p4.x - p3.x) * (p2.y - p1.y);\r\nnx \/= dn;\r\n\/\/ ny \/= dn\r\nny = p1.y + nx * (p2.y - p1.y);\r\nnx = p1.x + nx * (p2.x - p1.x);\r\nreturn new Point(nx, ny);\r\n<\/pre>\n
It’s important to note here that if we didn’t intend to calculate line segments we could exclude the initial calculation of ny.<\/p>\n
At this point we’re ready to get rid of duplicate math operations by wrapping them in variables. In this case this only includes subtraction:<\/p>\n
\r\nvar x4_x3:Number=p4.x-p3.x;\r\nvar y4_y3:Number=p4.y-p3.y;\r\nvar x2_x1:Number=p2.x-p1.x;\r\nvar y2_y1:Number=p2.y-p1.y;\r\nvar x1_x3:Number=p1.x-p3.x;\r\nvar y1_y3:Number=p1.y-p3.y;\r\n\r\nnx=x4_x3*y1_y3-y4_y3*x1_x3;\r\nny=x2_x1*y1_y3-y2_y1*x1_x3;\r\ndn=y4_y3*x2_x1-x4_x3*y2_y1;\r\n\r\nnx\/=dn;\r\nny\/=dn;\r\n\r\nny=p1.y+nx*y2_y1;\r\nnx=p1.x+nx*x2_x1;\r\n\r\nreturn new Point(nx, ny);\r\n<\/pre>\n
After wrapping repetitive math into variables the only optimization left to be made is related to the instantiation of a new Point(). Instantiation of objects is an expensive process, so it’s better to define the point once outside of the intersection() function definition. <\/p>\n
In the end our function looks like this:<\/p>\n
\r\nvar ip:Point = new Point();\r\n\r\nfunction intersection(p1:Sprite, p2:Sprite, p3:Sprite, p4:Sprite):Point {\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\tnx = x4_x3 * pre5 - pre2 * pre6;\r\n\tny = pre3 * pre5 - pre4 * pre6;\r\n\tdn = pre2 * pre3 - x4_x3 * pre4;\r\n\tnx \/= dn;\r\n\tny \/= dn;\r\n    \/\/ has intersection\r\n\tif(nx >= 0 && nx <= 1 && ny >= 0 && ny <= 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\/\/ no intersection\r\n\t\tip.x = ip.y = -1000;\r\n\t}\r\n\treturn ip\r\n}\r\n<\/pre>\n
The final version contains a conditional that checks the end values of nx and ny, if they are between 0 and 1 then we know that there is an intersection between the segments.<\/p>\n
Note: Optimized code usually breaks some best practices… as best practices are usually geared toward code flexibility and readability… and not speed.<\/i><\/p>\n","protected":false},"excerpt":{"rendered":"
\/\/ optimized line to line intersection test: \/\/ from wikipedia: http:\/\/en.wikipedia.org\/wiki\/Line-line_intersection \/\/ and http:\/\/local.wasp.uwa.edu.au\/~pbourke\/geometry\/lineline2d\/ var ip:Point = new Point(); function intersection(p1:Sprite, p2:Sprite, p3:Sprite, p4:Sprite):Point { var nx:Number, ny:Number, dn:Number; var x4_x3:Number = p4.x – p3.x; var y4_y3:Number = p4.y – p3.y; var x2_x1:Number = p2.x – p1.x; var y2_y1:Number = p2.y – p1.y; var x1_x3:Number […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[121,94],"tags":[3,4],"class_list":["post-219","post","type-post","status-publish","format-standard","hentry","category-math","category-misc","tag-actionscript","tag-flash"],"_links":{"self":[{"href":"https:\/\/actionsnippet.com\/index.php?rest_route=\/wp\/v2\/posts\/219","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=219"}],"version-history":[{"count":0,"href":"https:\/\/actionsnippet.com\/index.php?rest_route=\/wp\/v2\/posts\/219\/revisions"}],"wp:attachment":[{"href":"https:\/\/actionsnippet.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=219"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/actionsnippet.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=219"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/actionsnippet.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=219"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}