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
Remarks:
- 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.
Thanks Steffen.
What are you using for graphics?
Art
Comment by Art Scott — Wednesday, 7. January 2009 um 23:25 Uhr