Eeover

Ellipse-Ellipse overlap area:

This program calculates the overlapping area of two arbitrary ellipses. It implements the algorithm published in this paper. See also the available preprint. The page if this project is here.

Usage:

• compile the code:

make

This should produce an executable (overlap)

• run the executable with an input-file and an id:

./overlap inputfile id

(id is 1 or 2 to choose between two different quartic solvers)

• This should produce two output-files:

• result-File: results.txt

• root-File: roots.txt

Contents and Formats of files:

• the input-File should be in the following format

id A1 B1 H1 K1 PHI_1 A2 B2 H2 K2 PHI_2

(11 columns)

• id is a running number
• Ax and
• Bx are semi-axes of the one ellipse with the center coordinates
• (Hx, Kx)
• and the inclination with respect to the x-axis Phi_x (x in {1, 2})

• results-File is in the following format:

id areaE1 areaE2 OverlapAreaAnalytical OverlapAreaPolynomial rel_err

• roots-File contains the coordinates of the intersection points (if any):

id x0 y0 x1 y1 x2 y2 ...

this file is used by the plot-script

How to visualize the results:

python plot.py inputFile rootsFile resultsFile

That would produce in the directory ./cases/ a couple of png's

Requirements:

• > GSL: to solve the quartic equations
• (optional) > Boost.polygon: to compare the results of this code, the overlap-area of polygonized ellipses is calculated with Boost.polygon. In case you don't have boost installed (and don't want to) then you need to set USING_BOOST in call_ee.cpp to 0

#define USING_BOOST 0

Remarks:

The solver of the quartic function is the central part of the code. Actually, two different solvers are used separately:

• gsl_poly_complex_solve() from GSL,
• and gsl_poly_complex_solve_quartic() from Andrew Steiner.
  

The second one is faster, however fails to calculate accurately the roots of test_5.

To do:

• [ ] Implement the algorithm from the paper The fast quartic solver by Peter Strobach.
• [ ] Try MPSolve. This library adds some dependencies though.
• [ ] Add more tests to cover all the cases.