intersection (geometry)

{{further|Plane (geometry)|Two-dimensional space}}

{{main|Line–line intersection}}

For the determination of the intersection point of two non-parallel lines

$a\_1x+b\_1y=c\_1,\; \backslash \; a\_2x+b\_2y=c\_2$

one gets, from Cramer's rule or by substituting out a variable, the coordinates of the intersection point $(x\_s,y\_s)$ :

:$x\_s=\backslash frac\{c\_1b\_2-c\_2b\_1\}\{a\_1b\_2-a\_2b\_1\}\; ,\; \backslash quad\; y\_s=\backslash frac\{a\_1c\_2-a\_2c\_1\}\{a\_1b\_2-a\_2b\_1\}.\; \backslash$

(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 ===

{{see also|Multiple line segment intersection|Line–line intersection#Given two points on each line segment}}

File:Is-linesegm.svg

For two non-parallel line segments $(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\backslash le\; s\_0,t\_0\; \backslash 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\; \backslash \; .$

It can be solved for s and t using Cramer's rule (see above). If the condition $0\backslash le\; s\_0,t\_0\; \backslash 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=\backslash tfrac\{3\}\{11\},\; t\_0=\backslash tfrac\{6\}\{11\}$. That means: the lines intersect at point $(\backslash tfrac\{17\}\{11\},\backslash tfrac\{14\}\{11\})$.

Remark: Considering lines, instead of segments, determined by pairs of points, each condition $0\backslash le\; s\_0,t\_0\; \backslash le\; 1$ can be dropped and the method yields the intersection point of the lines (see above).

{{further|Line–sphere intersection}}

File:Is-circle-line-s.svg

For the intersection of

• line $ax+by=c$ and circle $x^2+y^2=r^2$

one solves the line equation for {{mvar|x}} or {{mvar|y}} 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\_\{1/2\}=\; \backslash frac\{ac\backslash pm\; b\backslash sqrt\{r^2(a^2+b^2)-c^2\}\}\{a^2+b^2\}\; \backslash \; ,$

:$y\_\{1/2\}=\; \backslash frac\{bc\backslash mp\; a\backslash sqrt\{r^2(a^2+b^2)-c^2\}\}\{a^2+b^2\}\; \backslash \; ,$

if $r^2(a^2+b^2)-c^2\; >\; 0\; \backslash \; .$ If this condition holds with strict inequality, there are two intersection points; in this case the line is called a secant line 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.Erich Hartmann: [http://www.mathematik.tu-darmstadt.de/~ehartmann/cdgen0104.pdf Geometry and Algorithms for COMPUTER AIDED DESIGN]. Lecture notes, Technische Universität Darmstadt, October 2003, p. 17 The intersection of a line and a parabola or hyperbola may be treated analogously.

{{see also|Lens (geometry)}}

The determination of the intersection points of two circles

• $(x-x\_1)^2+(y-y\_1)^2=r\_1^2\; ,\backslash \; \backslash 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.

File:Is-circle-circle-2x.svg

Special case $\backslash ;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 $\backslash ;2x\_2x=r\_1^2-r\_2^2+x\_2^2\backslash ;$ and the points of intersection can be written as $(x\_0,\backslash pm\; y\_0)$ with

:$x\_0=\backslash frac\{r\_1^2-r\_2^2+x\_2^2\}\{2x\_2\},\backslash quad\; y\_0\; =\backslash sqrt\{r\_1^2-x\_0^2\}\backslash \; .$

In case of

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.

File:Is-circle-ellipse-s.svg

The problem of intersection of an ellipse/hyperbola/parabola with another conic section 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. 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.

File:Schnittp2d-transv-s.svg

File:Beruehr-schnitt-s.svg

Two curves in $\backslash 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 (see diagram):

: a) different tangent lines (transversal intersection, after transversality), or

: b) the tangent line in common and they are crossing each other (touching intersection, after tangency).

If both the curves have a point {{mvar|S}} and the tangent line there in common but do not cross each other, they are just touching at point {{mvar|S}}.

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:

File:Schnittp2d-pi-s.svg

File:Schnittp2d-ii-s.svg

• If both curves are explicitly given: $y=f\_1(x),\; \backslash \; y=f\_2(x)$, equating them yields the equation

:: $f\_1(x)=f\_2(x)\; \backslash \; .$

• If both curves are parametrically given: $C\_1:\; (x\_1(t),y\_1(t)),\; \backslash \; C\_2:\; (x\_2(s),y\_2(s)).$

: Equating them yields two equations in two variables:

:: $x\_1(t)=x\_2(s),\; \backslash \; y\_1(t)=y\_2(s)\; \backslash \; .$

• If one curve is parametrically and the other implicitly given: $C\_1:\; (x\_1(t),y\_1(t)),\; \backslash \; 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\; \backslash \; .$

• If both curves are implicitly given: $C\_1:\; f\_1(x,y)=0,\; \backslash \; C\_2:\; f\_2(x,y)=0.$

: Here, an intersection point is a solution of the system

::$f\_1(x,y)=0,\; \backslash \; f\_2(x,y)=0\; \backslash \; .$

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 {{mvar|t}} or {{mvar|x}} 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

.Erich Hartmann: [http://www.mathematik.tu-darmstadt.de/~ehartmann/cdgen0104.pdf Geometry and Algorithms for COMPUTER AIDED DESIGN]. Lecture notes, Technische Universität Darmstadt, October 2003, p. 33

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\_\{n+1\}:=t\_n-\backslash frac\{f(t\_n)\}\{f\text{'}(t\_n)\}$ 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

:::$\{x\_\{n+1\}\backslash choose\; y\_\{n+1\}\}=\{x\_\{n\}+\backslash delta\_x\backslash choose\; y\_n+\backslash delta\_y\}$ has to be performed, where $\{\backslash delta\_x\; \backslash choose\; \backslash delta\_y\}$ is the solution of the linear system

:::$\backslash begin\{pmatrix\}$

\frac{\partial f_1}{\partial x} & \frac{\partial f_1}{\partial y} \\

\frac{\partial f_2}{\partial x} & \frac{\partial f_2}{\partial y}

\end{pmatrix}{\delta_x \choose \delta_y}={-f_1\choose -f_2}

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

File:Is-polygpolyg-s.svg

If one wants to determine the intersection points of two polygons, 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.Erich Hartmann: [http://www.mathematik.tu-darmstadt.de/~ehartmann/cdg-skript-1998.pdf CDKG: Computerunterstützte Darstellende und Konstruktive Geometrie]. Lecture notes, TU Darmstadt, 1997, p. 79 (PDF; 3,4 MB)

{{more information|three-dimensional space}}

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

{{main|Line–plane intersection}}

File:Schnittp-ger-eb-s.svg

The intersection of a line and a plane in general position 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\backslash \; ,$

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.

If a line is defined by two intersecting planes $\backslash varepsilon\_i:\; \backslash \; \backslash vec\; n\_i\backslash cdot\backslash vec\; x=d\_i,\; \backslash \; i=1,2$ and should be intersected by a third plane $\backslash varepsilon\_3:\; \backslash \; \backslash vec\; n\_3\backslash cdot\backslash vec\; x=d\_3$, the common intersection point of the three planes has to be evaluated.

Three planes $\backslash varepsilon\_i:\; \backslash \; \backslash vec\; n\_i\backslash cdot\backslash vec\; x=d\_i,\; \backslash \; i=1,2,3$ with linear independent normal vectors $\backslash vec\; n\_1,\backslash vec\; n\_2,\; \backslash vec\; n\_3$ have the intersection point

:$\backslash vec\; p\_0=\backslash frac\{d\_1(\backslash vec\; n\_2\backslash times\; \backslash vec\; n\_3)\; +d\_2(\backslash vec\; n\_3\backslash times\; \backslash vec\; n\_1)\; +\; d\_3(\backslash vec\; n\_1\backslash times\; \backslash vec\; n\_2)\}\{\backslash vec\; n\_1\backslash cdot(\backslash vec\; n\_2\backslash times\; \backslash vec\; n\_3)\}\; \backslash \; .$

For the proof one should establish $\backslash vec\; n\_i\backslash cdot\backslash vec\; p\_0=d\_i,\; \backslash \; i=1,2,3\; ,$ using the rules of a scalar triple product. 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).

File:Is-pcurve-isurface-s.svg

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: [http://www.mathematik.tu-darmstadt.de/~ehartmann/cdgen0104.pdf 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))\backslash \; ,$

• parametric curve $C:\; (x(t),y(t),z(t))$ and

:implicit surface $S:\; f(x,y,z)=0\backslash \; .$

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 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 consists of discrete points, but a curve may be partly or totally contained in a surface.

{{main|Intersection of a polyhedron with a line}}

{{main|Intersection curve}}

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

{{also|Spherical circle}}

When the intersection of a sphere and a plane is not empty or a single point, it is a circle. This can be seen as follows:

Let S be a sphere with center O, P a plane which intersects S. Draw {{overline|OE}} perpendicular to P and meeting P at E. Let A and B be any two different points in the intersection. Then AOE and BOE are right triangles with a common side, OE, and hypotenuses AO and BO equal. Therefore, the remaining sides AE and BE are equal. This proves that all points in the intersection are the same distance from the point E in the plane P, in other words all points in the intersection lie on a circle C with center E.Proof follows Hobbs, Prop. 304 This proves that the intersection of P and S is contained in C. Note that OE is the axis of the circle.

Now consider a point D of the circle C. Since C lies in P, so does D. On the other hand, the triangles AOE and DOE are right triangles with a common side, OE, and legs EA and ED equal. Therefore, the hypotenuses AO and DO are equal, and equal to the radius of S, so that D lies in S. This proves that C is contained in the intersection of P and S.

As a corollary, on a sphere there is exactly one circle that can be drawn through three given points.Hobbs, Prop. 308

The proof can be extended to show that the points on a circle are all a common angular distance from one of its poles.Hobbs, Prop. 310

Compare also conic sections, which can produce ovals.

To show that a non-trivial intersection of two spheres is a circle, assume (without loss of generality) that one sphere (with radius $R$) is centered at the origin. Points on this sphere satisfy

:$x^2\; +\; y^2\; +\; z^2\; =\; R^2.$

Also without loss of generality, assume that the second sphere, with radius $r$, is centered at a point on the positive x-axis, at distance $a$ from the origin. Its points satisfy

:$(x-a)^2\; +\; y^2\; +\; z^2\; =\; r^2.$

The intersection of the spheres is the set of points satisfying both equations. Subtracting the equations gives

:$\backslash begin\{align\}$

(x-a)^2 - x^2 & = r^2 - R^2 \\

a^2 - 2ax & = r^2 - R^2 \\

x & = \frac{a^2 + R^2 - r^2}{2a}.

\end{align}

In the singular case $a\; =\; 0$, the spheres are concentric. There are two possibilities: if $R\; =\; r$, the spheres coincide, and the intersection is the entire sphere; if $R\; \backslash not=\; r$, the spheres are disjoint and the intersection is empty.

When a is nonzero, the intersection lies in a vertical plane with this x-coordinate, which may intersect both of the spheres, be tangent to both spheres, or external to both spheres.

The result follows from the previous proof for sphere-plane intersections.

• Line-plane intersection
• Line–sphere intersection
• Line-cylinder intersection
• Analytic geometry#Intersections
• Computational geometry
• Equation of a line
• Intersection (set theory)
• Intersection theory

{{reflist}}

• {{cite book |title=Solid Geometry|url=https://archive.org/details/solidgeometry00hobbgoog|first=C.A.|last=Hobbs|publisher=G.H. Kent|year=1921|pages=[https://archive.org/details/solidgeometry00hobbgoog/page/n151 397] ff}}

• {{cite web |url= https://www.realtimerendering.com/intersections.html |title=Intersections (Ray Tracing Resources Page) |last= Haines |first= Eric |date= June 6, 2021 |website=Real-Time Rendering |access-date=December 14, 2023 |quote=a grid of intersection routines for various popular objects, pointing to resources in books and on the web.}}
• Nicholas M. Patrikalakis and Takashi Maekawa, Shape Interrogation for Computer Aided Design and Manufacturing, Springer, 2002, {{ISBN|3540424547}}, 9783540424543, pp. 408. [https://books.google.com/books?id=qoxBeti5ySoC&q=intersection]
• {{cite book |title=Solid Geometry

|url=https://archive.org/details/solidgeometry01comsgoog

|first1=M.|last1=Sykes|first2=C.E.|last2=Comstock|publisher=Rand McNally

|year=1922|pages=[https://archive.org/details/solidgeometry01comsgoog/page/n93 81] ff}}

*