Finding all regions defined by a set of pseudorandom circles. Here, 8 input circles gave 37 output regions.
Python using pyclipper for 2d predicates & matplotlib for display. The (probably inefficient and maybe wrong) algorithm for ensuring all regions are found by me using trial and error.
pssst don't tell anyone but the circles are actually just 360-gons.
I'm not sure what the correct algorithm is, but here's what I did: For each input circle 'ci', start by creating a set of boundaries that just consists of that circle {ci}.
Then, for each circle cj ≠ ci, update the set, replacing a set element e with e & ci (the intersection) and e - ci (the difference) of the shapes. In the end, this gives all the subdivisions of the original circle ci.
The final output is set of all subdivisions created in this way.
I don't know if this process will be fast enough for my ultimate goals (hundreds of circles but not thousands); the first optimization would be a sweep-line algorithm to avoid considering many circle pairs.
The most obvious optimization to make would be to use a sweep-line algorithm to avoid useless intersection/difference operations.
Stylus