Find the intersection of two lines

From Rosetta Code
Find the intersection of two lines is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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).

ALGOL 68[edit]

Using "school maths".

BEGIN
# mode to hold a point #
MODE POINT = STRUCT( REAL x, y );
# mode to hold a line expressed as y = mx + c #
MODE LINE = STRUCT( REAL m, c );
# returns the line that passes through p1 and p2 #
PROC find line = ( POINT p1, p2 )LINE:
IF x OF p1 = x OF p2 THEN
# the line is vertical #
LINE( 0, x OF p1 )
ELSE
# the line is not vertical #
REAL m = ( y OF p1 - y OF p2 ) / ( x OF p1 - x OF p2 );
LINE( m, y OF p1 - ( m * x OF p1 ) )
FI # find line # ;
 
# returns the intersection of two lines - the lines must be distinct and not parallel #
PRIO INTERSECTION = 5;
OP INTERSECTION = ( LINE l1, l2 )POINT:
BEGIN
REAL x = ( c OF l2 - c OF l1 ) / ( m OF l1 - m OF l2 );
POINT( x, ( m OF l1 * x ) + c OF l1 )
END # INTERSECTION # ;
 
# find the intersection of the lines as per the task #
POINT i = find line( POINT( 4.0, 0.0 ), POINT( 6.0, 10.0 ) )
INTERSECTION find line( ( 0.0, 3.0 ), ( 10.0, 7.0 ) );
print( ( fixed( x OF i, -8, 4 ), fixed( y OF i, -8, 4 ), newline ) )
 
END
Output:
  5.0000  5.0000

C#[edit]

using System;
using System.Drawing;
public class Program
{
static PointF FindIntersection(PointF s1, PointF e1, PointF s2, PointF e2) {
float a1 = e1.Y - s1.Y;
float b1 = s1.X - e1.X;
float c1 = a1 * s1.X + b1 * s1.Y;
 
float a2 = e2.Y - s2.Y;
float b2 = s2.X - e2.X;
float c2 = a2 * s2.X + b2 * s2.Y;
 
float delta = a1 * b2 - a2 * b1;
//If lines are parallel, the result will have Infinity values.
return new PointF((b2 * c1 - b1 * c2) / delta, (a1 * c2 - a2 * c1) / delta);
}
 
static void Main() {
Func<float, float, PointF> p = (x, y) => new PointF(x, y);
Console.WriteLine(FindIntersection(p(4f, 0f), p(6f, 10f), p(0f, 3f), p(10f, 7f)));
Console.WriteLine(FindIntersection(p(0f, 0f), p(1f, 1f), p(1f, 2f), p(4f, 5f)));
}
}
Output:
{X=5, Y=5}
{X=-Infinity, Y=-Infinity}

C++[edit]

#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);
 
}
Output:
result 1,5,5

Haskell[edit]

import Data.Maybe (isNothing)
 
type Line = (Point, Point)
 
type Point = (Float, Float)
 
-- INTERSECTION OF TWO LINES --------------------------------------------------
maybeIntersection :: Line -> Line -> Maybe Point
maybeIntersection ((ax, ay), (bx, by)) ((px, py), (qx, qy)) =
if determinant == 0
then Nothing
else let abD = ax * by - ay * bx
pqD = px * qy - py * qx
in Just
( (abD * pqDX - abDX * pqD) / determinant
, (abD * pqDY - abDY * pqD) / determinant)
where
abDX = ax - bx
pqDX = px - qx
abDY = ay - by
pqDY = py - qy
determinant = abDX * pqDY - abDY * pqDX
 
-- TEST -----------------------------------------------------------------------
ab :: Line
ab = ((4.0, 0.0), (6.0, 10.0))
 
pq :: Line
pq = ((0.0, 3.0), (10.0, 7.0))
 
interSection :: Maybe Point
interSection = maybeIntersection ab pq
 
main :: IO ()
main =
putStrLn $
if isNothing interSection
then "(parallel lines – no intersection)"
else (\(Just x) -> show x) interSection
Output:
(5.0,5.0)

JavaScript[edit]

Translation of: Haskell

ES6[edit]

(() => {
'use strict';
 
// INTERSECTION OF TWO LINES ----------------------------------------------
 
// maybeIntersection :: Line -> Line -> Maybe Point
const maybeIntersection = ([
[ax, ay],
[bx, by]
], [
[px, py],
[qx, qy]
]) => {
const
abDX = ax - bx,
pqDX = px - qx,
abDY = ay - by,
pqDY = py - qy,
determinant = abDX * pqDY - abDY * pqDX;
 
return determinant !== 0 ? ({
valid: true,
value: (() => {
const
abD = ax * by - ay * bx,
pqD = px * qy - py * qx;
return [
(abD * pqDX - abDX * pqD) / determinant,
(abD * pqDY - abDY * pqD) / determinant
];
})()
}) : {
valid: false
};
};
 
// TEST -------------------------------------------------------------------
// ab :: Line
const ab = [
[4.0, 0.0],
[6.0, 10.0]
];
 
// pq :: Line
const pq = [
[0.0, 3.0],
[10.0, 7.0]
];
 
// intersection :: Maybe Point
const intersection = maybeIntersection(ab, pq);
 
return intersection.valid ? (
JSON.stringify(intersection.value)
) : '(Parallel lines – no intersection)';
})();
Output:
[5,5]

Kotlin[edit]

Translation of: C#
// version 1.1.1
 
class PointF(val x: Float, val y: Float) {
override fun toString() = "{$x, $y}"
}
 
class LineF(val s: PointF, val e: PointF)
 
fun findIntersection(l1: LineF, l2: LineF): PointF {
val a1 = l1.e.y - l1.s.y
val b1 = l1.s.x - l1.e.x
val c1 = a1 * l1.s.x + b1 * l1.s.y
 
val a2 = l2.e.y - l2.s.y
val b2 = l2.s.x - l2.e.x
val c2 = a2 * l2.s.x + b2 * l2.s.y
 
val delta = a1 * b2 - a2 * b1
// If lines are parallel, intersection point will contain infinite values
return PointF((b2 * c1 - b1 * c2) / delta, (a1 * c2 - a2 * c1) / delta)
}
 
fun main(args: Array<String>) {
var l1: LineF
var l2: LineF
l1 = LineF(PointF(4f, 0f), PointF(6f, 10f))
l2 = LineF(PointF(0f, 3f), PointF(10f, 7f))
println(findIntersection(l1, l2))
l1 = LineF(PointF(0f, 0f), PointF(1f, 1f))
l2 = LineF(PointF(1f, 2f), PointF(4f, 5f))
println(findIntersection(l1, l2))
}
Output:
{5.0, 5.0}
{-Infinity, -Infinity}

Perl[edit]

Translation of: C#

If warning are enabled the second print will issue a warning since we are trying to print out an undef

 
sub intersect {
my ($x1, $y1, $x2, $y2, $x3, $y3, $x4, $y4) = @_;
my $a1 = $y2 - $y1;
my $b1 = $x1 - $x2;
my $c1 = $a1 * $x1 + $b1 * $y1;
my $a2 = $y4 - $y3;
my $b2 = $x3 - $x4;
my $c2 = $a2 * $x3 + $b2 * $y3;
my $delta = $a1 * $b2 - $a2 * $b1;
return (undef, undef) if $delta == 0;
# If delta is 0, i.e. lines are parallel then the below will fail
my $ix = ($b2 * $c1 - $b1 * $c2) / $delta;
my $iy = ($a1 * $c2 - $a2 * $c1) / $delta;
return ($ix, $iy);
}
 
my ($ix, $iy) = intersect(4, 0, 6, 10, 0, 3, 10, 7);
print "$ix $iy\n";
($ix, $iy) = intersect(0, 0, 1, 1, 1, 2, 4, 5);
print "$ix $iy\n";
 

Perl 6[edit]

Works with: Rakudo version 2016.11
Translation of: zkl
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 );
Output:
Intersection point: (5 5)
Intersection point: (5.010893 5.054466)
Intersection point: Lines are parallel

Python[edit]

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))
Output:
POINT (5 5)

Racket[edit]

Translation of: C++
#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))
Output:
5
5

REXX[edit]

version 1[edit]

Naive implementation. To be improved for parallel lines and degenerate lines such as y=5 or x=8.

/* 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')'
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[edit]

complete implementation taking care of all possibilities

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
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

Sidef[edit]

Translation of: Perl 6
func det(a, b, c, d) { a*d - b*c }
 
func intersection(ax, ay, bx, by,
cx, cy, dx, dy) {
 
var detAB = det(ax,ay, bx,by)
var detCD = det(cx,cy, dx,dy)
 
var ΔxAB = (ax - bx)
var ΔyAB = (ay - by)
var ΔxCD = (cx - dx)
var ΔyCD = (cy - dy)
 
var x_numerator = det(detAB, ΔxAB, detCD, ΔxCD)
var y_numerator = det(detAB, ΔyAB, detCD, ΔyCD)
var denominator = det( ΔxAB, ΔyAB, ΔxCD, ΔyCD)
 
denominator == 0 && return 'lines are parallel'
[x_numerator / denominator, y_numerator / denominator]
}
 
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))
Output:
Intersection point: [5, 5]
Intersection point: [2300/459, 2320/459]
Intersection point: lines are parallel

zkl[edit]

Translation of: C++
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
lineIntersect(4.0,0.0, 6.0,10.0,  0.0,3.0, 10.0,7.0).println();
Output:
L(5,5)

References[edit]

  1. [1]