Line-line intersection

# Line-line intersection

Discussion

Encyclopedia

In Euclidean geometry
Euclidean geometry
Euclidean geometry is a mathematical system attributed to the Alexandrian Greek mathematician Euclid, which he described in his textbook on geometry: the Elements. Euclid's method consists in assuming a small set of intuitively appealing axioms, and deducing many other propositions from these...

, the intersection
Intersection
Intersection has various meanings in different contexts:*In mathematics and geometry**Intersection , the set of elements common to some collection of sets.**Line-line intersection**Line-plane intersection**Lineâ€“sphere intersection...

of a line
Line (mathematics)
The notion of line or straight line was introduced by the ancient mathematicians to represent straight objects with negligible width and depth. Lines are an idealization of such objects...

and a line can be the empty set
Empty set
In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...

,
a point
Point (geometry)
In geometry, topology and related branches of mathematics a spatial point is a primitive notion upon which other concepts may be defined. In geometry, points are zero-dimensional; i.e., they do not have volume, area, length, or any other higher-dimensional analogue. In branches of mathematics...

, or
a line. Distinguishing these cases, and finding the intersection point have use, for example, in computer graphics
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....

, motion planning
Motion planning
Motion planning is a term used in robotics for the process of detailing a task into discrete motions....

, and collision detection
Collision detection
Collision detection typically refers to the computational problem of detecting the intersection of two or more objects. While the topic is most often associated with its use in video games and other physical simulations, it also has applications in robotics...

.

The number and locations of possible intersections between two lines and the number of possible lines with no intersections (parallel
Parallel (geometry)
Parallelism is a term in geometry and in everyday life that refers to a property in Euclidean space of two or more lines or planes, or a combination of these. The assumed existence and properties of parallel lines are the basis of Euclid's parallel postulate. Two lines in a plane that do not...

) with a given line are the distinguishing features of Non-Euclidean geometry
Non-Euclidean geometry
Non-Euclidean geometry is the term used to refer to two specific geometries which are, loosely speaking, obtained by negating the Euclidean parallel postulate, namely hyperbolic and elliptic geometry. This is one term which, for historical reasons, has a meaning in mathematics which is much...

.

## Mathematics

The intersection of two lines and in 2 dimensional space. With line being defined by two points and , and line being defined by two points and .

The intersection of line and can be defined using determinant
Determinant
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...

s.

The determinants can be written out as:

Note that the intersection point is for the infinitely long lines defined by the points, rather than the line segment
Line segment
In geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. Examples of line segments include the sides of a triangle or square. More generally, when the end points are both vertices of a polygon, the line segment...

s between the points, and can produce an intersection point beyond the lengths of the line segments.

## n-line intersection

In two dimensions, more than two lines almost certainly do not intersect at a single point. Similarly, in three or more dimensions, even two lines almost certainly do not intersect. However, 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 the two-dimensional case, first, represent line i as a point on the line and a normal vector, perpendicular to that line. That is, if and are points on line 1, then let and let
which is the unit vector along the line, rotated by 90 degrees.

Note that the distance from a point, x to the line (p, n) is given by.
And so the squared distance from a point, x, to a line is.
the sum of squared distances to many lines is the cost function:
This can be rearranged:

To find the minimum, we differentiate with respect to x and set the result equal to the zero vector:
so
and so.
This can be generalized to any number of dimensions by noting that is the simply the (symmetric) matrix with all eigenvalues unity except for a zero eigenvalue in the direction along the line providing a seminorm on the distance between and another point giving the distance to the line. In any number of dimensions, if is a unit vector along the ith line, then
becomes

where I is the identity matrix, and so
.

• Line segment intersection
Line segment intersection
In computational geometry, the line segment intersection problem supplies a list of line segments in the plane and asks us to determine whether any two of them intersect, or cross....

• Line intersection in projective space
• Distance from a point to a line
Distance from a point to a line
The distance from a point to a line is the shortest distance from a point to a line in Euclidean geometry. It can be calculated in the following ways.-Cartesian coordinates:...

• Parallel postulate
Parallel postulate
In geometry, the parallel postulate, also called Euclid's fifth postulate because it is the fifth postulate in Euclid's Elements, is a distinctive axiom in Euclidean geometry...