# Finding ellipse-ellipse intersections in $\mathbb R^2$

The setting is as follows: we considers 2 disks embedded in $$\mathbb R^3,$$ and are interested in projecting one disk (either) onto the plane of the other other, and then compute their area of intersection within that chosen plane.

Suppose the plane of the disk ("2") into which we project is $$\Pi$$ described by a normal vector $$\mathbf n,$$ and $$O_\Pi$$ a projection operator, projecting onto an orthonormal basis within the 2D plane (spanned by the null-space of $$\mathbf n$$). Then if our disk "1" (to be projected onto $$\Pi$$) is centred at $$\mathbf r_1,$$ initially in a plane with normal $$\mathbf n_1,$$ then the half-axis vectors of the projected disk which is an ellipsoid in general ($$l$$ to denote large axis and $$s$$ the small one) can be expressed as:

\begin{align} \mathbf a_l =& r (\mathbf n_1 \times \mathbf n) \text{ and projected to } O_\Pi \mathbf a_l \in\mathbb R^2 \tag{1} \\ \mathbf a_s =& r \mathbf n_1 \times (\mathbf n_1 \times \mathbf n) \text{ and similarly } O_\Pi \mathbf a_s\in\mathbb R^2 \tag{2} \end{align}

where $$r$$ is the radius of the two disks. For simplicity, in the plane $$\Pi,$$ we assume a coordinate system where the original disk of the plane has its centre at origin and the projected disk (the ellipsoid) is centred at $$O_\Pi(\mathbf r_1-\mathbf r_2),$$ which is the difference vector of the disks' position vectors. To describe the obtained ellipsoid (projected disk), we can use the Kronecker product to compute its covariance matrix $$\text{cov}=(O_\Pi a_l \otimes O_\Pi a_l)+(O_\Pi a_s \otimes O_\Pi a_s)$$ (whose eigenvalues give the length of the axes and the eigenvectors the orientation), which together with the centre position provide a complete characterisation of the ellipsoid.

For an intuitive picture, here (scrolling down a bit) an example of a disk projected onto another plane, thus the resulting ellipsoid, are visualised. But unlike our problem, there's no other disk lying in the projected plane to consider an intersection with.

• Question is: generally, is there a way to calculate algebraically the intersection area of the disk with the projection (the ellipsoid)? In other words, is the problem of ellipsoid-ellipsoid intersection area in $$\mathbb R^2$$ solved or is it recommended to recur to numerical schemes? I am not aware of whether there exists algorithms that solve this efficiently.

David Eberly worked out the (formidable) details in these documents:

David Eberly, "The Area of Intersecting Ellipses." Geometric Tools. 2016. PDF1 download.

He says, "The formulas are in closed form, thus providing the exact area in terms of real-valued arithmetic." His calculations require solving quartics.

Algebraically - no. Your problem is reduced to computing the area of intersection of an ellipse with a disk. There can be different configurations, but one of them is when the centers coincide, and the ellipse has 4 points of intersection with the circle. Then this intersection is broken into two circular sectors and two elliptic sectors. The area of an elliptic sector is not an algebraic function (this was proved by Newton!). However there is a formula for this area in terms of transcendental functions:

https://math.stackexchange.com/questions/114371/deriving-the-area-of-a-sector-of-an-ellipse

Using this formula, you can derive a formula for your problem, but it is going to be complicated and not algebraic.

Newton's proof is so remarkable that I will reproduce it here: Let the rectilinear sides of the sector be $$a$$ and $$b$$ with common point $$O$$. Keep $$a$$ fixed and rotate $$b$$ about $$O$$. Then the area will be multi-valued function (infinitely valued!) of $$b$$: every time when $$b$$ makes a full turn, the area of the whole ellipse is added. But an algebraic function cannot be infinitely valued.

• Please forgive a stupid question, but doesn't that proof idea apply to the area of a circular sector? But the area of a circular sector is an algebraic function... of the central angle of the sector. Unless perhaps you mean to consider it as a function of something else? Or perhaps, to ignore multiple counting of areas, e.g., the sector from $0$ to $5\pi/2$ is the same as the sector from $0$ to $\pi/2$? – Zach Teitler Dec 2 '19 at 19:26
• Ah, suppose the ellipse has area $A$, fix a ray from the center, and let $f(\theta)$ be the area of the sector swept by angle $\theta$ from the initial ray (counting area multiply, or negatively if $\theta<0$). Let $g(\theta) = f(\theta)-A\theta/(2\pi)$. Then $g$ is periodic, hence not algebraic, so $f$ is also not algebraic; except if $g=0$, which is the case for a circle. - Just a minor change from what you wrote: the area function is not infinitely-valued, it’s the difference $g$ that is. – Zach Teitler Dec 2 '19 at 21:20
• @Zach Teiler: it is an algebraic function of the angle, but not an algebraic function of the points on the circle ("corners" of the sector). Newton's argument is of course applicable to a disk as well. – Alexandre Eremenko Dec 2 '19 at 23:29

This does not answer your question as to the area of overlap, but is perhaps of interest if you planned to use that area as proxy for proximity of the ellipses: in this paper, Perram & Werthiem describe a contact function that is respectively greater than, less than or equal to one depending on whether the ellipses are disjoint, overlap or are tangent. The function is a 1-dimensional convex maximisation, so can be performed very quickly and reliably.