Shashwat Anand wrote:
I want to calculate areas.
like for two circles (0, 0) and (0, 1) : the output is '1.228370'
similarly my aim is to take 'n' co-ordinates, all of radius '1' and
calculate the area common to all.
The best I got was monte-carlo methods which is inefficient. Is there any
other approach possible.
You start with a list of circles, each having center (a,b), and radius
(r). As you stated the problem, r is always 1, but I'll keep the
algorithm general.
This is untested, and probably contains typos, at least.
I would do it with successively smaller squares. A square can be
described using center coordinates (x,y) , and length (s) of a side.
Each square can have three states: not included, partially included,
and fully included.
You build a list of squares, starting with one, the bounding square for
the first circle.
For each square in the list, you go through all the circles (each with
center a,b, and radius r), and for each circle decide if the square is
entirely within the circle, or partially. If it's fully included in all
of them, you add its area to the the accumulator, and drop it from your
list. if it's not included at all in one of them, you just drop it
from the list. (Note, be careful about modifying a list you're
iterating through -- make a copy)
After a pass through the list, the accumulator is a lower-bound for the
area, and the accumulator plus the areas of all the squares is an upper
bound. If these are close enough together, you terminate.
Otherwise you take the remaining squares in the list, split each into
four pieces, and end up with a list 4 times as long. And repeat the
loop, checking each square against each circle.
The only remaining question is how you decide for a given circle and a
given square which of the three states it's in. And it turns out you
can be pretty approximate in this, and it'll still converge. So you can
take a distance between (a,b) and (x,y), and compare it to r-s/2 and to
r+(s*0.707106781187). If it's greater than r+s*0.707106781187, no
intersection. If it's less than r-s/2, then the square's entirely inside.
Note that I used 0.707106781187 above, but you'd actually use sqr(0.5)
to whatever precision you needed. And if it's convenient to round it,
round it upwards; again it won't affect the result. I doubt if it
would matter in Python code, but you could even do the whole thing in
integers (avoiding the sqrt for distance calc), if you were careful
about the bounding formulas. That's premature optimization, however.
HTH,
DaveA
--
http://mail.python.org/mailman/listinfo/python-list
