Line-line intersection - AbsoluteAstronomy.com

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

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:

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

External links

Distance between Lines and Segments with their Closest Point of Approach, applicable to two, three, or more dimensions.

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.

Mathematics

n-line intersection

See also

External links