The idea for this mini project emerged when I was watching how marks left by rain drops on a terrace incrementally turned the dry wood to a darker, wet version of itself. As more drops would conquer new terrain, some would also fall partially or fully within previously made marks. I wondered if I would be able to model that process, and simulate the time required to cover a given area. The method would have to take into account overlapping circles so no area would be counted twice.

After the obligatory google search I found an interesting question on stackoverflow discussing possible ways to compute the combined area of overlapping circles. Some methods proposed to brute force the solution by performing a Monte Carlo simulation of a number of points in a bounding box. The area of the circles could then be approximated by taking the share of points encompassed by the circles and multiplying it with the area of the box. Another method proposed an exact solution, but I could not find a fleshed out implementation of it.

Thus my mini project was taking form; I would try to implement a slightly altered version of both methods in Python using Object-oriented programming. I reckoned it would be a good exercise, and since I was set on making visualizations using the d3.js javaScript library based on some user input I would have to make calls to the server with Ajax.

Identifying clusters

The first step in computing the combined area of the circles is computing all the intersections between each circle. From those intersections we can then easily enough start at a random circle, identify other circles intersecting with it, and continue that process until no new circle can be found. This results in our first step: a group of circles intersecting with one another, as well as their intersections which we will need further on.

There are obviously exceptions: some circles will have no intersections at all. If they are encompassed by any other circle we remove them as they do not provide any information for the computation of the total area, otherwise they are considered as single-circle clusters. Some identified clusters might also be encompassed by a circle, and again will be removed.

In the visualization below you can observe the cluster identification process; Each (set of) pulsating circle(s) intersected with the previously pulsating circle(s). For those circles we draw the corresponding intersections. The removal of encompassed circles is also visualized.

Click on a cluster for its vizualization.

Filtering intersections

Next up we filter any intersection which is encompassed by a circle, such that we are left with only intersections lying on the boundary of the cluster. For two-circle clusters, obviously no intersections can be filtered. Also note that clusters might have gaps or holes in them, and that intersections lying on these inner boundaries are not encompassed by any circle either.

From the visualization: for each drawn intersection we assess if it is encompassed by any circle, and if so we pulsate that circle and draw the point red. Blue points are intersections lying on the outer or one of the inner boundaries of the cluster.

Click on a cluster for its vizualization.

Defining polygons

For clusters of two or more circles, we are thus left with all the intersections lying on the boundary of the cluster. Computing the area of the polygon bounded by these intersections can be solved by a simple algorithm, but for that its vertices need to be ordered clockwise. To find the correct order we start at some remaining intersection and pick another intersection on that same circle which results in the smallest angle formed. Then we reiterate the process for the newly added intersection and its corresponding circle until the loop is closed.

Note that the graph only visualizes the process for the outer boundary of a cluster. For inner boundaries the method used is identical, but in those cases we look for the largest angle.

Click on a cluster for its vizualization.

Computing areas

Finally we determine the method we will use to compute the area of each cluster. For a single-circle cluster the answer is straightforward, and for a two-circle cluster it is a simple case of calculus. For clusters of more than two circles we can now compute the area of the polygon bounded by the intersections lying on the outer boundary.

To compute the area of the parts of the circles which are not encompassed by the polygon we can use the formula for the circular segment, which is in fact a subcomponent for computing the area of two circles. Note that for some circles the part not included should be equal to the circular segment, but for others it should be equal to the area of that circle minus the circular segment. One method to decide between both is to check if the centerpoint of the circle lies inside of the polygon. For inner boundaries a similar process is performed. I have put the code on github with a short notebook explaining how to use the library.

Hover over a cluster for its vizualization.

Published on 20 August 2018