You should be able to use an appraoch like the following:
- 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.)
- 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.
- 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.
- Mark the neighbors to those inner points that were not removed the "loose ends" of the circles.
- Connect the points that were not removed, including the loose ends, to their original left and right neighbors.
- 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.)