[Tutor] Tutor Digest, Vol 72, Issue 3

Carnell, James E jecarnell at saintfrancis.com
Mon Feb 1 21:53:10 CET 2010



Let there be 'n' circles (upper bound on n = 10**6) each of radius '1'.
We enter their co-ordinates which are floating points and lies between
(-1000, 1000). I need to find area of the resulting figure formed by
intersection of circles. I came across these links :
http://stackoverflow.com/questions/1667310/combined-area-of-overlapping-
circles
http://answers.google.com/answers/threadview?id=480288
http://mathworld.wolfram.com/Circle-CircleIntersection.html
But of no avail. Can anyone point me towards right direction? :(

~Shashwat Anand
===========================
This is probably spam, but...

1) My bad answer is to render them in pygame et al and do edge
detection, if overlap color pixels a different color then count pixels.
Probably would have to do in parts since the area is so big. Last I knew
edge detection for circles sucks... 

2) My trying to be good answer but is untested and probably doesn't work
(ugh) is to use an FFT on the x and y axis. Numpy  has an FFT. Since
they all have the same circumference then maybe you can just scan to the
left and right on the X axis and on the Y axis compute the difference
and the resulting intersection. Put the intersection in a lookup chart
under a key value for the differences (I think you can sum the x and y
difference maybe not to have less keys). At some point you could
probably just interpolate your lookup chart to save time unless you need
it exact as possible. 

Is this some kind of vision algorithm?

Sincerely,

Bad answer man


More information about the Tutor mailing list