{"id":218,"date":"2009-03-13T07:40:06","date_gmt":"2009-03-13T14:40:06","guid":{"rendered":"https:\/\/actionsnippet.com\/?p=949"},"modified":"2009-03-13T07:40:06","modified_gmt":"2009-03-13T14:40:06","slug":"line-intersection-part-1-unoptimized","status":"publish","type":"post","link":"https:\/\/actionsnippet.com\/?p=218","title":{"rendered":"Line Intersection Part 1 (unoptimized)"},"content":{"rendered":"
\r\n\/\/ completely unoptimized line to line intersection test:\r\n\/\/ from wikipedia: http:\/\/en.wikipedia.org\/wiki\/Line-line_intersection\r\nfunction intersection(p1:Sprite, p2:Sprite, p3:Sprite, p4:Sprite):Point {\r\n\tvar nx:Number, ny:Number, dn:Number;\r\n\tnx = (p1.x * p2.y - p1.y * p2.x) * (p3.x - p4.x) - (p1.x - p2.x) * (p3.x * p4.y - p3.y * p4.x);\r\n\tdn = (p1.x - p2.x) * (p3.y - p4.y) - (p1.y - p2.y) * (p3.x - p4.x);\r\n\tny = (p1.x * p2.y - p1.y * p2.x) * (p3.y - p4.y) - (p1.y - p2.y) * (p3.x * p4.y - p3.y * p4.x);\r\n\treturn new Point(nx \/ dn, ny \/ dn);\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 snippet shows the first step toward a usable line to line intersection test. While this demo is fully functional, there is some room for optimization within the intersection() function itself… <\/p>\n
From Equations to Code<\/h3>\n
When I go directly from an equation to code I like to try to make the code resemble the equation… test to make sure it works and then<\/em> add optimizations. I do this to keep things clear for myself and also so that I have a step by step process to show my students.<\/p>\n
The optimizations and additional features that I’ll add to this function tomorrow will make it look very different from the original equation from wikipedia<\/a>. Some things that I’ll do:<\/p>\n
1) tweak the equation to use fewer operators (it has 12 multiplications right now)
\n2) wrap duplicate mathmatical operations in variables
\n3) add the ability to test for line segments rather than infinite lines
\n4) move any object instantiation outside the function
\netc…<\/p>\n","protected":false},"excerpt":{"rendered":"
\/\/ completely unoptimized line to line intersection test: \/\/ from wikipedia: http:\/\/en.wikipedia.org\/wiki\/Line-line_intersection function intersection(p1:Sprite, p2:Sprite, p3:Sprite, p4:Sprite):Point { var nx:Number, ny:Number, dn:Number; 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); dn = (p1.x – p2.x) * (p3.y – […]<\/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-218","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\/218","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=218"}],"version-history":[{"count":0,"href":"https:\/\/actionsnippet.com\/index.php?rest_route=\/wp\/v2\/posts\/218\/revisions"}],"wp:attachment":[{"href":"https:\/\/actionsnippet.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=218"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/actionsnippet.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=218"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/actionsnippet.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=218"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}