Rash thoughts about .NET, C#, F# and Dynamics NAV.


"Every solution will only lead to new problems."

Tuesday, 2. December 2008


Calculate the intersection point of two lines in F# (2 dimensions)

Filed under: English posts,F#,Informatik — Steffen Forkmann at 11:58 Uhr

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:

Intersection of two lines

We can write this as an equation system with two variables and two equations:

  • Ax + r (Bx – Ax) = Cx + s (Dx – Cx)
  • Ay + r (By – Ay) = Cy + s (Dy – Cy)

After solving this system we can calculate the intersection:

  • Px = Ax + r (Bx – Ax)
  • Py = Ay + r (By – Ay)

Putting this all together we can derive the following F#-code:

let calcIntersection (A:Location, B:Location, C:Location, D:Location) =
  let (Ax,Ay,Bx,By,Cx,Cy,Dx,Dy) =
     (A.XPos, A.YPos, B.XPos, B.YPos, C.XPos, C.YPos, D.XPos, D.YPos)
  let d = (Bx-Ax)*(Dy-Cy)-(By-Ay)*(Dx-Cx)  

  if  d = 0 then
    // parallel lines ==> no intersection in euclidean plane
    None
  else
let q = (Ay-Cy)*(Dx-Cx)-(Ax-Cx)*(Dy-Cy) let r = q / d let p = (Ay-Cy)*(Bx-Ax)-(Ax-Cx)*(By-Ay) let s = p / d if r < 0. or r > 1. or s < 0. or s > 1. then None // intersection is not within the line segments else Some( (Ax+r*(Bx-Ax)), // Px (Ay+r*(By-Ay))) // Py


Remarks:

  1. If one given line degenerates into a point, then the algorithm gives no intersection.
  2. If the given lines are parallel, then the algorithm gives no intersection, even if the lines have an overlap.
Tags: , , ,

1 Comment »

  1. Thanks Steffen.

    What are you using for graphics?

    Art

    Comment by Art Scott — Wednesday, 7. January 2009 um 23:25 Uhr

RSS feed for comments on this post. | TrackBack URI

Leave a comment

XHTML ( You can use these tags): <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> .