{"id":606,"date":"2008-12-02T11:58:03","date_gmt":"2008-12-02T10:58:03","guid":{"rendered":"http:\/\/www.navision-blog.de\/2008\/12\/02\/calculate-the-intersection-of-two-lines-in-fsharp-2d\/"},"modified":"2008-12-02T11:58:03","modified_gmt":"2008-12-02T10:58:03","slug":"calculate-the-intersection-of-two-lines-in-fsharp-2d","status":"publish","type":"post","link":"http:\/\/www.navision-blog.de\/blog\/2008\/12\/02\/calculate-the-intersection-of-two-lines-in-fsharp-2d\/","title":{"rendered":"Calculate the intersection point of two lines in F# (2 dimensions)"},"content":{"rendered":"<p>In one of my next postings I will show a algorithm, that calculates <a href=\"http:\/\/en.wikipedia.org\/wiki\/Line_segment_intersection\">line segment intersections<\/a>. As a prerequisite we need an algorithm, which calculates the intersection of two lines. In this post I will consider the following intersection of two lines in the euclidean plan:<\/p>\n<p><img loading=\"lazy\" style=\"border-top-width: 0px; border-left-width: 0px; border-bottom-width: 0px; border-right-width: 0px\" height=\"155\" alt=\"Intersection of two lines\" src=\"http:\/\/www.navision-blog.de\/images\/CalculatetheintersectionoftwolinesinF_BEB4\/image.png\" width=\"300\" border=\"0\"><\/p>\n<p>We can write this as an equation system with two variables and two equations<strong>:<\/strong><\/p>\n<ul>\n<li>Ax + r (Bx &#8211; Ax) = Cx + s (Dx &#8211; Cx)\n<li>Ay + r (By &#8211; Ay) = Cy + s (Dy &#8211; Cy) <\/li>\n<\/ul>\n<p>After solving this system we can calculate the intersection:<\/p>\n<ul>\n<li>Px = Ax + r (Bx &#8211; Ax)\n<li>Py = Ay + r (By &#8211; Ay) <\/li>\n<\/ul>\n<p>Putting this all together we can derive the following F#-code:<\/p>\n<pre class=\"code\"><span style=\"color: blue\">let <\/span>calcIntersection (A:Location, B:Location, C:Location, D:Location) =\n  <span style=\"color: blue\">let <\/span>(Ax,Ay,Bx,By,Cx,Cy,Dx,Dy) =\n     (A.XPos, A.YPos, B.XPos, B.YPos, C.XPos, C.YPos, D.XPos, D.YPos)\n  <span style=\"color: blue\">let <\/span>d = (Bx-Ax)*(Dy-Cy)-(By-Ay)*(Dx-Cx)  \n\n  <span style=\"color: blue\">if  <\/span>d = 0 <span style=\"color: blue\">then\n    <\/span><span style=\"color: green\">\/\/ parallel lines ==&gt; no intersection in euclidean plane\n    <\/span>None\n  <span style=\"color: blue\">else<br>    <\/span><span style=\"color: blue\">let <\/span>q = (Ay-Cy)*(Dx-Cx)-(Ax-Cx)*(Dy-Cy) <span style=\"color: blue\">\n    let <\/span>r = q \/ d\n    <span style=\"color: blue\">let <\/span>p = (Ay-Cy)*(Bx-Ax)-(Ax-Cx)*(By-Ay)\n    <span style=\"color: blue\">let <\/span>s = p \/ d\n\n<span style=\"color: blue\">    if <\/span>r &lt; 0. <span style=\"color: blue\">or <\/span>r &gt; 1. <span style=\"color: blue\">or <\/span>s &lt; 0. <span style=\"color: blue\">or <\/span>s &gt; 1. <span style=\"color: blue\">then\n      <\/span>None <span style=\"color: green\">\/\/ intersection is not within the line segments\n    <\/span><span style=\"color: blue\">else\n      <\/span>Some(\n        (Ax+r*(Bx-Ax)),  <span style=\"color: green\">\/\/ Px\n        <\/span>(Ay+r*(By-Ay)))  <span style=\"color: green\">\/\/ Py<\/span><\/pre>\n<p><\/p>\n<pre class=\"code\"><\/pre>\n<p>Remarks:<\/p>\n<ol>\n<li>If one given line degenerates into a point, then the algorithm gives no intersection.\n<li>If the given lines are parallel, then the algorithm gives no intersection, even if the lines have an overlap. <\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>In one of my next postings I will show a algorithm, that calculates line segment intersections. As a prerequisite we need an algorithm, which calculates the intersection of two lines. In this post I will consider the following intersection of two lines in the euclidean plan: We can write this as an equation system with [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[23,448,8],"tags":[477,664,476,478],"_links":{"self":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/606"}],"collection":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/comments?post=606"}],"version-history":[{"count":0,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/606\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/media?parent=606"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/categories?post=606"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/tags?post=606"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}