Calculating the regions of intersecting circles can be solved completely geometrically, by iterating through all of the circle intersections, and reducing the results into intersected and subtracted areas, until there are none left. However, this can also be done with graphs.

Graphs are a data structure made up of nodes, which can be connected to one or more nodes with edges. You can then use these edges to traverse from node to node (!!! Fig 404 !!!).

For this concept of finding the intersections, our graph will be made up of nodes that represent the points of intersection (how we get these, coming up), and the connections between the nodes (the edges) will be the arcs between the intersection points (more on this).

Finding the nodes and edges

Starting with any number of circles, for which we know the center point as X and Y coordinates and the radius of the circle. The only geometric calculation we have to do to get our starting dataset of arcs is to test each circle against every other circle for an intersection (This is already a well solved problem).

Using all of the intersection points (our nodes), we have a reference to the 2 circles that contributed to the intersection, and we can determine the arcs (the edges) by finding the next intersection point (counter/clockwise) of each of the circles involved in the intersection.

From here, we can now use the identified nodes to describe areas of intersection. For example, [0 -> 2 -> 1 -> 0], would describe the top most intersection area.

A quick edge case

Before we start looking at how to traverse this graph to find the intersection areas, consider this edge case. With the circle arrangement (!!! Fig 404 !!!), we can easily describe the path of every single one of those intersection areas by using the node identifiers. Now consider where there are just 2 overlapping circles (!!! Fig 404 !!!), giving us just 2 nodes on our graph, but 4 edges.

How are we now supposed to describe a path that makes up the intersection areas? If I said [0 -> 1 -> 0] or [1 -> 0 -> 1], which one of the intersection areas does that cover?

We also need to be able to identify the edges, so we can specify which one we want to traverse (!!! Fig 404 !!!). Now we can describe traversals like [0.2.1 -> 1.3.0], in other words "Traverse from node 0 to node 1 via edge 2, then traverse from node 1 to node 0 via edge 3", to get us the left most intersection are.

Storing traversals

Now that we have a way to refer to these traversals we need to be able to store them (this will become apparent in just a moment). One thing we need to consider with storing traversals, is we need to be able to reference them irrespective of the direction the graph has been traversed.

As an example (!!! Fig 404 !!!), the intersection described as [0.2.1 -> 1.3.0], we could have traversed in the opposite direction, giving us a path of [0.3.1 -> 1.2.0]. We could have also started at Node 1, giving us another 2 possible paths of [1.3.0 -> 0.2.1] and [1.2.0 -> 0.3.1].

One way to overcome this is to store them in a Bitset (a sequence of 0s and 1s), where each Bit refers to the index of a Node or an Edge. If the Node or Edge is used in the traversal, we flip the Bit to a 1, if not it remains a 0.

This may seem unnecessary with the example above of 2 nodes as we could easily stored all 4 combinations, however the number of permutations follows nodes visited * 4, so 3 nodes has 12 permutations, 4 nodes has 16, 5 has 20, etc... Using a Bitset we can cover all the possible variations with a single comparable entity.

The rules for a traversal

To form all the valid intersections paths existing in our graph, we can traverse the graph while applying 5 very simple rules.