User talk:Vballhermie007

From Rosetta Code

Total circles area

For a demonstration of the algorithm see http://stackoverflow.com/a/1667789/10562

The algorithm itself I described below the Haskell code on the task page, which would probably be easier to follow if you sketch a few circles on a piece of paper and try to verify it step by step. I understand that the Haskell code is kinda hard to follow, despite it having been cleaned up by someone else already, but believe me that it would be even harder to read had I written it in C++, because of, well, me and C++. But once you understand how the algorithm works, it's really nothing more than elementary geometry and bookkeeping, tedious as it may be, rocket science it is not.

That being said, I don't really recommend the algorithm if you need it for serious work. Depending on the circles you have, the algorithm can be error-prone if intersection points are very close to each other. The algorithm depends on the correct construction of an outline for the union of overlapping circles, which in turn depends on correctly intersecting and sorting arc segments, which can get messy when the intersections are dense. The scanline methods on the same task page are much more stable, not necessarily slower or less accurate, and a lot cleaner, so consider using that if at all possible. --Ledrug (talk) 21:00, 5 March 2015 (UTC)

Fortunately, I am deal with numbers of circles typically in the single digits, sometimes in the tens of circles. Your geometric solution certainly seems more satisfying than the scanline methods. I do think you are right that the scanline method would be easier, but I also need to adapt the code to measure perimeter. Your geometric solution would seem to give that inherently, though getting it from the scanline method shouldnt be much more than counting transition from a box in the total area to one that isnt (and vice-versa), right?

I appreciate your fast response to my question. Thank you for your help!

To calculate the perimeter, your idea of tracking transitions between inside and outside should work, provided that you take into account the slopes of the circles at the scanline intersections (segment length ~ scanline spacing / sine of tangential line's angle). I don't know how well it converges, because circles can be a little funny at top and bottom (slope near zero, so 1/sin can get really big), but I think it's worth a try. --Ledrug (talk) 19:41, 6 March 2015 (UTC)