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.
1
No going back
After traversing from one node to another, you cannot traverse back to the same node.
2
Within bounds
The traversal path must not cross into or out of any circles that have been traversed before.
3
Unique
The Bitset of a traversal with 2 or more edges must not exist in previous traversals.
4
Node 4 max traversals
A node can only be visited a maximum of 4 times.
5
Edge 2 max traversals
An edge can only be visited a maximum of 2 times.
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
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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

Finding the optimal solution for solving the classic game of Snake with pathfinding and heuristics

An exploration into finding the most optimal programmatic solution for completing the classic game of snake.