Find the intersection of two lines
Finding the intersection of two lines that are in the same plane is an important topic in collision detection.[1]
- Task
Find the point of intersection of two lines in 2D. The first line passes though (4.0,0.0) and (6.0,10.0). The second line passes though (0.0,3.0) and (10.0,7.0).
C++
<lang cpp>#include <iostream>
- include <cmath>
- include <assert.h>
using namespace std;
/** Calculate determinant of matrix: [a b] [c d]
- /
inline double Det(double a, double b, double c, double d) { return a*d - b*c; }
///Calculate intersection of two lines. ///\return true if found, false if not found or error bool LineLineIntersect(double x1, double y1, //Line 1 start double x2, double y2, //Line 1 end double x3, double y3, //Line 2 start double x4, double y4, //Line 2 end double &ixOut, double &iyOut) //Output { double detL1 = Det(x1, y1, x2, y2); double detL2 = Det(x3, y3, x4, y4); double x1mx2 = x1 - x2; double x3mx4 = x3 - x4; double y1my2 = y1 - y2; double y3my4 = y3 - y4;
double xnom = Det(detL1, x1mx2, detL2, x3mx4); double ynom = Det(detL1, y1my2, detL2, y3my4); double denom = Det(x1mx2, y1my2, x3mx4, y3my4); if(denom == 0.0)//Lines don't seem to cross { ixOut = NAN; iyOut = NAN; return false; }
ixOut = xnom / denom; iyOut = ynom / denom; if(!isfinite(ixOut) || !isfinite(iyOut)) //Probably a numerical issue return false;
return true; //All OK }
int main() { // **Simple crossing diagonal lines**
//Line 1 double x1=4.0, y1=0.0; double x2=6.0, y2=10.0;
//Line 2 double x3=0.0, y3=3.0; double x4=10.0, y4=7.0;
double ix = -1.0, iy = -1.0; bool result = LineLineIntersect(x1, y1, x2, y2, x3, y3, x4, y4, ix, iy); cout << "result " << result << "," << ix << "," << iy << endl;
double eps = 1e-6; assert(result == true); assert(fabs(ix - 5.0) < eps); assert(fabs(iy - 5.0) < eps);
}</lang>
- Output:
result 1,5,5
Perl 6
<lang perl6>sub intersection (Real $ax, Real $ay, Real $bx, Real $by,
Real $cx, Real $cy, Real $dx, Real $dy ) {
sub term:<|AB|> { determinate($ax, $ay, $bx, $by) }
sub term:<|CD|> { determinate($cx, $cy, $dx, $dy) }
my $ΔxAB = $ax - $bx; my $ΔyAB = $ay - $by; my $ΔxCD = $cx - $dx; my $ΔyCD = $cy - $dy;
my $x-numerator = determinate( |AB|, $ΔxAB, |CD|, $ΔxCD ); my $y-numerator = determinate( |AB|, $ΔyAB, |CD|, $ΔyCD ); my $denominator = determinate( $ΔxAB, $ΔyAB, $ΔxCD, $ΔyCD );
return 'Lines are parallel' if $denominator == 0;
($x-numerator/$denominator, $y-numerator/$denominator);
}
sub determinate ( Real $a, Real $b, Real $c, Real $d ) { $a * $d - $b * $c }
- TESTING
say 'Intersection point: ', intersection( 4,0, 6,10, 0,3, 10,7 ); say 'Intersection point: ', intersection( 4,0, 6,10, 0,3, 10,7.1 ); say 'Intersection point: ', intersection( 0,0, 1,1, 1,2, 4,5 );</lang>
- Output:
Intersection point: (5 5) Intersection point: (5.010893 5.054466) Intersection point: Lines are parallel
Python
<lang python>from __future__ import print_function from shapely.geometry import LineString
if __name__=="__main__": line1 = LineString([(4.0,0.0), (6.0,10.0)]) line2 = LineString([(0.0,3.0), (10.0,7.0)]) print (line1.intersection(line2))</lang>
- Output:
POINT (5 5)
Racket
<lang racket>#lang racket/base (define (det a b c d) (- (* a d) (* b c))) ; determinant
(define (line-intersect ax ay bx by cx cy dx dy) ; --> (values x y)
(let* ((det.ab (det ax ay bx by))
(det.cd (det cx cy dx dy))
(abΔx (- ax bx))
(cdΔx (- cx dx))
(abΔy (- ay by))
(cdΔy (- cy dy))
(xnom (det det.ab abΔx det.cd cdΔx))
(ynom (det det.ab abΔy det.cd cdΔy))
(denom (det abΔx abΔy cdΔx cdΔy)))
(when (zero? denom)
(error 'line-intersect "parallel lines"))
(values (/ xnom denom) (/ ynom denom))))
(module+ test (line-intersect 4 0 6 10
0 3 10 7))</lang>
- Output:
5 5
REXX
version 1
Naive implementation. To be improved for parallel lines and degenerate lines such as y=5 or x=8. <lang rexx>/* REXX */ Parse Value '(4.0,0.0)' With '(' xa ',' ya ')' Parse Value '(6.0,10.0)' With '(' xb ',' yb ')' Parse Value '(0.0,3.0)' With '(' xc ',' yc ')' Parse Value '(10.0,7.0)' With '(' xd ',' yd ')'
Say 'The two lines are:' Say 'yab='ya-xa*((yb-ya)/(xb-xa))'+x*'||((yb-ya)/(xb-xa)) Say 'ycd='yc-xc*((yd-yc)/(xd-xc))'+x*'||((yd-yc)/(xd-xc))
x=((yc-xc*((yd-yc)/(xd-xc)))-(ya-xa*((yb-ya)/(xb-xa))))/,
(((yb-ya)/(xb-xa))-((yd-yc)/(xd-xc)))
Say 'x='||x
y=ya-xa*((yb-ya)/(xb-xa))+x*((yb-ya)/(xb-xa))
Say 'yab='y Say 'ycd='yc-xc*((yd-yc)/(xd-xc))+x*((yd-yc)/(xd-xc)) Say 'Intersection: ('||x','y')'</lang>
- Output:
The two lines are: yab=-20.0+x*5 ycd=3.0+x*0.4 x=5 yab=5.0 ycd=5.0 Intersection: (5,5.0)
version 2
complete implementation taking care of all possibilities <lang>say ggx1('4.0 0.0 6.0 10.0 0.0 3.0 10.0 7.0') say ggx1('0.0 0.0 0.0 10.0 0.0 3.0 10.0 7.0') say ggx1('0.0 0.0 0.0 10.0 0.0 3.0 10.0 7.0') say ggx1('0.0 0.0 0.0 1.0 1.0 0.0 1.0 7.0') say ggx1('0.0 0.0 0.0 0.0 0.0 3.0 10.0 7.0') say ggx1('0.0 0.0 3.0 3.0 0.0 0.0 6.0 6.0') say ggx1('0.0 0.0 3.0 3.0 0.0 1.0 6.0 7.0') Exit
ggx1: Procedure Parse Arg xa ya xb yb xc yc xd yd Say 'A=('xa'/'ya') B=('||xb'/'yb') C=('||xc'/'yc') D=('||xd'/'yd')' res= If xa=xb Then Do
k1='*' x1=xa If ya=yb Then res='Points A and B are identical' End
Else Do
k1=(yb-ya)/(xb-xa) d1=ya-k1*xa End
If xc=xd Then Do
k2='*' x2=xc If yc=yd Then res='Points C and D are identical' End
Else Do
k2=(yd-yc)/(xd-xc) d2=yc-k2*xc End
If res= Then Do
If k1='*' Then Do
If k2='*' Then Do
If x1=x2 Then
res='Lines AB and CD are identicl'
Else
res='Lines AB and CD are parallel'
End
Else Do
x=x1
y=k2*x+d2
End
End
Else Do
If k2='*' Then Do
x=x2
y=k1*x+d1
End
Else Do
If k1=k2 Then Do
If d1=d2 Then
res='Lines AB and CD are identicl'
Else
res='Lines AB and CD are parallel'
End
Else Do
x=(d2-d1)/(k1-k2)
y=k1*x+d1
End
End
End
End
If res= Then
res='Intersection is ('||x'/'y')'
Return ' -->' res</lang>
- Output:
A=(4.0/0.0) B=(6.0/10.0) C=(0.0/3.0) D=(10.0/7.0) --> Intersection is (5/5.0) A=(0.0/0.0) B=(0.0/10.0) C=(0.0/3.0) D=(10.0/7.0) --> Intersection is (0.0/3.0) A=(0.0/0.0) B=(0.0/10.0) C=(0.0/3.0) D=(10.0/7.0) --> Intersection is (0.0/3.0) A=(0.0/0.0) B=(0.0/1.0) C=(1.0/0.0) D=(1.0/7.0) --> Lines AB and CD are parallel A=(0.0/0.0) B=(0.0/0.0) C=(0.0/3.0) D=(10.0/7.0) --> Points A and B are identical A=(0.0/0.0) B=(3.0/3.0) C=(0.0/0.0) D=(6.0/6.0) --> Lines AB and CD are identicl A=(0.0/0.0) B=(3.0/3.0) C=(0.0/1.0) D=(6.0/7.0) --> Lines AB and CD are parallel
zkl
<lang zkl>fcn lineIntersect(ax,ay, bx,by, cx,cy, dx,dy){ // --> (x,y)
detAB,detCD := det(ax,ay, bx,by), det(cx,cy, dx,dy); abDx,cdDx := ax - bx, cx - dx; // delta x abDy,cdDy := ay - by, cy - dy; // delta y
xnom,ynom := det(detAB,abDx, detCD,cdDx), det(detAB,abDy, detCD,cdDy);
denom := det(abDx,abDy, cdDx,cdDy);
if(denom.closeTo(0.0, 0.0001))
throw(Exception.MathError("lineIntersect: Parallel lines"));
return(xnom/denom, ynom/denom);
} fcn det(a,b,c,d){ a*d - b*c } // determinant</lang> <lang zkl>lineIntersect(4.0,0.0, 6.0,10.0, 0.0,3.0, 10.0,7.0).println();</lang>
- Output:
L(5,5)