Line–line intersection
Distinguishing these cases and finding the intersection have uses, for example, in computer graphics, motion planning, and collision detection.
These inequalities can be tested without the need for division, allowing rapid determination of the existence of any line segment intersection before calculating its exact point.
[3] The x and y coordinates of the point of intersection of two non-vertical lines can easily be found using the following substitutions and rearrangements.
By using homogeneous coordinates, the intersection point of two implicitly defined lines can be determined quite easily.
The intersection point, if it exists, is given by where Ag is the Moore–Penrose generalized inverse of A (which has the form shown because A has full column rank).
As before there is a unique intersection point if and only if A has full column rank and the augmented matrix [A | b] does not, and the unique intersection if it exists is given by In two or more dimensions, we can usually find a point that is mutually closest to two or more lines in a least-squares sense.
In any number of dimensions, if v̂i is a unit vector along the ith line, then where I is the identity matrix, and so[5] In order to find the intersection point of a set of lines, we calculate the point with minimum distance to them.
Each line is defined by an origin ai and a unit direction vector n̂i.
The sum of distances to the square to all lines is To minimize this expression, we differentiate it with respect to p. which results in where I is the identity matrix.
This is a matrix Sp = C, with solution p = S+C, where S+ is the pseudo-inverse of S. In spherical geometry, any two great circles intersect.
