Area of intersection of n circles each having radius 'r'

Prob Statement: 'N' equal radii circles are plotted on a graph from (-)infinity to (+)infinity.Find the total area of intersection I.e all the area on the graph which is covered by开发者_如何学编程 two or more circles.

Firstly a correction: these aren't circles. They're ellipses (circles being a special case of ellipses where a = b). You can calculate the intersection of two ellipses so given N ellipses you need to check each pair, so the entire operation is O(n²) (multiplied by whatever the intersection operation is).

Take a look at Intersection of Ellipses and The Area of Intersecting Ellipses.

Edit: the intersection of circles is an easier problem but follows the same principle. Take a look at Intersection Of Two Circles and Circle-Circle Intersection.

Easiest (not necessarily fastest or "best") way to code is to find the bounding box that contains all circles and then use a numerical stochastic method to integrate.

Now by being smart you can probably group circles and box them separately, i.e work in a number of bounding boxes. And even handle certain special cases exactly.

But a pure stochastic method has the beauty of being easy to implement (but potentially slow).

This is only acceptable if you are happy to have an "approximate" (but arbitrarily close to correct) answer.