Calculating ellipse overlap areas

Abstract

We present an approach for finding the overlap area between two ellipses that does not rely on proxy curves. The Gauss-Green formula is used to determine a segment area between two points on an ellipse. Overlap between two ellipses is calculated by combining the areas of appropriate segments and polygons in each ellipse. For four of the ten possible orientations of two ellipses, the method requires numerical determination of transverse intersection points. Approximate intersection points can be determined by solving the two implicit ellipse equations simultaneously. Alternative approaches for finding transverse intersection points are available using tools from algebraic geometry, e.g., based on solving an Eigen-problem that is related to companion matrices of the two implicit ellipse curves. Implementations in C of several algorithm options are analyzed for accuracy, precision and robustness with a range of input ellipses.

1 Introduction

Ellipses are useful in many applied scenarios, and in widely disparate fields. In our research, we have encountered a common need for efficiently calculating the overlap area between two ellipses. In one case, the design for a solar calibrator onboard an orbiting satellite required an efficient routine for finding ellipse overlap areas. In a more down-to-earth setting, calculating ellipse overlap areas is useful for modeling pedestrian dynamics. The approach described in [4] surrounds each pedestrian by an elliptical footprint area that the model uses to anticipate obstacles and other pedestrians in or near the intended path. A force-based model produces a repulsive force between ellipses, causing the pedestrians to slow down or change course when the exclusion force becomes large. To calibrate the strength of the repulsive force a quantity describing the amount of overlapping between two ellipses was defined, which requires calculating the overlap area between many different ellipses in general orientations and the overlap algorithm must be efficient, so as not to bog down the simulation.

Overlap area between two ellipses can be determined with high accuracy and precision by Monte Carlo integration (e.g., [17]), but the method is numerically intensive. More efficient approaches for determining ellipse areas based on approximating the ellipse curves with polygons [9, 11], adaptive polygons [10], polytopes [1], and polyarcs [8] have also been described. For these methods, accuracy of the overlap area value is governed by the number of sample points used to represent the original curve with a polygon or other proxy curve. Other than Monte Carlo integration, we have yet to find any ellipse overlap area algorithms in the peer-reviewed literature that do not rely on use of proxy curves. An un-published algorithm that does not use proxy curves is available online [5].

• In this paper, we provide an algorithm that determines the overlap area between two general ellipses without using proxy curves. We first find the area of an ellipse segment, which is the area between a secant line and the ellipse boundary. The segment algorithm then forms the basis of an application for calculating the overlap area between two general ellipses, using points of intersection between the two ellipses to identify appropriate segment areas. Intersection points can be found by solving the two implicit ellipse equations simultaneously. Alternative methods for determining intersection points can be adopted from Algebraic Geometry, such as solving an Eigen-problem that is formed from companion matrices of the two implicit ellipse curves. Accuracy of the area estimate is determined by accuracy and precision of calculated intersection points. The algorithm is implemented in C and tested with a range of input ellipses.

2 Ellipse equations and areas

2.1 Ellipse parametric and implicit polynomial equations

Consider an ellipse that is centered at the origin, with its axes aligned to the coordinate axes. If the semi-axis length along the $x$-axis is $A$, and the semi-axis length along the $y$-axis is $B$, then the ellipse is defined by a locus of points that satisfy the implicit polynomial Eq. (1a), or parametrically as in Eq. (1b):

$$\begin{aligned} \frac{x^{2}}{A^{2}}+\frac{y^{2}}{B^{2}}&= 1\end{aligned}$$

(1a)

$$\begin{aligned}&\left. {\begin{array}{l} x(t)=A\cdot cos(t)\\ y(t)=B\cdot sin(t)\\ \end{array}}\right\} \quad 0\le t\le 2\pi \end{aligned}$$

(1b)

More generally, a rotated ellipse can be defined parametrically using Eq. (1b) with a general 2-D rotation through counterclockwise angle $\varphi$:

$$\begin{aligned}&\!\!\!\!\! \left. \left[ {\begin{array}{l} x(t)\\ y(t)\\ \end{array}}\right] =\left[ {\begin{array}{ll} cos(\varphi )&{} -sin(\varphi )\\ sin(\varphi )&{} cos(\varphi )\\ \end{array}}\right] \cdot \left[ {\begin{array}{l} A\cdot cos(t)\\ B\cdot sin(t)\\ \end{array}}\right] \right\} \quad 0\le t\le 2\pi \nonumber \\&\left. {\begin{array}{l} \!\!\!\!\!x(t)=A\cdot cos(\varphi )\cdot cos(t)-B\cdot sin(\varphi )\cdot sin(t)\\ \!\!\!\!\!y(t)=A\cdot sin(\varphi )\cdot cos(t)+B\cdot cos(\varphi )\cdot sin(t)\\ \end{array}}\right\} \quad 0\le t\le 2\pi \end{aligned}$$

(2)

In the most general case, the rotated ellipse can also be translated away from the origin by an amount $(h, k)$, and the parametric form of a rotated-then-translated ellipse is given by:

$$\begin{aligned} \left. {\begin{array}{l} \!\!\!x(t)=A\cdot cos(\varphi )\cdot cos(t)-B\cdot sin(\varphi )\cdot sin(t)+h\\ \!\!\!y(t)=A\cdot sin(\varphi )\cdot cos(t)+B\cdot cos(\varphi )\cdot sin(t)+k\\ \end{array}}\right\} \quad 0\le t\le 2\pi \nonumber \\ \end{aligned}$$

(3)

A rotated-then-translated ellipse can be defined by the set of parameters $\{A, B, h, k, \varphi \}$, with the understanding that the rotation through $\varphi$ is performed before the translation through $(h, k)$.

Parametric formulation of ellipses is commonly used in models, since the parameters have intuitive geometric analogs. However, finding intersection points between two ellipses is generally accomplished by implicitizing the parametric form. For a general ellipse that may be rotated and translated, the implicit polynomial form is written in the conventional way as:

$$\begin{aligned} AA\cdot x^{2}&+ BB\cdot x\cdot y+CC\cdot y^{2}+DD\cdot x\nonumber \\&+ EE\cdot y+FF=0 \end{aligned}$$

(4a)

Equation (4a) can also be written as the matrix equation $\hbox {X}^{\mathrm{T}} \cdot \hbox {A}\cdot \hbox {X} = 0$, where $\hbox {X}^{\mathrm{T}} = [x, y, 1]$ and A is the symmetric matrix of coefficients $[(a_{i,j})]$:

$$\begin{aligned}&\!\!\! a_{1,1} \cdot x^{2}+2\cdot a_{1,2} \cdot x\cdot y+a_{2,2} \cdot y^{2}\nonumber \\&\quad +2\cdot a_{1,3} \cdot x+2\cdot a_{2,3} \cdot y+a_{3,3} =0\end{aligned}$$

(4b)

$$\begin{aligned}&\!\!\! \left[ {\begin{array}{lll} x&{} y&{} 1 \\ \end{array}}\right] \cdot \left[ {\begin{array}{lll} a_{1,1}&{}a_{1,2}&{}a_{1,3}\\ a_{1,2}&{}a_{2,2}&{}a_{2,3}\\ a_{1,3}&{}a_{2,3}&{}a_{3,3}\\ \end{array}}\right] \cdot \left[ {\begin{array}{l} x \\ y \\ 1 \\ \end{array}}\right] =0 \end{aligned}$$

(4c)

Equivalence of Eqs. (4b) and (4c) is easily verified by multiplying the matrices in Eq. (4c). The matrix form will be convenient for several operations in the overlap area algorithm.

Implicitization from parametric form of Eq. (3) to implicit form of Eq. (4a) is commonly required in applications, and in particular for determining intersection points. Parametric ellipse parameters can be converted algebraically to implicit polynomial coefficients. Suppose the original ellipse is defined by the set of parameters $\{A, B, h, k, \varphi \}$. Any point $(x, y)$ on the original ellipse can be translated by $(-h, -k)$, and then rotated through an angle $-\varphi$:

$$\begin{aligned} \left[ {\begin{array}{l} x^{\prime }\\ y^{\prime }\\ \end{array}}\right]&= \left[ {\begin{array}{ll} cos(-\varphi )&{}\quad -sin(-\varphi )\\ sin(-\varphi )&{}\quad cos(-\varphi ) \\ \end{array}}\right] \cdot \left\{ \left[ {\begin{array}{l} x\\ y\\ \end{array}}\right] +\left[ {\begin{array}{l} -h\\ -k\\ \end{array}}\right] \right\} \\&= \left[ {\begin{array}{l} cos(\varphi )\cdot (x-h)+sin(\varphi )\cdot (y-k)\\ -sin(\varphi )\cdot (x-h)+cos(\varphi )\cdot (y-k)\\ \end{array}}\right] \end{aligned}$$

The locus of points $(x^\prime , y^\prime )$ all satisfy the implicit polynomial form of Eq. (1a), with parameters $A$ and $B$:

$$\begin{aligned}&\frac{\left[ cos(\varphi )\cdot (x-h)+sin(\varphi )\cdot (y-k)\right] ^{2}}{A^{2}}\\&\quad +\frac{\left[ -sin(\varphi )\cdot (x-h) +cos(\varphi )\cdot (y-k)\right] ^{2}}{B^{2}}=1 \end{aligned}$$

Expanding the squares and collecting terms in $x$ and $y$ produces conversions from the set of parameters $\{A, B, h, k, \varphi \}$ to implicit polynomial coefficients by Eqs. (5a)–(5f):

$$\begin{aligned} AA&= a_{1,1} =\frac{\cos ^{2}(\varphi )}{A^{2}}+\frac{\sin ^{2}(\varphi )}{B^{2}}\end{aligned}$$

(5a)

$$\begin{aligned} BB&= 2\cdot a_{1\cdot 2} = \frac{2\cdot \sin (\varphi )\cdot \cos (\varphi )}{A^{2}}- \frac{2\cdot \sin (\varphi )\cdot \cos (\varphi )}{B^{2}}\end{aligned}$$

(5b)

$$\begin{aligned} CC&= a_{2,2} =\frac{\sin ^{2}(\varphi )}{A^{2}}+\frac{\cos ^{2}(\varphi )}{B^{2}}\end{aligned}$$

(5c)

$$\begin{aligned} DD&= 2\cdot a_{1,3} =\frac{-2\cdot \cos (\varphi )\cdot \left[ h\cdot \cos (\varphi )+k\cdot \sin (\varphi )\right] }{A^{2}}\nonumber \\&+\frac{2\cdot \sin (\varphi )\cdot \left[ k\cdot \cos (\varphi )-h\cdot \sin (\varphi )\right] }{B^{2}}\end{aligned}$$

(5d)

$$\begin{aligned} EE&= 2\cdot a_{2,3} =\frac{-2\cdot \sin (\varphi )\cdot \left[ h\cdot \cos (\varphi )+k\cdot \sin (\varphi )\right] }{A^{2}}\nonumber \\&+\frac{2\cdot \cos (\varphi )\cdot \left[ h\cdot \sin (\varphi )-k\cdot \cos (\varphi )\right] }{B^{2}}\end{aligned}$$

(5e)

$$\begin{aligned} FF&= a_{3,3} =\frac{\left[ h\cdot \cos (\varphi )+k\cdot \sin (\varphi )\right] ^{2}}{A^{2}}\nonumber \\&+\frac{\left[ h\cdot \sin (\varphi )-k\cdot \cos (\varphi )\right] ^{2}}{B^{2}}-1 \end{aligned}$$

(5f)

Note that for an ellipse which is centered at the origin, as in Eq. (2), we have $(h, k) = (0, 0)$, and some implicit polynomial coefficients are simplified, as $DD = 0, EE = 0$, and $FF = -1$. Also note that for an ellipse which is both centered and axis aligned, we have $(h, k) = (0, 0)$ and $\varphi =0$, resulting in $AA=(1/A)^{2}, BB = 0, CC = (1/B)^{2}, DD=0, EE=0$, and $FF=-1$, and Eq. (4a) simplifies exactly to Eq. (1), as expected.

2.2 Ellipse area

The area of a centered and axis-aligned ellipse can be found using the parametric form of Eq. (1b) with the Gauss-Green formula:

$$\begin{aligned} \hbox {Area}&= \frac{1}{2}\int \limits _{t_1}^{t_2}\left[ x(t)\cdot y^{{\prime }}(t)-y(t)\cdot x^{{\prime }}(t)\right] dt\end{aligned}$$

(6)

$$\begin{aligned}&= \frac{1}{2}\int \limits _0^{2\pi } \left[ A\cdot cos(t)\cdot B\cdot cos(t)\right. \nonumber \\&\quad \left. -B\cdot sin(t)\cdot (-A)\cdot sin(t)\right] dt\nonumber \\&= \frac{1}{2}\int \limits _0^{2\pi } A\cdot B\cdot \left[ cos^{2}(t)+sin^{2}(t)\right] dt\nonumber \\&= \frac{A\cdot B}{2}\int \limits _0^{2\pi } dt\nonumber \\&= \pi \cdot A\cdot B \end{aligned}$$

(7)

Rotation of an ellipse is an area-preserving transformation, and it is easily verified that the Gauss-Green integrand $x(t)\cdot y^\prime (t)- y(t)\cdot x^\prime (t)$ for a rotated, centered ellipse simplifies to $A\cdot B$ when using the parametric form in Eq. (2). It is also clear that translation by $(h, k)$ is an area-preserving transformation.

2.3 Ellipse sector area

The ellipse sector between two points $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$ on an ellipse is the area that is swept out by a vector that begins at the ellipse center and ends on the ellipse curve, starting the sweep at the first point $(x_{1}, y_{1})$, as the vector end travels along the ellipse in a counter-clockwise direction from the point $(x_{1}, y_{1})$ to the point $(x_{2}, y_{2})$. An example is shown in Fig. 1 for a centered, rotated ellipse.

Fig. 1

The area of a sector between two points on an ellipse that is centered at the origin is the area swept out by a vector from the origin to the first point $(x_{1},y_{1})$ as the vector tip travels along the ellipse in a counter-clockwise direction to the second point $(x_{2}, y_{2})$

The Gauss-Green formula (Eq. (6)) can be used to determine the area of a centered ellipse sector by:

$$\begin{aligned} \hbox {Sector Area}=\frac{A\cdot B}{2}\int \limits _{\theta _1}^{\theta _2} dt=\frac{\left( \theta _2 -\theta _1\right) \cdot A\cdot B}{2} \end{aligned}$$

(8)

The parametric angle $\theta$ corresponding to a point $(x, y)$ on the ellipse is formed between the ellipse axis branch that corresponds to the positive $x$-axis when $\varphi = 0$, with positive $\theta$ in the counter-clockwise direction. Using the principal-valued inverse trigonometric functions that return angles in the in the range $0 \le \theta \le \pi$ for $\theta = \hbox {arccos}\;(z)$, and in the range $-\pi /2 \le \theta \le \pi /2$ for $\theta = \hbox {arcsin}\;(z)$, ellipse parametric angles can be found with the relations in Table 1.

Table 1 Relations for finding the parametric angle corresponding to a given point $(x, y)$ on a centered, rotated ellipse defined with parameters $\{A, B, 0, 0, \varphi \}$

For calculating a sector area, the Gauss-Green formula is sensitive to the direction of integration. For the larger goal of determining ellipse overlap areas, we follow the convention that the sector area is calculated from the first point $(x_{1}, y_{1})$ to the second point $(x_{2}, y_{2})$ in a counter-clockwise direction. For example, if the points $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$ of Fig. 1 were to have their labels switched, then the ellipse sector defined by the new points will have an area that is complementary to that of the sector in Fig. 1, as shown in Fig. 2.

Fig. 2

The ellipse sector area is calculated from the first point $(x_{1}, y_{1})$ to the second point $(x_{2}, y_{2})$ in a counter-clockwise direction

The definitions in Table 1 will always produce an angle in the range $0 \le \theta < 2\pi$ for any point on the ellipse; as such, with the point orientations shown in Fig. 2, the corresponding angles will be ordered as $\theta _{1} > \theta _{2}$. The first angle can be transformed by subtracting $2\pi$ to restore the condition that $\theta _{1}< \theta _{2}$, and the sector area formula of Eq. (8) can then be used, with the integration angle from $(\theta _{1}- 2\pi )$ through $\theta _{2}$.

2.4 Ellipse segment area

For the overall goal of determining overlap areas between two ellipses, a useful measure is the area of an ellipse segment. A secant line drawn between two points on an ellipse partitions the ellipse area into two fractions, as shown in Figs. 1 and 2. An ellipse segment is the area confined by the secant line and the portion of the ellipse from the first point $(x_{1}, y_{1})$ to the second point $(x_{2}, y_{2})$ traversed in a counter-clockwise direction. The segment’s complement is the second of the two areas demarcated by the secant line. For the ellipse shown in Fig. 1, the segment area defined by the secant line through the points $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$ is the area of the sector minus the area of a triangle defined by the two points and the ellipse center (at the origin). The coordinates for the triangle’s vertices are known, i.e., as $(x_{1}, y_{1}), (x_{2}, y_{2})$ and the origin (0, 0), and the triangle area can be found by:

$$\begin{aligned} \hbox {Triangle Area}=\frac{1}{2}\cdot \left| x_1 \cdot y_2 -x_2 \cdot y_1\right| \end{aligned}$$

(9)

For the case depicted in Fig. 1, subtracting the triangle area (Eq. (9)) from the area of the ellipse sector (Eq. (8)) gives the area between the secant line and the ellipse, i.e., the area of the ellipse segment counter-clockwise from $(x_{1}, y_{1})$ to $(x_{2}, y_{2})$.

For the ellipse of Fig. 2, the area of the segment shown is the sector area plus the area of the triangle. The key difference between the cases in Figs. 1 and 2 that requires the area of the triangle to be either subtracted from, or added to, the sector area is the size of the integration angle. If the integration angle is less than $\uppi$, then the triangle area must be subtracted from the sector area to give the segment area. If the integration angle is greater than $\uppi$, the triangle area must be added to the sector area.

$$\begin{aligned} \hbox {Segment Area}=\frac{\left( \theta _2 -\theta _1\right) \cdot A\cdot B}{2}\pm \frac{1}{2}\cdot \left| x_1 \cdot y_2 -x_2 \cdot y_1\right| \nonumber \\ \end{aligned}$$

(10)

An algorithm for determining the area of an ellipse segment for a general ellipse is achieved through a generalization of the cases illustrated in Figs. 1, 2 and Eq. (10). Points are passed to the algorithm as $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$, both of which must be on the ellipse. The ELLIPSE_SEGMENT algorithm is outlined below:

• 1. $(x_1, y_1), (x_2, y_2)\; \hbox {on ellipse}\; \left\{ A,B,h,k,\varphi \right\}$ Inputs to the algorithm

• 2. $\left[ {\begin{array}{l} x_i^{\prime }\\ y_i^{\prime }\\ \end{array}}\right] =\left[ {\begin{array}{l} cos(\varphi )\cdot (x_i-h)+sin(\varphi )\cdot (y_i -k)\\ -sin(\varphi )\cdot (x_i -h)+cos(\varphi )\cdot (y_i -k)\\ \end{array}}\right] , i=1,2$

• 3. $\begin{array}{l} \theta _1 =\left\{ \begin{array}{l@{\quad }l} \arccos ({x_1^{\prime } /A}), &{} y_1^{\prime } \ge 0 \\ 2\pi -\arccos \left( x_1^{\prime }/A\right) , &{} y_1^{\prime } <0\\ \end{array}\right. \theta _2 =\left\{ {\begin{array}{l@{\quad }l} \arccos (x_2^{\prime }/A), &{} y_2^{\prime } \ge 0\\ 2\pi -\arccos (x_2^{\prime }/A), &{} y_2^{\prime } <0\\ \end{array}}\right. \\ \end{array}$

• 4. $\hat{\theta }_1 =\left\{ {\begin{array}{ll} \theta _1, &{}\theta _1 <\theta _2 \\ \theta _1-2\pi , &{}\theta _1 >\theta _2 \\ \end{array}}\right.$

• 5. $\hbox {Area}=\frac{\left( {\theta _2 -\hat{\theta }_1}\right) \cdot A\cdot B}{2}+\frac{sign\left( {\theta _2 -\hat{\theta }_1 -\pi }\right) }{2}\cdot \left| x_1 \cdot y_2 -x_2 \cdot y_1\right|$

where:

• the ellipse is defined by the set of parameters $\{A, B, h, k, \varphi \}$, under the convention that rotation through $\varphi$ is performed before translation by $(h, k)$

• $(x_{1}, y_{1})$ is the first given point, which must be on the ellipse

• $(x_{2}, y_{2})$ is the second given point, which must be on the ellipse

• $\theta _{1}$ and $\theta _{2}$ are the parametric angles corresponding to the points $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$

• Area = segment area proceeding from $(x_{1}, y_{1})$ counterclockwise to $(x_{2}, y_{2})$

3 Ellipse-ellipse overlap area

We seek a method to determine the overlap area between two general ellipses that are defined parametrically as $(A_{1}, B_{1}, h_{1}, k_{1}, \varphi _{1})$ and $(A_{2}, B_{2}, h_{2}, k_{2}, \varphi _{2})$. The ellipses are first characterized as belonging to one of the ten possible relative positions of two ellipses. Six of the 10 relative positions do not involve transverse intersection points, and overlap area can be computed directly. For the four remaining relative positions, overlap area is calculated by combining the areas of appropriate segments and polygons in each ellipse based on the location of intersection points, which are found numerically.

3.1 Relative position of two ellipses

An algorithm for ellipse overlap area benefits from first determining relative ellipse positions. A robust approach for characterizing the relative positions of two ellipses without knowledge of intersection points is described by [7]. For two ellipses with coefficient matrices $\hbox {A} = [(a_{i,j})]$ and $\hbox {B} = [(b_{i,j})]$ as annotated in Eq. (4b), the characteristic polynomial of the pencil $\lambda \hbox {A}+\hbox {B}$ is defined as:

$$\begin{aligned} f(\lambda )=\det \left( \lambda \cdot \hbox {A}+\hbox {B}\right) =\lambda ^{3}+a\cdot \lambda ^{2}+b\cdot \lambda +c \end{aligned}$$

(11)

To summarize results from [7], it is not necessary to determine roots of the characteristic polynomial. Cases shown in Fig. 3 can be discerned by evaluating inequalities of algebraic combinations of the characteristic polynomial coefficients.

Fig. 3

Classification of the relative positions of two ellipses from [7]. A tenth possible configuration is represented by coincident ellipses, i.e., the two ellipses are the same. Overlap area for cases 3, 4, 6, 7, 8 and 10 can be calculated directly from Eq. (7). For the remaining four cases, overlap area is determined by combining the areas of appropriate segments and polygons in each ellipse, based on the position of transverse intersection points

In the context of calculating ellipse area overlap, six of the 10 possible relative positions of two ellipses can be dispensed before attempting to determine points of intersection. Determining relative position reduces the overall calculations required by an overlap area routine that is called many times, as in a simulation. The approach may also avoid sending some ill-conditioned cases to the intersection routine. On the other hand, some ill-conditioned cases may be mis-classified by the relative position algorithm, leading to erroneous overlap area results; difficult cases are discussed in Sect. 3.6.

An algorithm adapted from [7] for determining the relative position of two general ellipses defined implicitly as $(AA_{1}, BB_{1}, CC_{1}, DD_{1}, EE_{1}, FF_{1})$ and $(AA_{2}, BB_{2}, CC_{2}, DD_{2}, EE_{2}, FF_{2})$ called ELLIPSE_CASE is outlined below.

• 1. $\left\{ AA_1, BB_1, CC_1, DD_1, EE_1, FF_1\right\} , \left\{ AA_2, BB_2, CC_2,\right. \left. DD_2, EE_2, FF_2\right\}$ Inputs to the algorithm

• 2. Calculate coefficients of det $(\lambda \cdot [\hbox {A}]+[\hbox {B}])=\lambda ^{3}+a\cdot \lambda ^{2}+b\cdot \lambda +c$

  $$\begin{aligned}&d=AA_1 \cdot \left( CC_1 \cdot FF_1 -EE_1^2\right) \\&\quad -\left( CC_1 \cdot DD_1^2 -2\cdot BB_1 \cdot DD_1 \cdot EE_1 +FF_1 \cdot BB_1^2\right) \\&a=\frac{1}{d}\cdot \left[ AA_1 \cdot \left( CC_1 \cdot FF_2 -2\cdot EE_1 \cdot EE_2 +FF_1 \cdot CC_2\right) \right. \\&\quad +\,2\cdot BB_1 \cdot \left( EE_1 \cdot DD_2 -FF_1 \cdot BB_2 +DD_1 \cdot EE_2\right) \\&\quad +\,2\cdot DD_1 \cdot \left( EE_1 \cdot BB_2 -CC_1 \cdot DD_2\right) \\&\quad \left. -\,\left( BB_1^2 \cdot FF_2 +DD_1^2 \cdot CC_2 +EE_1^2 \cdot b_{1,1}\right) \right. \\&\quad \left. +\,\left( CC_1 \cdot FF_1 \cdot AA_2\right) \right] \\&b=\frac{1}{d}\cdot \left[ AA_1 \cdot \left( CC_2 \cdot FF_2 -EE_2^2\right) \right. \\&\quad +\,2\cdot BB_1 \cdot \left( EE_2 \cdot DD_2 -FF_2 \cdot BB_2\right) \\&\quad +\,2\cdot DD_1 \cdot \left( EE_2 \cdot BB_2 -CC_2 \cdot DD_2\right) \\&\quad +\,CC_1 \cdot \left( AA_2 \cdot FF_2 -DD_2^2\right) \\&\quad +\,2\cdot EE_1 \cdot \left( BB_2 \cdot DD_2 -AA_2 \cdot EE_2\right) \\&\quad \left. +\,FF_1 \cdot \left( AA_2 \cdot CC_2 -BB_2^2\right) \right] \\&c=\frac{1}{d}\cdot \left[ AA_2 \cdot \left( CC_2 \cdot FF_2 -EE_2^2\right) \right. \\&\quad \left. -\,\left( BB_2^2 \cdot FF_2 -2\cdot BB_2 \cdot DD_2 \cdot EE_2 +DD_2^2 \cdot CC_2\right) \right] \end{aligned}$$

• 3. Interpret Coefficients of $\lambda ^{3}+a\cdot \lambda ^{2}+b\cdot \lambda +c$

  $$\begin{aligned}&s_4 =-27\cdot c^{3}+18\cdot c\cdot a\cdot b+a^{2}\cdot b^{2}\\&\qquad -4\cdot a^{3}\cdot c-4\cdot b^{3} \end{aligned}$$

3.2 Determining transverse intersection points I: a direct approach

A direct approach for finding intersection points, discussed in [5], seeks to solve the two implicit ellipse equations simultaneously. The two polynomials, in the form of Eq. (4a), can be re-written as quadratic polynomials in $x$ whose coefficients are functions of $y$:

$$\begin{aligned}&\!\!\!\! (AA_1)\cdot x^{2}+\left( BB_1 \cdot y+DD_1\right) \cdot x+\left( CC_1 \cdot y^{2}\right. \nonumber \\&\quad \left. +EE_1 \cdot y+FF_1\right) =0\end{aligned}$$

(12a)

$$\begin{aligned}&\!\!\!\! (AA_2)\cdot x^{2}+\left( BB_2 \cdot y+DD_2\right) \cdot x+\left( CC_2 \cdot y^{2}\right. \nonumber \\&\quad \left. +EE_2 \cdot y+FF_2\right) =0 \end{aligned}$$

(12b)

Any points of intersection $(x, y)$ for the two ellipses will satisfy Eqs. (12a) and (12b) simultaneously. For convenience, the coefficients can be substituted:

$$\begin{aligned}&\!\!\!\!u_2 \cdot x^{2}+u_1 \cdot x+u_0 =0\nonumber \\&\quad u_2 = (AA_1), u_1 =\left( BB_1 \cdot y+DD_1\right) ,\nonumber \\&\quad u_0=\left( CC_1 \cdot y^{2}+EE_1 \cdot y+FF_1\right) \end{aligned}$$

(13a)

$$\begin{aligned}&\!\!\!\!v_2 \cdot x^{2}+v_1 \cdot x+v_0 =0\nonumber \\&\quad v_2 = (AA_2), v_1 =\left( BB_2 \cdot y+DD_2\right) , \nonumber \\&\quad v_0=\left( CC_2 \cdot y^{2}+EE_2 \cdot y+FF_2\right) \end{aligned}$$

(13b)

Using a standard approach (developed in the nineteenth century), the two polynomials of Eq. (13) have a common root whenever their Bézout determinant is zero:

$$\begin{aligned}&\!\!\!\!\left( u_1 \cdot v_0 -u_0 \cdot v_1\right) \cdot \left( u_2 \cdot v_1 -u_1 \cdot v_2\right) \nonumber \\&-\left( u_2 \cdot v_0 -u_0 \cdot v_2\right) ^{2}=0 \end{aligned}$$

(14)

Using the definitions from Eq. (13) and substituting into Eq. (14) produces a quartic polynomial in $y$ with the following coefficients:

$$\begin{aligned} cy[4]\cdot y^{4}&+ cy [3]\cdot y^{3}+cy [2]\cdot y^{2}\nonumber \\&+ cy [1]\cdot y^{1}+cy [0]=0 \end{aligned}$$

(15)

where:

$$\begin{aligned} cy[4]&= \left( BB_1 \cdot CC_2 -CC_1 \cdot BB_2\right) \cdot \left( AA_1 \cdot BB_2 -BB_1 \cdot AA_2\right) \\&\quad -\left( AA_1 \cdot CC_2 -CC_1 \cdot AA_2\right) ^{2}\\ cy[3]&= 2\cdot \left( EE_1 \cdot AA_2 -AA_1 \cdot EE_2\right) \cdot \left( AA_1 \cdot CC_2 -CC_1 \cdot AA_2\right) \\&\quad +\left( DD_1 \cdot CC_2 +BB_1 \cdot EE_2 -EE_1 \cdot BB_2 -CC_1 \cdot DD_2\right) \\&\quad \cdot \left( AA_1 \cdot BB_2 -BB_1 \cdot AA_2\right) +\left( BB_1 \cdot CC_2 -CC_1 \cdot BB_2\right) \\&\quad \cdot \left( AA_1 \cdot DD_2 -DD_1 \cdot AA_2\right) \\ cy[2]&= 2\cdot \left( FF_1 \cdot AA_2 -AA_1 \cdot FF_2\right) \cdot \left( AA_1 \cdot CC_2 -CC_1 \cdot AA_2\right) \\&\quad +\left( DD_1 \cdot EE_2 +BB_1 \cdot FF_2 -FF_1 \cdot BB_2\right. \\&\quad \left. -EE_1 \cdot DD_2\right) \cdot \left( AA_1 \cdot BB_2 -BB_1 \cdot AA_2\right) \\&\quad +\left( DD_1 \cdot CC_2 +BB_1 \cdot EE_2 -EE_1 \cdot BB_2 -CC_1 \cdot DD_2\right) \\&\quad \cdot \left( AA_1 \cdot DD_2 -DD_1 \cdot AA_2\right) -\left( AA_1 \cdot EE_2 -EE_1 \cdot AA_2\right) ^{2}\\ cy[1]&= 2\cdot \left( FF_1 \cdot AA_2 -AA_1 \cdot FF_2\right) \cdot \left( AA_1 \cdot EE_2 -EE_1 \cdot AA_2\right) \\&\quad +\left( DD_1 \cdot EE_2 +BB_1 \cdot FF_2 -FF_1 \cdot BB_2 -EE_1 \cdot DD_2\right) \\&\quad \cdot \left( AA_1 \cdot DD_2 -DD_1 \cdot AA_2\right) \\&\quad +\left( DD_1 \cdot FF_2 -FF_1 \cdot DD_2\right) \cdot \left( AA_1 \cdot BB_2 -BB_1 \cdot AA_2\right) \\ cy[0]&= \left( DD_1 \cdot FF_2 -FF_1 \cdot DD_2\right) \cdot \left( AA_1 \cdot DD_2 -DD_1 \cdot AA_2\right) \\&\quad -\left( AA_1 \cdot FF_2 -FF_1 \cdot AA_2\right) ^{2} \end{aligned}$$

When roots of Eq. (15) are found, $y$-values where the polynomials of Eq. (12) intersect can be determined by:

$$\begin{aligned} \bar{y}=\frac{AA_1 \cdot (CC_2 \cdot \bar{y}^{2}{+}EE_2 \cdot \bar{y}{+}FF_2){-}AA_2 \cdot (CC_1 \cdot \bar{y}^{2}{+}EE_1 \cdot \bar{y}+FF_1)}{AA_2 \cdot \left( BB_1 \cdot \bar{y}+DD_1\right) -AA_1 \cdot \left( BB_2 \cdot \bar{y}+DD_2\right) }\nonumber \\ \end{aligned}$$

(16)

To find points of intersection, substitute each $\bar{\hbox {y}}$ back into Eq. (12a) (or Eq. (12b)), and solve for two $\bar{\hbox {x}}$ values, using the quadratic formula:

$$\begin{aligned} \bar{x} =\frac{-\left( BB_1 \cdot \bar{y} +DD_1\right) \pm AA_2 \cdot \sqrt{\left( {BB_1 \cdot \bar{y}+DD_1 }\right) ^{2}-4\cdot AA_1 \cdot \left( {CC_1 \cdot \bar{y}^{2}+EE_1 \cdot \bar{y} +FF_1 } \right) }}{2\cdot AA_1} \end{aligned}$$

(17)

Pairs $\left( \bar{\hbox {x}}, \bar{\hbox {y}}\right)$ that satisfy both Eqs. (12a) and (12b) represent points of intersection of the two original ellipses.

Many options exist for numeric solution of the quartic polynomial in Eq. (15); see, e.g, [16] or [6] for a survey of modern methods, and [13] for a comprehensive list of root-finding references. However, polynomial root-finding remains a challenging problem, and until recently the accuracy of most numerical implementations has been limited, particularly when multiple roots are present or when inexact coefficients are supplied. Several algorithms have been introduced recently that provide improved accuracy. One such algorithm is described in [15], based on recursive numerical splitting of the input polynomial into the product of factors. Another routine with improved accuracy is gsl_poly_complex_solve from the GNU scientific library (GSL), which is based on [19]. A custom GSL extension specifically for quartic polynomials is also available [18]. The algorithm in [19] first calculates the multiplicity structure for the roots, and computes an initial approximation to the roots; the initial approximation is then refined to an optimal accuracy.

In the context of determining ellipse area overlap for a simulation, some benefit may be obtained from a non-iterative solution of the quartic equation, even if results are less accurate than iterative solvers can provide. An expedient (non-iterative) method for determining roots of the polynomial in Eq. (15) can be accomplished using Ferrari’s quartic formula. A numerical implementation of Ferrari’s formula is given in [14]. Four complex roots are returned, and any roots whose imaginary part is returned as zero is a real root. When polynomial coefficients are constructed as in Eq. (15), the general case of two distinct ellipses typically results in a quartic polynomial, i.e., the coefficient cy[4] of Eq. (15) is non-zero. However, certain cases lead to polynomials of lesser degree. The solver in [14] is conveniently modular, providing separate functions BIQUADROOTS, CUBICROOTS and QUADROOTS to handle all the possible polynomial cases that arise when seeking points of intersection for two ellipses.

3.3 Determining transverse intersection points II: tools from algebraic geometry

To identify intersection points, the direct approach of solving the two implicit ellipse equations simultaneously is easily implemented. However, even with accurate root-finding algorithms, the direct approach encounters difficulties with some ill-conditioned cases. The root-finding algorithms in

[15] and [19] are robust in general situations; even so, both algorithms are still susceptible to error propagation from inexact coefficients, particularly when there are multiple roots or roots that are clustered very close together. The direct approach calculates polynomial coefficients from Eq. (15), and will send difficult polynomials to the root-finding routine in cases where the curves intersect at a shallow angle. Robustness of the area overlap algorithm can be improved using methods from algebraic geometry that have been designed specifically for identifying intersection points of implicitly defined curves.

Several independent approaches are available for finding intersection points of two implicit curves. [12] describe a method for computing geometrically isolated higher order intersections of curves. A similar method is described in [3]. Both of these methods are based on solving an Eigen-problem that is related to companion matrices of the two implicit ellipse curves. In the context of finding intersection points, one advantage of the companion matrix approach is that accuracy of numerical approaches for Eigen-problems is well-studied, and error bounds for intersection points can be established.

3.4 Overlap area determination

In six of the 10 possible relative positions of two ellipses shown in Fig. 3, ellipse overlap area can be calculated directly. In relative positions 3 and 6, the ellipses are disjoint and the overlap area is 0. In relative position 10 (coincident ellipses), the overlap area is $\pi \cdot A \cdot B$. For relative positions 4, 7 and 8, the overlap area is the area of the contained ellipse, which must be the smaller of the two ellipse areas.

Relative positions 2 and 9 each have two intersection points. Overlap area is found by adding the area of two ellipse segments, one from each ellipse, as shown in Fig. 4. The two intersection points $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$ must be passed to the segment area algorithm in the order that will return the correct segment from each ellipse. Only one area from each ellipse contributes to the overlap area. A check is made to determine which point order will return the desired segment area for each ellipse. First, the parametric angles $\theta _{1}$ and $\theta _{2}$ corresponding to $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$ on the first ellipse are determined, by the rules in Table 1. Then, a point midway between $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$ on the first ellipse is found using the parametric form:

$$\begin{aligned} x_{mid}&= A\cdot cos (\varphi _1)\cdot cos\left( \frac{\theta _1 +\theta _2}{2}\right) \nonumber \\&\quad -B\cdot sin (\varphi _1)\cdot sin\left( {\frac{\theta _1 +\theta _2}{2}}\right) +h_1\end{aligned}$$

(18a)

$$\begin{aligned} y_{mid}&= A\cdot sin (\varphi _1)\cdot cos\left( \frac{\theta _1 +\theta _2}{2}\right) \nonumber \\&\quad +B\cdot cos(\varphi _1)\cdot sin\left( \frac{\theta _1 +\theta _2 }{2}\right) +k_1 \end{aligned}$$

(18b)

The point $(x_{{\mathrm{mid}}}, y_{{\mathrm{mid}}})$ is on the first ellipse between $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$ when travelling counter- clockwise from $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$. If $(x_{{\mathrm{mid}}}, y_{{\mathrm{mid}}})$ is inside the second ellipse, then the desired segment of the first ellipse contains the point $(x_{{\mathrm{mid}}}, y_{{\mathrm{mid}}})$, and the segment algorithm should integrate counterclockwise from $(x_{1}, y_{1})$ to $(x_{2}, y_{2})$, which is the default order. Otherwise, the order of the points should be reversed before calling the segment algorithm. The implicit polynomial form can be used to determine whether $(x_{{\mathrm{mid}}}, y_{{\mathrm{mid}}})$ is inside or outside the second ellipse:

$$\begin{aligned} T&= AA_2 \cdot x_{mid}^2 +BB_2 \cdot x_{mid} \cdot y_{mid} +CC_2 \cdot y_{mid}^2 \nonumber \\&+DD_2 \cdot x_{mid} +EE_2 \cdot y_{mid} +FF_2 \end{aligned}$$

(19)

If $T < 0$ then the point $(x_{{\mathrm{mid}}}, y_{{\mathrm{mid}}})$ is inside the second ellipse. The desired segment area from the second ellipse is found in a manner similar to the first ellipse.

Fig. 4

Relative Positions 2 and 9 have two transverse intersection points. Overlap area is found by adding the area of two ellipse segments, one from each ellipse

Relative position 5 has three intersection points, but only two are transverse. Overlap area can be found by the same method as relative positions 2 and 9, if the two transverse intersection points are used, as shown in Fig. 5. For ellipses in relative position 5, the transverse intersection points correspond to roots of multiplicity 1. The tangential intersection point corresponds to a root of multiplicity 2. For ellipses in relative position 9, there are two transverse intersection points; one of the points corresponds to a root of multiplicity 1, and the other corresponds to a root of multiplicity 3.

Fig. 5

Relative position 5 (left) has three intersection points, but only two are transverse. Overlap area is found by determining which two points are transverse, then adding the area of two ellipse segments, one from each ellipse. Relative position 1 (right) has four transverse intersection points. Overlap area is found by adding the area of four ellipse segments, two from each ellipse, and one quadrilateral

Relative position 1 consists four transverse intersection points, shown in Fig. 5. The two ellipse curves must cross at all four of the intersection points, resulting in a partial overlap. The overlap area consists of two segments from each ellipse, and a central convex quadrilateral. The four intersection points are sorted ascending in a counter-clockwise order around the first ellipse. The ordered set of intersection points is $(x_{1}, y_{1}), (x_{2}, y_{2}), (x_{3}, y_{3})$ and $(x_{4}, y_{4})$. The ordering allows a direct calculation of the quadrilateral area. The standard formula uses the cross-product of the two diagonals:

$$\begin{aligned} \hbox {area}&= \frac{1}{2}\left| {\left( {\hbox {x}_3-\hbox {x}_1, \hbox {y}_3 -\hbox {y}_1}\right) \times \left( {\hbox {x}_4 -\hbox {x}_2, \hbox {y}_4 -\hbox {y}_2}\right) } \right| \nonumber \\&= \frac{1}{2}\left| {\left( {\hbox {x}_3 -\hbox {x}_1}\right) \cdot \left( {\hbox {y}_4 -\hbox {y}_2}\right) -\left( {\hbox {x}_4 -\hbox {x}_2}\right) \cdot \left( {\hbox {x}_3 -\hbox {x}_1}\right) } \right| \nonumber \\ \end{aligned}$$

(20)

The point ordering also simplifies the search for the appropriate segments of each ellipse that contribute to the overlap area. Suppose that the first two sorted points $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$ demarcate a segment of the first ellipse that contributes to the overlap area. It follows that contributing segments from the first ellipse are between the points $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$, and also between the points $(x_{3}, y_{3})$ and $(x_{4}, y_{4})$. In this case, the contributing segments from the second ellipse are between the points $(x_{2}, y_{2})$ and $(x_{3}, y_{3})$, and between the points $(x_{4}, y_{4})$ and $(x_{1}, y_{1})$. To determine which segments contribute to the overlap area, it suffices to test whether a point midway between the points $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$ is inside or outside the second ellipse. The segment algorithm is used for each of the four areas, and added to the quadrilateral to obtain the total overlap area.

3.5 General overlap area algorithm

Combining the results presented above leads to an algorithm for determining the overlap area between two general ellipses defined parametrically as $(A_{1}, B_{1}, h_{1}, k_{1}, \varphi _{1})$ and $(A_{2}, B_{2}, h_{2}, k_{2}, \varphi _{2})$. The algorithm ELLIPSE_OVERLAP is outlined below. Condition of the implicitization operation can be improved for some difficult cases by translating both ellipses to put the midpoint of the two ellipse centers at the origin. Translation does not affect the relative position of the two original ellipses.

• 1. $\left\{ A_1, B_1, \bar{h}_1, \bar{k}_1, \varphi _1\right\} , \left\{ A_2, B_2, \bar{h}_2, \bar{k}_2, \varphi _2\right\}$ Inputs to the algorithm

• 2. $\left[ {\begin{array}{l} \bar{h}_i\\ \bar{k}_i\\ \end{array}}\right] =\left[ {\begin{array}{l} h_i -\frac{h_1 +h_2}{2}\\ k_i -\frac{k_1 +k_2}{2}\\ \end{array}}\right] ,i=1,2$

• 3. $\begin{array}{l} \!\!\left\{ \!A_1, B_1, \bar{h}_1, \bar{k}_1, \varphi _1\!\right\} \!{\rightarrow }\!\left\{ \!AA_1,\! BB_1,\! CC_1,\! DD_1,\! EE_1,\! FF_1\right\} \!\!\left\{ \!A_2, B_2, \bar{h}_2, \bar{k}_2, \varphi _2\right\} \!{\rightarrow }\! \left\{ \!AA_2,\! BB_2,\! CC_2,\! DD_2,\! EE_2,\! FF_2\right\} \end{array}$ by Eq. (5)

• 4. Determine relative position of the two implicitly defined ellipses by ELLIPSE_CASE algorithm adapted from [7], as given in Sect. 3.1

• 5. RELATIVE POSITION:

  • CASE10: one ellipse contained in the other

    • AREA $= \pi \cdot A_1 \cdot B_1 = \pi \cdot A_2 \cdot B_2 :\hbox {RETURN}$

  • CASE 3, 6: no overlap area

    • AREA=0: RETURN

  • CASE 4, 7, 8: one ellipse contained in the other

    • AREA $=\min \left\{ \pi \cdot A_1 \cdot B_1, \pi \cdot A_2 \cdot B_2\right\} :\hbox {RETURN}$

  • CASE 1, 2, 5, 9: transverse intersections

    • Calculate coefficients cy[4], cy[3], cy[2], cy[1], cy[0] by Eq. (15)

    • Solve quartic $cy[4]\cdot y^{4}+cy[3]\cdot y^{3}+cy[2]\cdot y^{2}+cy[1]\cdot y^{1}+cy[0]=0$

    • Calculate intersection points $\left( \bar{\hbox {x}}, \bar{\hbox {y}}\right)$ by Eqs. (16) and (17)

    • CASE 2, 5, 9: two transverse intersections

      • Calculate segment area contributed by each ellipse using ELLIPSE_SEGMENT algorithm, as given in Sect. 2.4

      • AREA $=$ Segment 1 $+$ Segment 2:RETURN

    • CASE 1: four transverse intersections

      • Calculate four segment areas contributed by each ellipse using ELLIPSE_SEGMENT algorithm, as given in Sect. 2.4

      • Calculate quadrilateral area contributed by each ellipse using Eq. (20)

      • AREA $=$ Segment 1 $+$ Segment 2 $+$ Segment 3 $+$  Segment 4+Quadrilateral :RETURN

3.6 Notes on accuracy, precision, and robustness

The algorithms presented in this paper describe an approach for determining the overlap area between two general ellipses. Any numerical implementation of the algorithm is susceptible to propagation of fixed-point round-off errors. Round-off errors that arise during implicitization of the ellipse parameters using Eq. (5) can produce inexact polynomial coefficients, leading to inaccurate roots. Inaccuracy the polynomial roots produces perturbed intersection points, and the error propagates to the determination of polygon and ellipse sector areas. Closed-form determination of overlap areas is not available for all but the simplest cases, so absolute accuracy of the algorithm is not obtainable. For ellipses that are commonly encountered in applications, errors in the overlap area algorithm are directly tied to root-finding, for which error bounds are available [15]. We have encountered some ‘odd’ cases, such as extremely eccentric ellipses, where the algorithm returns the wrong polynomial case; in these situations, the area returned by the algorithm is unrelated to the actual overlap area.

A relevant question is whether the algorithm as presented here will handle cases where one or both ellipses are circles. In such cases, inputs to the algorithm could include one or two ellipses defined using the parametric definition for an ellipse as $(A, A, h, k, 0)$, representing a circle of radius $A$ centered at $(h, k)$. The implicitization of Eq. (5) is still valid, and simplifies to:

$$\begin{aligned} AA&= a_{1,1} =\frac{1}{A^{2}}\end{aligned}$$

(21a)

$$\begin{aligned} BB&= 2\cdot a_{1,2} =0\end{aligned}$$

(21b)

$$\begin{aligned} CC&= a_{2,2} =\frac{1}{A^{2}}\end{aligned}$$

(21c)

$$\begin{aligned} DD&= 2\cdot a_{1,3} =\frac{-2\cdot h}{A^{2}}\end{aligned}$$

(21d)

$$\begin{aligned} EE&= 2\cdot a_{2,3} =\frac{-2\cdot k}{A^{2}}\end{aligned}$$

(21e)

$$\begin{aligned} FF&= a_{3,3} =\frac{h^{2}}{A^{2}}+\frac{k^{2}}{A^{2}}-1 \end{aligned}$$

(21f)

Following the algorithm by inputting circles as ellipses with the appropriate features, the polynomial coefficients of Eq. (15) are calculated, as shown in Eq. (21), and the algorithm returns the correct overlap area where one or both curves are circles. The eccentricity of a circle is zero, so circles do not result in eccentricity-related issues for the algorithm. Circles that are very close in size and position can still lead to difficult root-finding cases.

An implementation in C-code of the ELLIPSE_OVERLAP algorithm and all of its dependencies was compiled and run under Cygwin-1.7.7-1 and Debian 7.2 (Wheezy), and returns the following values for examples of the test cases presented in Fig. 3:

The accuracy of the algorithm, as implemented in C and C++, was tested extensively. We compare the results of 1,000 selected pairs of ellipses with the overlap areas and calculation times of the corresponding $n$-sided polygons. Figure 6 shows that implementation of the analytical solution on an Intel Core i7-2620M, 2,7 GHz, 4MB Cache, is 40–140 times faster than the solution based a polygon-approximation of ellipses. For the results presented in Fig. 6, we make use of the C++-library Boost-polygon [2]. Figure 7 shows a quantitative visualization of the calculated crossing points of selected ellipses. The code is open source and can be downloaded from https://github.com/chraibi/EEOver.

Fig. 6

Top: The ratio of the run-time of the polygon-based method $(t_{p})$ and the analytical solution presented in this paper as implemented in C++ $(t_{e})$ with respect to the number of edges. Bottom: The relative error of the calculated overlap areas with respect to the number of edges of a corresponding $n$-sided polygons used to approximate the area

Fig. 7

Results of selected test cases. The red and blue points represent ellipse centers, and green points represent intersection points, calculated with the algorithm as implemented in C++