# the intersection of n disks/circles

Given that $n$ disks/circles share a common area, meaning that every two of them intersect or overlap one another, and we know their coordinates $（x_{1},y_{1},r_{1})$, $(x_{2},y_{2},r_{2})$, ..., $(x_{n},y_{n},r_{n})$, where $x_{i}$,$y_{i}$,$r_{i}$ represent the $x$ axis coordinate, the $y$ axis coordinate, and the radius of the $i$-th disk/circle, respectively, can you provide a method to calculate the coordinate of the centroid of the intersection of these disks/circles?

-
I assume you mean that $x_i$ and $y_i$ are the coordinates of the centre of the $i$th circle, but you should say so explicitly. –  Chris Eagle Oct 27 '12 at 7:45
Can more than two disks intersect at the same point? If so, this looks like a messy calculation involving integrals, and inclusion-exclusion. –  ronno Oct 27 '12 at 20:37
@Chris Eagle, You perfer to the explicit descripition. Great! But sometimes implicit descripition is enough. ^^ I guess you are a person who like to pursue perfection. –  York Tsai Oct 29 '12 at 13:41
@ronno, n disks can intersect at the same point. But you can do not consider this particular scenario. –  York Tsai Oct 29 '12 at 13:43
Do you know how to compute the area and centroid of the intersection of two disks? –  ronno Oct 29 '12 at 13:56

The intersection of $n$ disks is a convex shape bounded by circular arcs that meet at vertices where two or more circles intersect.

The first thing to do is to identify these vertices and the arcs that connect them to each other. If no three circles are coincident,$^1$ then this isn't very hard: Consider every pair of circles; find their two intersection points, which form two candidate vertices; if a candidate vertex is inside all other circles, then it is indeed a vertex of the intersection. This gives you a set of vertices.$^2$ Each vertex lies on exactly two circles; using this connectivity, you can sort them in consistent order around the intersection shape.

Now you can decompose the intersection shape into a number of pieces: (i) the polygon (shaded blue above) that connects the vertices, and (ii) a collection of circular segments (shaded red), one for each arc of the shape. You can find the areas and centroids of each piece using closed-form formulas (polygon, circular segment). The centroid of the full shape is then just the weighted average of the centroids of each of the pieces, weighted by area.

$^1$If multiple circles are coincident on a vertex, then doing pairwise tests may not always get you a consistent set of vertices, especially if you're using floating-point arithmetic. You might be able to get around this to some extent by fudging the inside-circle test with some epsilon bias, but a truly robust solution would have to come from a computational geometry expert.

$^2$It's possible that the set of vertices turns out to be empty. Then there are two possibilities: either the intersection is equal to one of the circles, or the intersection is empty. It is easy to distinguish between these two cases by checking if there exists a circle that is entirely inside all the others.

-
@Rahual Narain, rigorous, thorough, beautiful, you present such a solution. Seem to omit nothing. Very enjoyable. –  York Tsai Oct 30 '12 at 17:58
@Rahual Narain, how do you draw this graph? What graphic software do you use? It seems that you implement it by coding a program, right? –  York Tsai Oct 30 '12 at 18:02
@York, if you are happy with this answer, you can mark it as accepted by clicking the grey check mark to its left. –  Rahul Oct 30 '12 at 19:05
I drew the figure in Inkscape. –  Rahul Oct 30 '12 at 19:05
@Rahual, inkscape, an open source tool, fantastic! Thank you very much. –  York Tsai Oct 31 '12 at 6:35