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 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
- If one given line degenerates into a point, then the algorithm gives no intersection.
- If the given lines are parallel, then the algorithm gives no intersection, even if the lines have an overlap.