# Finding circle intersections with graphs

## An explanation in using graphs to find intersections of geometry by conditionally and dynamically creating connections that follow a set of rules.

19 Aug 2021

This is a rewrite of a previous article, which I didn't like as it didn't focus on the main concept of traversing the intersections with graphs. You can read the origin article here.

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 (visual representation below).

**Fig 1.**Graph visual representation

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.

**Fig 2.**Arrangement of three intersecting circles. A graph in it's entirety

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 in Fig 2, we can easily describe the path of every single one of those intersection areas by using the node identifiers. Now consider Fig 3, where there are just 2 overlapping circles, giving us just 2 nodes on our graph, but 4 edges.

**Fig 3.**Arrangement of two intersecting circles.

**Fig 4.**Arrangement of two intersecting circles, with labelled 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 4). 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.

Using Fig 4 as an example, 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.

**Fig 5.**Bitsets of all the valid traversals in Fig 4

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.

An interactive intersection graph explorer

Below is an interactive explorer that allows you to click on the intersection points to create intersecting regions. Showing you what are the valid points, and what the reasons for their exclusion.

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

1

2

3

4

5

Rule Example Configurations

Summary

While re-writing this article, it occurred to me that this approach is not isolated to just circles. Without any exploration into this thought, I believe this approach could be applied to any shapes.

I haven't done any benchmarks on the performance of this algorithm, nor have I spent any time optimizing my implementation, however in theory it should be pretty fast 🤷♂️.

Harrison Hogg

Software Engineer

# Finding circle intersections with graphs

## An explanation in using graphs to find intersections of geometry by conditionally and dynamically creating connections that follow a set of rules.

19 Aug 2021

svg

visualisation

geometry

data structures

graphs

bitset