Line segment intersection
   HOME

TheInfoList



OR:

In
geometry Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...
, an intersection is a point, line, or curve common to two or more objects (such as lines, curves, planes, and surfaces). The simplest case in
Euclidean geometry Euclidean geometry is a mathematical system attributed to ancient Greek mathematician Euclid, which he described in his textbook on geometry: the '' Elements''. Euclid's approach consists in assuming a small set of intuitively appealing axioms ...
is the
line–line intersection In Euclidean geometry, the intersection of a line and a line can be the empty set, a point, or another line. Distinguishing these cases and finding the intersection have uses, for example, in computer graphics, motion planning, and collision de ...
between two distinct lines, which either is one point or does not exist (if the lines are
parallel Parallel is a geometric term of location which may refer to: Computing * Parallel algorithm * Parallel computing * Parallel metaheuristic * Parallel (software), a UNIX utility for running programs in parallel * Parallel Sysplex, a cluster o ...
). Other types of geometric intersection include: *
Line–plane intersection In analytic geometry, the intersection of a line and a plane in three-dimensional space can be the empty set, a point, or a line. It is the entire line if that line is embedded in the plane, and is the empty set if the line is parallel to the pla ...
*
Line–sphere intersection In analytic geometry, a line and a sphere can intersect in three ways: # No intersection at all # Intersection in exactly one point # Intersection in two points. Methods for distinguishing these cases, and determining the coordinates for the p ...
* Intersection of a polyhedron with a line * Line segment intersection * Intersection curve Determination of the intersection of
flats Flat or flats may refer to: Architecture * Flat (housing), an apartment in the United Kingdom, Ireland, Australia and other Commonwealth countries Arts and entertainment * Flat (music), a symbol () which denotes a lower pitch * Flat (soldier), ...
– linear geometric objects embedded in a higher-
dimension In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coord ...
al space – is a simple task of
linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrice ...
, namely the solution of a
system of linear equations In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variables. For example, :\begin 3x+2y-z=1\\ 2x-2y+4z=-2\\ -x+\fracy-z=0 \end is a system of three equations in t ...
. In general the determination of an intersection leads to non-linear equations, which can be solved numerically, for example using
Newton iteration In numerical analysis, Newton's method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real-val ...
. Intersection problems between a line and a
conic section In mathematics, a conic section, quadratic curve or conic is a curve obtained as the intersection of the surface of a cone with a plane. The three types of conic section are the hyperbola, the parabola, and the ellipse; the circle is a ...
(circle, ellipse, parabola, etc.) or a
quadric In mathematics, a quadric or quadric surface (quadric hypersurface in higher dimensions), is a generalization of conic sections (ellipses, parabolas, and hyperbolas). It is a hypersurface (of dimension ''D'') in a -dimensional space, and it is de ...
(sphere, cylinder, hyperboloid, etc.) lead to
quadratic equation In algebra, a quadratic equation () is any equation that can be rearranged in standard form as ax^2 + bx + c = 0\,, where represents an unknown value, and , , and represent known numbers, where . (If and then the equation is linear, not qu ...
s that can be easily solved. Intersections between quadrics lead to
quartic equation In mathematics, a quartic equation is one which can be expressed as a ''quartic function'' equaling zero. The general form of a quartic equation is :ax^4+bx^3+cx^2+dx+e=0 \, where ''a'' ≠ 0. The quartic is the highest order polynomi ...
s that can be solved algebraically.


On a plane


Two lines

For the determination of the intersection point of two non-parallel lines a_1x+b_1y=c_1, \ a_2x+b_2y=c_2 one gets, from
Cramer's rule In linear algebra, Cramer's rule is an explicit formula for the solution of a system of linear equations with as many equations as unknowns, valid whenever the system has a unique solution. It expresses the solution in terms of the determinants o ...
or by substituting out a variable, the coordinates of the intersection point (x_s,y_s) : : x_s=\frac , \quad y_s=\frac. \ (If a_1b_2-a_2b_1=0 the lines are parallel and these formulas cannot be used because they involve dividing by 0.)


Two line segments

For two non-parallel
line segment In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between i ...
s (x_1,y_1),(x_2,y_2) and (x_3,y_3),(x_4,y_4) there is not necessarily an intersection point (see diagram), because the intersection point (x_0,y_0) of the corresponding lines need not to be contained in the line segments. In order to check the situation one uses parametric representations of the lines: : (x(s),y(s))=(x_1+s(x_2-x_1),y_1+s(y_2-y_1)), : (x(t),y(t))=(x_3+t(x_4-x_3),y_3+t(y_4-y_3)). The line segments intersect only in a common point (x_0,y_0) of the corresponding lines if the corresponding parameters s_0,t_0 fulfill the condition 0\le s_0,t_0 \le 1 . The parameters s_0,t_0 are the solution of the linear system : s(x_2-x_1)-t(x_4-x_3)=x_3-x_1, : s(y_2-y_1)-t(y_4-y_3)=y_3-y_1 \ . It can be solved for ''s'' and ''t'' using Cramer's rule (see above). If the condition 0\le s_0,t_0 \le 1 is fulfilled one inserts s_0 or t_0 into the corresponding parametric representation and gets the intersection point (x_0,y_0). ''Example:'' For the line segments (1,1),(3,2) and (1,4),(2,-1) one gets the linear system : 2s-t=0 :s+5t=3 and s_0=\tfrac, t_0=\tfrac. That means: the lines intersect at point (\tfrac,\tfrac). ''Remark:'' Considering lines, instead of segments, determined by pairs of points, each condition 0\le s_0,t_0 \le 1 can be dropped and the method yields the intersection point of the lines (see above).


A line and a circle

For the intersection of *line ax+by=c and
circle A circle is a shape consisting of all points in a plane that are at a given distance from a given point, the centre. Equivalently, it is the curve traced out by a point that moves in a plane so that its distance from a given point is cons ...
x^2+y^2=r^2 one solves the line equation for or and substitutes it into the equation of the circle and gets for the solution (using the formula of a quadratic equation) (x_1,y_1),(x_2,y_2) with :x_= \frac \ , :y_= \frac \ , if r^2(a^2+b^2)-c^2 > 0 \ . If this condition holds with strict inequality, there are two intersection points; in this case the line is called a
secant line Secant is a term in mathematics derived from the Latin ''secare'' ("to cut"). It may refer to: * a secant line, in geometry * the secant variety, in algebraic geometry * secant (trigonometry) (Latin: secans), the multiplicative inverse (or recipr ...
of the circle, and the line segment connecting the intersection points is called a chord of the circle. If r^2(a^2+b^2)-c^2=0 holds, there exists only one intersection point and the line is tangent to the circle. If the weak inequality does not hold, the line does not intersect the circle.
If the circle's midpoint is not the origin, see. The intersection of a line and a parabola or hyperbola may be treated analogously.


Two circles

The determination of the intersection points of two circles * (x-x_1)^2+(y-y_1)^2=r_1^2 ,\ \quad (x-x_2)^2+(y-y_2)^2=r_2^2 can be reduced to the previous case of intersecting a line and a circle. By subtraction of the two given equations one gets the line equation: :2(x_2-x_1)x+2(y_2-y_1)y=r_1^2-x_1^2-y_1^2-r_2^2+x_2^2+y_2^2. This special line is the radical line of the two circles. Special case \;x_1=y_1=y_2=0 :
In this case the origin is the center of the first circle and the second center lies on the x-axis (s. diagram). The equation of the radical line simplifies to \;2x_2x=r_1^2-r_2^2+x_2^2\; and the points of intersection can be written as (x_0,\pm y_0) with :x_0=\frac,\quad y_0 =\sqrt\ . In case of r_1^2 the circles have no points in common.
In case of r_1^2=x_0^2 the circles have one point in common and the radical line is a common tangent. Any general case as written above can be transformed by a shift and a rotation into the special case. The intersection of two disks (the interiors of the two circles) forms a shape called a
lens A lens is a transmissive optical device which focuses or disperses a light beam by means of refraction. A simple lens consists of a single piece of transparent material, while a compound lens consists of several simple lenses (''elements ...
.


Two conic sections

The problem of intersection of an ellipse/hyperbola/parabola with another
conic section In mathematics, a conic section, quadratic curve or conic is a curve obtained as the intersection of the surface of a cone with a plane. The three types of conic section are the hyperbola, the parabola, and the ellipse; the circle is a ...
leads to a system of quadratic equations, which can be solved in special cases easily by elimination of one coordinate. Special properties of conic sections may be used to obtain a
solution Solution may refer to: * Solution (chemistry), a mixture where one substance is dissolved in another * Solution (equation), in mathematics ** Numerical solution, in numerical analysis, approximate solutions within specified error bounds * Solutio ...
. In general the intersection points can be determined by solving the equation by a Newton iteration. If a) both conics are given implicitly (by an equation) a 2-dimensional Newton iteration b) one implicitly and the other parametrically given a 1-dimensional Newton iteration is necessary. See next section.


Two smooth curves

Two curves in \R^2 (two-dimensional space), which are continuously differentiable (i.e. there is no sharp bend), have an intersection point, if they have a point of the plane in common and have at this point : a: different tangent lines ( transversal intersection), or : b: the tangent line in common and they are crossing each other (touching intersection, see diagram). If both the curves have a point and the tangent line there in common but do not cross each other, they are just ''touching'' at point . Because touching intersections appear rarely and are difficult to deal with, the following considerations omit this case. In any case below all necessary differential conditions are presupposed. The determination of intersection points always leads to one or two non-linear equations which can be solved by Newton iteration. A list of the appearing cases follows: *If ''both curves are explicitly'' given: y=f_1(x), \ y=f_2(x), equating them yields the equation :: f_1(x)=f_2(x) \ . *If ''both curves are parametrically'' given: C_1: (x_1(t),y_1(t)), \ C_2: (x_2(s),y_2(s)). : Equating them yields two equations in two variables: :: x_1(t)=x_2(s), \ y_1(t)=y_2(s) \ . *If ''one curve is parametrically and the other implicitly'' given: C_1: (x_1(t),y_1(t)), \ C_2: f(x,y)=0. :This is the simplest case besides the explicit case. One has to insert the parametric representation of C_1 into the equation f(x,y)=0 of curve C_2 and one gets the equation: ::f(x_1(t),y_2(t))=0 \ . *If ''both curves are implicitly'' given: C_1: f_1(x,y)=0, \ C_2: f_2(x,y)=0. : Here, an intersection point is a solution of the system ::f_1(x,y)=0, \ f_2(x,y)=0 \ . Any Newton iteration needs convenient starting values, which can be derived by a visualization of both the curves. A parametrically or explicitly given curve can easily be visualized, because to any parameter or respectively it is easy to calculate the corresponding point. For implicitly given curves this task is not as easy. In this case one has to determine a curve point with help of starting values and an iteration. See . ''Examples:'' :1: C_1: (t,t^3) and circle C_2: (x-1)^2+(y-1)^2-10=0 (see diagram). :: The Newton iteration t_:=t_n-\frac for function :::f(t)=(t-1)^2+(t^3-1)^2-10 has to be done. As start values one can choose −1 and 1.5. ::The intersection points are: (−1.1073, −1.3578), (1.6011, 4.1046) :2:C_1: f_1(x,y)=x^4+y^4-1=0, :: C_2: f_2(x,y)=(x-0.5)^2+(y-0.5)^2-1=0 (see diagram). :: The Newton iteration :::= has to be performed, where is the solution of the linear system :::\begin \frac & \frac \\ \frac & \frac \end= at point (x_n,y_n). As starting values one can choose(−0.5, 1) and (1, −0.5). :: The linear system can be solved by Cramer's rule. ::The intersection points are (−0.3686, 0.9953) and (0.9953, −0.3686).


Two polygons

If one wants to determine the intersection points of two
polygon In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed '' polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two ...
s, one can check the intersection of any pair of line segments of the polygons (see above). For polygons with many segments this method is rather time-consuming. In practice one accelerates the intersection algorithm by using ''window tests''. In this case one divides the polygons into small sub-polygons and determines the smallest window (rectangle with sides parallel to the coordinate axes) for any sub-polygon. Before starting the time-consuming determination of the intersection point of two line segments any pair of windows is tested for common points. See.


In space (three dimensions)

In 3-dimensional space there are intersection points (common points) between curves and surfaces. In the following sections we consider '' transversal intersection'' only.


A line and a plane

The intersection of a line and a plane ''in
general position In algebraic geometry and computational geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the ''general case'' situation, as opposed to some more special or coincidental cases that are ...
'' in three dimensions is a point. Commonly a line in space is represented parametrically (x(t),y(t),z(t)) and a plane by an equation ax+by+cz=d. Inserting the parameter representation into the equation yields the linear equation :ax(t)+by(t)+cz(t)=d\ , for parameter t_0 of the intersection point (x(t_0),y(t_0),z(t_0)). If the linear equation has no solution, the line either lies on the plane or is parallel to it.


Three planes

If a line is defined by two intersecting planes \varepsilon_i: \ \vec n_i\cdot\vec x=d_i, \ i=1,2 and should be intersected by a third plane \varepsilon_3: \ \vec n_3\cdot\vec x=d_3 , the common intersection point of the three planes has to be evaluated. Three planes \varepsilon_i: \ \vec n_i\cdot\vec x=d_i, \ i=1,2,3 with linear independent normal vectors \vec n_1,\vec n_2, \vec n_3 have the intersection point : \vec p_0=\frac \ . For the proof one should establish \vec n_i\cdot\vec p_0=d_i, \ i=1,2,3 , using the rules of a
scalar triple product In geometry and algebra, the triple product is a product of three 3-dimensional vectors, usually Euclidean vectors. The name "triple product" is used for two different products, the scalar-valued scalar triple product and, less often, the vector- ...
. If the scalar triple product equals to 0, then planes either do not have the triple intersection or it is a line (or a plane, if all three planes are the same).


A curve and a surface

Analogously to the plane case the following cases lead to non-linear systems, which can be solved using a 1- or 3-dimensional Newton iteration.Erich Hartmann
''Geometry and Algorithms for COMPUTER AIDED DESIGN''
Lecture notes, Technische Universität Darmstadt, October 2003, p. 93
*parametric curve C: (x(t),y(t),z(t)) and :parametric surface S: (x(u,v),y(u,v),z(u,v))\ , *parametric curve C: (x(t),y(t),z(t)) and :implicit surface S: f(x,y,z)=0\ . Example: :parametric curve C: (t,t^2,t^3) and :implicit surface S: x^4+y^4+z^4-1=0 (s. picture). :The intersection points are: (−0.8587, 0.7374, −0.6332), (0.8587, 0.7374, 0.6332). A
line–sphere intersection In analytic geometry, a line and a sphere can intersect in three ways: # No intersection at all # Intersection in exactly one point # Intersection in two points. Methods for distinguishing these cases, and determining the coordinates for the p ...
is a simple special case. Like the case of a line and a plane, the intersection of a curve and a surface ''in
general position In algebraic geometry and computational geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the ''general case'' situation, as opposed to some more special or coincidental cases that are ...
'' consists of discrete points, but a curve may be partly or totally contained in a surface.


A line and a polyhedron


Two surfaces

Two transversally intersecting surfaces give an intersection curve. The most simple case the intersection line of two non-parallel planes.


See also

* Analytic geometry#Intersections *
Computational geometry Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...
*
Equation of a line In geometry, a line is an infinitely long object with no width, depth, or curvature. Thus, lines are one-dimensional objects, though they may exist in two, three, or higher dimension spaces. The word ''line'' may also refer to a line segment ...
*
Intersection (set theory) In set theory, the intersection of two sets A and B, denoted by A \cap B, is the set containing all elements of A that also belong to B or equivalently, all elements of B that also belong to A. Notation and terminology Intersection is writt ...
*
Intersection theory In mathematics, intersection theory is one of the main branches of algebraic geometry, where it gives information about the intersection of two subvarieties of a given variety. The theory for varieties is older, with roots in Bézout's theorem o ...


References


Further reading

* Nicholas M. Patrikalakis and Takashi Maekawa, ''Shape Interrogation for Computer Aided Design and Manufacturing'', Springer, 2002, {{ISBN, 3540424547, 9783540424543, pp. 408

Geometric intersection, *