Algorithm for joining circles into a polygon

Question

What is the best way of combining overlapping circles into polygons?

I am given a list of centre points of circles with a fixed diameter.

I need to join any overlapping circles together and output a list of points in the resulting polygon.

This seems like a fairly common problem (GIS systems, vectors, etc.). This is possible to do through the Google Maps API but I am looking for the actual algorithm.

I have tried to solve this problem by calculating points around each circle.

Then removing any points located inside any circle.

This gives me the correct list of points in the desired polygon.

However, the order of the points is a problem with this solution. Each circle has its points stored in an array. To merge them correctly with 2 overlapping circles is relatively straight forward. However, when dealing with multiple overlapping circles it gets complicated.

Hopefully you have some ideas to either make this solution work or of another algorithm that will achieve the desired result.

Thanks in advance!

Answer 1

You should be able to use an appraoch like the following:

1. First, identify circles that belong to the same group of overlapping circles. Obviously, two circles overlap if the absolute distance of their centres is less than their combined radii. For each circle, store the circles it itersecs with in a hashmap/dictionary. (You can extend this to entire groups of circles using the union-find algorithm, or disjoint sets, but this is not really needed.)
2. When creating the points belonging to one circle, memorize the left and right neighbor of each point. You get this for free by just storing them in an ordered array.
3. Remove the "inner" points, i.e. those that are closer than one radius to any of the centres of the circles intersecting the first circle.
4. Mark the neighbors to those inner points that were not removed the "loose ends" of the circles.
5. Connect the points that were not removed, including the loose ends, to their original left and right neighbors.
6. For each loose end point, find the closest loose end of a different circle in the same group and connect them.

Here's a picture to illustrate the approach.

• Red dots are "inner" points that are removed
• Blue dots are "loose ends" by being neighbors to "inner" points; each "loose end" has another "loose end" of a different circle that's less than two "point-distances" away
• Green dots can easily be connected to their neighbors (including the "loose ends") by the order in which they were arranged around the circle.

You can further decrease the number of possible combinations by distinguishing left and right loose ends, and using the fact that each left loose end of one circle has to be connected to a right loose end of another circle. For n circles in a group, that leaves just (n-1)! ways to connect those circles, irrespective of the number of points per circle.

And even this can be reduced further if you consider only those circles in the group that actually intersect the circle with the loose end (just store those in a hashmap/dictionary). So if you have n circles that on average intersect with k other circles, then there are only n*k possible combinations.

You could also use the fact that the other loose end can not be farther away than two times the distance between two point on the circle. Let's call this distance d, then you can create a spatial map with resolution d (e.g. a hashmap, or just a 2D array) and assign each loose end to cells in that map, then the other loose end must be in the same of one of the surrounding cells of the first loose end.

Thus, the number of ways in which points can be connected to each other is greatly reduced (in particular, the way they are connected in your final image would not be allowed to begin with): This should be doable even with brute force unless you have lots of overlapping circles in the same group, and there are smarter algorithms for nearest-neighbor search that you can use.

---

Update: Reviewing this answer after some time, it seems that you can determine the matching pairs of "loose end" points rather easily: Say you have a "right" loose end in circle A, then the matching "left" loose end has to belong to the circle whose radius overlapped the next "inner" point to the first "loose end". So if you store that relation in another map, you can immediately determine the matching loose end. (If an inner point is overlapped by multiple other circles, the map should contain the circle that overlaps it the most.)

Answer 2

Here's a sketch of an O(n log n)-time algorithm.

1. Use your favorite algorithm/library to compute a Delaunay triangulation on the circle centers.

2. Delete the edges between circles that do not overlap.

3. Walk around the infinite face of each connected component. This is easy to do with a doubly connected edge list representation, where the ordering of the edge lists is used to indicate the topology of the planar graph. Every half-edge on this boundary turns into a vertex where an arc segment belonging to its tail point ends and an arc segment belonging to its head point begins.

4. (Optional) Approximate each arc segment by a polygonal line.

_{If anyone from Google is reading this, please note that I have not looked at the relevant code.}