Points, lines, and planesIn what follows are various notes and algorithms dealing with points, lines, and planes.
Minimum Distance between
Written by Paul Bourke 
 . . . 1 
To derive this result consider the projection of the line (P_{a}  P_{b}) onto the normal of the plane n, that is just P_{a}  P_{b} cos(theta), where theta is the angle between (P_{a}  P_{b}) and the normal n. This projection is the minimum distance of P_{a} to the plane.
This can be written in terms of the dot product as
That is
 . . . 2 
Since point (x_{b}, y_{b}, z_{b}) is a point on the plane
 . . . 3 
Substituting equation 3 into equation 2 gives the result shown in equation 1.
This note describes the technique and algorithm for determining the intersection point of two lines (or line segments) in 2 dimensions.
The equations of the lines are
P_{b} = P3 + u_{b} ( P4  P3 )
Solving for the point where P_{a} = P_{b} gives the following two equations in two unknowns (u_{a} and u_{b})
Solving gives the following expressions for u_{a} and u_{b}
Substituting either of these into the corresponding equation for the line gives the intersection point. For example the intersection point (x,y) is
y = y1 + u_{a} (y2  y1)
Original C code by Paul Bourke.
C++ contribution by Damian Coventry.
LISP implementation by Paul Reiners.
C version for Rockbox firmware by Karl Kurbjun.
C# version by Olaf Rabbachin.
VB.net version by Olaf Rabbachin.
VBA implementation by Giuseppe Iaria.
Javascript version by Leo Bottaro.
Two lines in 3 dimensions generally don't intersect at a point, they may be parallel (no intersections) or they may be coincident (infinite intersections) but most often only their projection onto a plane intersect.. When they don't exactly intersect at a point they can be connected by a line segment, the shortest line segment is unique and is often considered to be their intersection in 3D.
The following will show how to compute this shortest line segment that joins two lines in 3D, it will as a biproduct identify parallel lines. In what follows a line will be defined by two points lying on it, a point on line "a" defined by points P_{1} and P_{2} has an equation. similarly a point on a second line "b" defined by points P_{4} and P_{4} will be written as
The values of mu_{a} and mu_{b} range from negative to positive infinity. The line segments between P_{1} P_{2} and P_{3} P_{4} have their corresponding mu between 0 and 1. 

There are two approaches to finding the shortest line segment between lines "a" and "b". The first is to write down the length of the line segment joining the two lines and then find the minimum. That is, minimise the following
Substituting the equations of the lines gives
The above can then be expanded out in the (x,y,z) components. There are conditions to be met at the minimum, the derivative with respect to mu_{a} and mu_{b} must be zero. Note: it is easy to convince oneself that the above function only has one minima and no other minima or maxima. These two equations can then be solved for mu_{a} and mu_{b}, the actual intersection points found by substituting the values of mu into the original equations of the line.
An alternative approach but one that gives the exact same equations is to realise that the shortest line segment between the two lines will be perpendicular to the two lines. This allows us to write two equations for the dot product as
(P_{a}  P_{b}) dot (P_{4}  P_{3}) = 0
Expanding these given the equation of the lines
( P_{1}  P_{3} + mu_{a} (P_{2}  P_{1})  mu_{b} (P_{4}  P_{3}) ) dot (P_{4}  P_{3}) = 0
Expanding these in terms of the coordinates (x,y,z) is a nightmare but the result is as follows
d_{1343} + mu_{a} d_{4321}  mu_{b} d_{4343} = 0
where
Note that d_{mnop} = d_{opmn}
Finally, solving for mu_{a} gives
and backsubstituting gives mu_{b}
Source Code
Original C source code from the author: lineline.c
Contribution by Dan Wills in MEL (Maya Embedded Language): source.mel.
A Matlab version by Cristian Dima: linelineintersect.m.
A Maxscript function by Chris Johnson: LineLineIntersect.ms
LISP version for AutoCAD (and Intellicad) by Andrew Bennett: int1.lsp and int2.lsp
A contribution by Bruce Vaughan in the form of a Python script for the SDS/2 design software: L3D.py
C# version by Ronald Holthuizen: calclineline.cs
VBA VB6 version by Thomas Ludewig: vbavb6.txt
Contribution by Bryan Hanson: Implementation in R
This note will illustrate the algorithm for finding the intersection of a line and a plane using two possible formulations for a plane.
Substituting in the equation of the line through points P1 (x1,y1,z1) and P2 (x2,y2,z2)
The standard equation of a plane in 3 space is
The normal to the plane is the vector (A,B,C). 

Given three points in space (x1,y1,z1), (x2,y2,z2), (x3,y3,z3) the equation of the plane through these points is given by the following determinants.
Expanding the above gives
A = y1 (z2  z3) + y2 (z3  z1) + y3
(z1  z2)
B = z1 (x2  x3) + z2 (x3  x1) + z3
(x1  x2)
C = x1 (y2  y3) + x2 (y3  y1) + x3
(y1  y2)
 D = x1
(y2 z3  y3 z2) +
x2 (y3 z1  y1 z3) +
x3 (y1 z2  y2 z1)
Note that if the points are collinear then the normal (A,B,C) as calculated above will be (0,0,0).
The sign of s = Ax + By + Cz + D determines which side the point (x,y,z) lies with respect to the plane. If s > 0 then the point lies on the same side as the normal (A,B,C). If s < 0 then it lies on the opposite side, if s = 0 then the point (x,y,z) lies on the plane.
AlternativelyIf vector N is the normal to the plane then all points p on the plane satisfy the following
N . p = k
where . is the dot product between the two vectors.
ie: a . b = (a_{x},a_{y},a_{z}) . (b_{x},b_{y},b_{z}) = a_{x} b_{x} + a_{y} b_{y} + a_{z} b_{z}
Given any point a on the plane
N . (p  a) = 0
Define the two planes with normals N as
N_{2} . p = d_{2}
The equation of the line can be written as
Where "*" is the cross product, "." is the dot product, and u is the parameter of the line.
Taking the dot product of the above with each normal gives two equations with unknowns c_{1} and c_{2}.
N_{2} . p = d_{2} = c_{1} N_{1} . N_{2} + c_{2} N_{2} . N_{2}
Solving for c_{1} and c_{2}
c_{2} = ( d_{2} N_{1} . N_{1}  d_{1} N_{1} . N_{2}) / determinant
determinant = ( N_{1} . N_{1} ) ( N_{2} . N_{2} )  ( N_{1} . N_{2} )^{2}
Note that a test should first be performed to check that the planes aren't parallel or coincident (also parallel), this is most easily achieved by checking that the cross product of the two normals isn't zero. The planes are parallel if
A contribution by Bruce Vaughan in the form of a Python script for the SDS/2 design software: P3D.py.
The intersection of three planes is either a point, a line, or there is no intersection (any two of the planes are parallel).
The three planes can be written as
N_{2} . p = d_{2}
N_{3} . p = d_{3}
In the above and what follows, "." signifies the dot product and "*" is the cross product. The intersection point P is given by:
d_{1} ( N_{2} * N_{3} ) + d_{2} ( N_{3} * N_{1} ) + d_{3} ( N_{1} * N_{2} )  
P =   
N_{1} . ( N_{2} * N_{3} ) 
The denominator is zero if N_{2} * N_{3} = 0, in other words the planes are parallel. Or if N_{1} is a linear combination of N_{2} and N_{3}.
How might one represent a line in polar coordinates?
In Cartesian coordinates it can be represented as:
The derivation is quite straightforward once one realises that for a point (r, theta) the x axis is simply r cos(theta) and the y axis is r sin(theta). Substituting those into the equation for the line gives the following result.
Example from the Graphing Calculator.
Question
Given a line defined by two points L1 L2, a point P1 and angle z (bearing from north) find the intersection point between the direction vector from P1 to the line.
Short answer: choose a second point P2 along the direction vector from P1, say P2 = (x_{P1}+sin(z),y_{P1}+cos(z)). Apply the algorthm here for the intersection of two line segments. Perform the additional test that u_{b} must be greater than 0, the solution where u_{b} is less than 0 is the solution in the direction z+180 degrees.