Find the intersection of a line with a plane
Finding the intersection of an infinite ray with a plane in 3D is an important topic in collision detection.
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
Find the point of intersection for the infinite ray with direction (0,-1,-1) passing through position (0, 0, 10) with the infinite plane with a normal vector of (0, 0, 1) and which passes through [0, 0, 5].
C
Straightforward application of the intersection formula, prints usage on incorrect invocation. <lang C> /*Abhishek Ghosh, 12th October 2017*/
- include<stdio.h>
typedef struct{ double x,y,z; }vector;
vector addVectors(vector a,vector b){ return (vector){a.x+b.x,a.y+b.y,a.z+b.z}; }
vector subVectors(vector a,vector b){ return (vector){a.x-b.x,a.y-b.y,a.z-b.z}; }
double dotProduct(vector a,vector b){ return a.x*b.x + a.y*b.y + a.z*b.z; }
vector scaleVector(double l,vector a){ return (vector){l*a.x,l*a.y,l*a.z}; }
vector intersectionPoint(vector lineVector, vector linePoint, vector planeNormal, vector planePoint){ vector diff = subVectors(linePoint,planePoint);
return addVectors(addVectors(diff,planePoint),scaleVector(-dotProduct(diff,planeNormal)/dotProduct(lineVector,planeNormal),lineVector)); }
int main(int argC,char* argV[]) { vector lV,lP,pN,pP,iP;
if(argC!=5) printf("Usage : %s <line direction, point on line, normal to plane and point on plane given as (x,y,z) tuples separated by space>"); else{ sscanf(argV[1],"(%lf,%lf,%lf)",&lV.x,&lV.y,&lV.z); sscanf(argV[3],"(%lf,%lf,%lf)",&pN.x,&pN.y,&pN.z);
if(dotProduct(lV,pN)==0) printf("Line and Plane do not intersect, either parallel or line is on the plane"); else{ sscanf(argV[2],"(%lf,%lf,%lf)",&lP.x,&lP.y,&lP.z); sscanf(argV[4],"(%lf,%lf,%lf)",&pP.x,&pP.y,&pP.z);
iP = intersectionPoint(lV,lP,pN,pP);
printf("Intersection point is (%lf,%lf,%lf)",iP.x,iP.y,iP.z); } }
return 0; } </lang> Invocation and output:
C:\rosettaCode>linePlane.exe (0,-1,-1) (0,0,10) (0,0,1) (0,0,5) Intersection point is (0.000000,-5.000000,5.000000)
D
<lang D>import std.stdio;
struct Vector3D {
private real x; private real y; private real z;
this(real x, real y, real z) {
this.x = x;
this.y = y;
this.z = z;
}
auto opBinary(string op)(Vector3D rhs) const {
static if (op == "+" || op == "-") {
mixin("return Vector3D(x" ~ op ~ "rhs.x, y" ~ op ~ "rhs.y, z" ~ op ~ "rhs.z);");
}
}
auto opBinary(string op : "*")(real s) const {
return Vector3D(s*x, s*y, s*z);
}
auto dot(Vector3D rhs) const {
return x*rhs.x + y*rhs.y + z*rhs.z;
}
void toString(scope void delegate(const(char)[]) sink) const {
import std.format;
sink("(");
formattedWrite!"%f"(sink, x);
sink(",");
formattedWrite!"%f"(sink, y);
sink(",");
formattedWrite!"%f"(sink, z);
sink(")");
}
}
auto intersectPoint(Vector3D rayVector, Vector3D rayPoint, Vector3D planeNormal, Vector3D planePoint) {
auto diff = rayPoint - planePoint; auto prod1 = diff.dot(planeNormal); auto prod2 = rayVector.dot(planeNormal); auto prod3 = prod1 / prod2; return rayPoint - rayVector * prod3;
}
void main() {
auto rv = Vector3D(0.0, -1.0, -1.0);
auto rp = Vector3D(0.0, 0.0, 10.0);
auto pn = Vector3D(0.0, 0.0, 1.0);
auto pp = Vector3D(0.0, 0.0, 5.0);
auto ip = intersectPoint(rv, rp, pn, pp);
writeln("The ray intersects the plane at ", ip);
}</lang>
- Output:
The ray intersects the plane at (0.000000,-5.000000,5.000000)
Haskell
Note that V3 is implemented similarly in the external library linear. <lang Haskell>import Control.Applicative (liftA2) import Text.Printf (printf)
data V3 a = V3 a a a
deriving Show
instance Functor V3 where
fmap f (V3 a b c) = V3 (f a) (f b) (f c)
instance Applicative V3 where
pure a = V3 a a a V3 a b c <*> V3 d e f = V3 (a d) (b e) (c f)
instance Num a => Num (V3 a) where
(+) = liftA2 (+) (-) = liftA2 (-) (*) = liftA2 (*) negate = fmap negate abs = fmap abs signum = fmap signum fromInteger = pure . fromInteger
dot ::Num a => V3 a -> V3 a -> a dot a b = x + y + z
where V3 x y z = a * b
intersect :: Fractional a => V3 a -> V3 a -> V3 a -> V3 a -> V3 a intersect rayVector rayPoint planeNormal planePoint =
rayPoint - rayVector * pure prod3 where diff = rayPoint - planePoint prod1 = diff `dot` planeNormal prod2 = rayVector `dot` planeNormal prod3 = prod1 / prod2
main = printf "The ray intersects the plane at (%f, %f, %f)\n" x y z
where V3 x y z = intersect rv rp pn pp :: V3 Double rv = V3 0 (-1) (-1) rp = V3 0 0 10 pn = V3 0 0 1 pp = V3 0 0 5</lang>
- Output:
The ray intersects the plane at (0.0, -5.0, 5.0)
J
Solution: <lang j>mp=: +/ .* NB. matrix product p=: mp&{: %~ -&{. mp {:@] NB. solve intersectLinePlane=: {.@[ - {:@[ * p</lang> Example Usage: <lang j> Line=: 0 0 10 ,: 0 _1 _1 NB. Point, Ray
Plane=: 0 0 5 ,: 0 0 1 NB. Point, Normal Line intersectLinePlane Plane
0 _5 5</lang>
Java
<lang Java>public class LinePLaneIntersection {
private static class Vector3D {
private double x, y, z;
Vector3D(double x, double y, double z) {
this.x = x;
this.y = y;
this.z = z;
}
Vector3D plus(Vector3D v) {
return new Vector3D(x + v.x, y + v.y, z + v.z);
}
Vector3D minus(Vector3D v) {
return new Vector3D(x - v.x, y - v.y, z - v.z);
}
Vector3D times(double s) {
return new Vector3D(s * x, s * y, s * z);
}
double dot(Vector3D v) {
return x * v.x + y * v.y + z * v.z;
}
@Override
public String toString() {
return String.format("(%f, %f, %f)", x, y, z);
}
}
private static Vector3D intersectPoint(Vector3D rayVector, Vector3D rayPoint, Vector3D planeNormal, Vector3D planePoint) {
Vector3D diff = rayPoint.minus(planePoint);
double prod1 = diff.dot(planeNormal);
double prod2 = rayVector.dot(planeNormal);
double prod3 = prod1 / prod2;
return rayPoint.minus(rayVector.times(prod3));
}
public static void main(String[] args) {
Vector3D rv = new Vector3D(0.0, -1.0, -1.0);
Vector3D rp = new Vector3D(0.0, 0.0, 10.0);
Vector3D pn = new Vector3D(0.0, 0.0, 1.0);
Vector3D pp = new Vector3D(0.0, 0.0, 5.0);
Vector3D ip = intersectPoint(rv, rp, pn, pp);
System.out.println("The ray intersects the plane at " + ip);
}
}</lang>
- Output:
The ray intersects the plane at (0.000000, -5.000000, 5.000000)
Julia
<lang julia>function lineplanecollision(planenorm::Vector, planepnt::Vector, raydir::Vector, raypnt::Vector)
ndotu = dot(planenorm, raydir)
if ndotu ≈ 0 error("no intersection or line is within plane") end
w = raypnt - planepnt si = -dot(planenorm, w) / ndotu ψ = w .+ si .* raydir .+ planepnt return ψ
end
- Define plane
planenorm = Float64[0, 0, 1] planepnt = Float64[0, 0, 5]
- Define ray
raydir = Float64[0, -1, -1] raypnt = Float64[0, 0, 10]
ψ = lineplanecollision(planenorm, planepnt, raydir, raypnt) println("Intersection at $ψ")</lang>
- Output:
Intersection at [0.0, -5.0, 5.0]
Kotlin
<lang scala>// version 1.1.51
class Vector3D(val x: Double, val y: Double, val z: Double) {
operator fun plus(v: Vector3D) = Vector3D(x + v.x, y + v.y, z + v.z)
operator fun minus(v: Vector3D) = Vector3D(x - v.x, y - v.y, z - v.z)
operator fun times(s: Double) = Vector3D(s * x, s * y, s * z)
infix fun dot(v: Vector3D) = x * v.x + y * v.y + z * v.z
override fun toString() = "($x, $y, $z)"
}
fun intersectPoint(
rayVector: Vector3D, rayPoint: Vector3D, planeNormal: Vector3D, planePoint: Vector3D
): Vector3D {
val diff = rayPoint - planePoint val prod1 = diff dot planeNormal val prod2 = rayVector dot planeNormal val prod3 = prod1 / prod2 return rayPoint - rayVector * prod3
}
fun main(args: Array<String>) {
val rv = Vector3D(0.0, -1.0, -1.0)
val rp = Vector3D(0.0, 0.0, 10.0)
val pn = Vector3D(0.0, 0.0, 1.0)
val pp = Vector3D(0.0, 0.0, 5.0)
val ip = intersectPoint(rv, rp, pn, pp)
println("The ray intersects the plane at $ip")
}</lang>
- Output:
The ray intersects the plane at (0.0, -5.0, 5.0)
MATLAB
<lang MATLAB>function point = intersectPoint(rayVector, rayPoint, planeNormal, planePoint)
pdiff = rayPoint - planePoint; prod1 = dot(pdiff, planeNormal); prod2 = dot(rayVector, planeNormal); prod3 = prod1 / prod2;
point = rayPoint - rayVector * prod3;</lang>
- Output:
<lang MATLAB>>> intersectPoint([0 -1 -1], [0 0 10], [0 0 1], [0 0 5])
ans =
0 -5 5
</lang>
Modula-2
<lang modula2>MODULE LinePlane; FROM RealStr IMPORT RealToStr; FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
TYPE
Vector3D = RECORD
x,y,z : REAL;
END;
PROCEDURE Minus(lhs,rhs : Vector3D) : Vector3D; VAR out : Vector3D; BEGIN
RETURN Vector3D{lhs.x-rhs.x, lhs.y-rhs.y, lhs.z-rhs.z};
END Minus;
PROCEDURE Times(a : Vector3D; s : REAL) : Vector3D; BEGIN
RETURN Vector3D{a.x*s, a.y*s, a.z*s};
END Times;
PROCEDURE Dot(lhs,rhs : Vector3D) : REAL; BEGIN
RETURN lhs.x*rhs.x + lhs.y*rhs.y + lhs.z*rhs.z;
END Dot;
PROCEDURE ToString(self : Vector3D); VAR buf : ARRAY[0..63] OF CHAR; BEGIN
WriteString("(");
RealToStr(self.x,buf);
WriteString(buf);
WriteString(", ");
RealToStr(self.y,buf);
WriteString(buf);
WriteString(", ");
RealToStr(self.z,buf);
WriteString(buf);
WriteString(")");
END ToString;
PROCEDURE IntersectPoint(rayVector,rayPoint,planeNormal,planePoint : Vector3D) : Vector3D; VAR
diff : Vector3D; prod1,prod2,prod3 : REAL;
BEGIN
diff := Minus(rayPoint,planePoint); prod1 := Dot(diff, planeNormal); prod2 := Dot(rayVector, planeNormal); prod3 := prod1 / prod2; RETURN Minus(rayPoint, Times(rayVector, prod3));
END IntersectPoint;
VAR ip : Vector3D; BEGIN
ip := IntersectPoint(Vector3D{0.0,-1.0,-1.0},Vector3D{0.0,0.0,10.0},Vector3D{0.0,0.0,1.0},Vector3D{0.0,0.0,5.0});
WriteString("The ray intersects the plane at ");
ToString(ip);
WriteLn;
ReadChar;
END LinePlane.</lang>
Perl 6
<lang perl6>class Line {
has $.P0; # point has $.u⃗; # ray
} class Plane {
has $.V0; # point has $.n⃗; # normal
}
sub infix:<∙> ( @a, @b where +@a == +@b ) { [+] @a «*» @b } # dot product
sub line-plane-intersection ($𝑳, $𝑷) {
my $cos = $𝑷.n⃗ ∙ $𝑳.u⃗; # cosine between normal & ray
return 'Vectors are orthogonal; no intersection or line within plane'
if $cos == 0;
my $𝑊 = $𝑳.P0 «-» $𝑷.V0; # difference between P0 and V0
my $S𝐼 = -($𝑷.n⃗ ∙ $𝑊) / $cos; # line segment where it intersects the plane
$𝑊 «+» $S𝐼 «*» $𝑳.u⃗ «+» $𝑷.V0; # point where line intersects the plane
}
say 'Intersection at point: ', line-plane-intersection(
Line.new( :P0(0,0,10), :u⃗(0,-1,-1) ), Plane.new( :V0(0,0, 5), :n⃗(0, 0, 1) ) );</lang>
- Output:
Intersection at point: (0 -5 5)
Python
Based on the approach at geomalgorithms.com[1]
<lang python>#!/bin/python from __future__ import print_function import numpy as np
def LinePlaneCollision(planeNormal, planePoint, rayDirection, rayPoint, epsilon=1e-6):
ndotu = planeNormal.dot(rayDirection) if abs(ndotu) < epsilon: raise RuntimeError("no intersection or line is within plane")
w = rayPoint - planePoint si = -planeNormal.dot(w) / ndotu Psi = w + si * rayDirection + planePoint return Psi
if __name__=="__main__":
#Define plane
planeNormal = np.array([0, 0, 1])
planePoint = np.array([0, 0, 5]) #Any point on the plane
#Define ray rayDirection = np.array([0, -1, -1]) rayPoint = np.array([0, 0, 10]) #Any point along the ray
Psi = LinePlaneCollision(planeNormal, planePoint, rayDirection, rayPoint) print ("intersection at", Psi)</lang>
- Output:
intersection at [ 0 -5 5]
Racket
<lang racket>#lang racket
- vectors are represented by lists
(struct Line (P0 u⃗))
(struct Plane (V0 n⃗))
(define (· a b) (apply + (map * a b)))
(define (line-plane-intersection L P)
(match-define (cons (Line P0 u⃗) (Plane V0 n⃗)) (cons L P)) (define cos (· n⃗ u⃗)) (when (zero? cos) (error "vectors are orthoganal")) (define W (map - P0 V0)) (define *SI (let ((SI (- (/ (· n⃗ W) cos)))) (λ (n) (* SI n)))) (map + W (map *SI u⃗) V0))
(module+ test
(require rackunit)
(check-equal?
(line-plane-intersection (Line '(0 0 10) '(0 -1 -1))
(Plane '(0 0 5) '(0 0 1)))
'(0 -5 5)))</lang>
- Output:
No output -- all tests passed!
REXX
version 1
This program does NOT handle the case when the line is parallel to or within the plane. <lang rexx>/* REXX */ Parse Value '0 0 1' With n.1 n.2 n.3 /* Normal Vector of the plane */ Parse Value '0 0 5' With p.1 p.2 p.3 /* Point in the plane */ Parse Value '0 0 10' With a.1 a.2 a.3 /* Point of the line */ Parse Value '0 -1 -1' With v.1 v.2 v.3 /* Vector of the line */
a=n.1 b=n.2 c=n.3 d=n.1*p.1+n.2*p.2+n.3*p.3 /* Parameter form of the plane */ Say a'*x +' b'*y +' c'*z =' d
t=(d-(a*a.1+b*a.2+c*a.3))/(a*v.1+b*v.2+c*v.3)
x=a.1+t*v.1 y=a.2+t*v.2 z=a.3+t*v.3
Say 'Intersection: P('||x','y','z')'</lang>
- Output:
0*x + 0*y + 1*z = 5 Intersection: P(0,-5,5)
version 2
handle the case that the line is parallel to the plane or lies within it. <lang rexx>/*REXX*/ Parse Value '1 2 3' With n.1 n.2 n.3 Parse Value '3 3 3' With p.1 p.2 p.3 Parse Value '0 2 4' With a.1 a.2 a.3 Parse Value '3 2 1' With v.1 v.2 v.3
a=n.1 b=n.2 c=n.3 d=n.1*p.1+n.2*p.2+n.3*p.3 /* Parameter form of the plane */ Select
When a=0 Then pd= When a=1 Then pd='x' When a=-1 Then pd='-x' Otherwise pd=a'*x' End
pd=pd yy=mk2('y',b) Select
When left(yy,1)='-' Then pd=pd '-' substr(yy,2) When left(yy,1)='0' Then Nop Otherwise pd=pd '+' yy End
zz=mk2('z',c) Select
When left(zz,1)='-' Then pd=pd '-' substr(zz,2) When left(zz,1)='0' Then Nop Otherwise pd=pd '+' zz End
pd=pd '=' d
Say 'Plane definition:' pd
ip=0 Do i=1 To 3
ip=ip+n.i*v.i dd=n.1*a.1+n.2*a.2+n.3*a.3 End
If ip=0 Then Do
If dd=d Then Say 'Line is part of the plane' Else Say 'Line is parallel to the plane' Exit End
t=(d-(a*a.1+b*a.2+c*a.3))/(a*v.1+b*v.2+c*v.3)
x=a.1+t*v.1 y=a.2+t*v.2 z=a.3+t*v.3
ld=mk('x',a.1,v.1) ';' mk('y',a.2,v.2) ';' mk('z',a.3,v.3) Say 'Line definition:' ld
Say 'Intersection: P('||x','y','z')' Exit
Mk: Procedure /*---------------------------------------------------------------------
- build part of line definition
- --------------------------------------------------------------------*/
Parse Arg v,aa,vv If aa<>0 Then
res=v'='aa
Else
res=v'='
Select
When vv=0 Then
res=res||'0'
When vv=-1 Then
res=res||'-t'
When vv<0 Then
res=res||vv'*t'
Otherwise Do
If res=v'=' Then Do
If vv=1 Then
res=res||'t'
Else
res=res||vv'*t'
End
Else Do
If vv=1 Then
res=res||'+t'
Else
res=res||'+'vv'*t'
End
End
End
Return res
mk2: Procedure /*---------------------------------------------------------------------
- build part of plane definition
- --------------------------------------------------------------------*/
Parse Arg v,u Select
When u=0 Then
res=
When u=1 Then
res=v
When u=-1 Then
res='-'v
When u<0 Then
res=u'*'v
Otherwise Do
If pd<> Then
res='+'u'*'v
Else
res=u'*'v
End
End
Return res </lang>
- Output:
Plane definition: x+2*y+3*z=18 Line definition: x=3*t ; y=2+2*t ; z=4+t Intersection: P(0.6,2.4,4.2)
Sidef
<lang ruby>struct Line {
P0, # point u⃗, # ray
}
struct Plane {
V0, # point n⃗, # normal
}
func dot_prod(a, b) { a »*« b -> sum }
func line_plane_intersection(𝑳, 𝑷) {
var cos = dot_prod(𝑷.n⃗, 𝑳.u⃗) ->
|| return 'Vectors are orthogonal'
var 𝑊 = (𝑳.P0 »-« 𝑷.V0)
var S𝐼 = -(dot_prod(𝑷.n⃗, 𝑊) / cos)
𝑊 »+« (𝑳.u⃗ »*» S𝐼) »+« 𝑷.V0
}
say ('Intersection at point: ', line_plane_intersection(
Line(P0: [0,0,10], u⃗: [0,-1,-1]),
Plane(V0: [0,0, 5], n⃗: [0, 0, 1]),
))</lang>
- Output:
Intersection at point: [0, -5, 5]
zkl
<lang zkl>class Line { fcn init(pxyz, ray_xyz) { var pt=pxyz, ray=ray_xyz; } } class Plane{ fcn init(pxyz, normal_xyz){ var pt=pxyz, normal=normal_xyz; } }
fcn dotP(a,b){ a.zipWith('*,b).sum(0.0); } # dot product --> x fcn linePlaneIntersection(line,plane){
cos:=dotP(plane.normal,line.ray); # cosine between normal & ray
_assert_((not cos.closeTo(0,1e-6)),
"Vectors are orthoganol; no intersection or line within plane");
w:=line.pt.zipWith('-,plane.pt); # difference between P0 and V0
si:=-dotP(plane.normal,w)/cos; # line segment where it intersets the plane
# point where line intersects the plane:
//w.zipWith('+,line.ray.apply('*,si)).zipWith('+,plane.pt); // or
w.zipWith('wrap(w,r,pt){ w + r*si + pt },line.ray,plane.pt);
}</lang> <lang zkl>println("Intersection at point: ", linePlaneIntersection(
Line( T(0.0, 0.0, 10.0), T(0.0, -1.0, -1.0) ), Plane(T(0.0, 0.0, 5.0), T(0.0, 0.0, 1.0) ))
);</lang>
- Output:
Intersection at point: L(0,-5,5)
References