areas of intersecting circles
stev...@gmail.com
I have to work with 2d areas created by intersection of circular
regions. I was wondering if there is any theory on this already and
any results I could use.
To be more explicit, I am given two sets of circles with known centers
and radii. A valid area is defined as the points that find themselves
within all the circular regions in the first set and in none of the
second set. An example is the black delimited area in figure:
http://temporaryfilesharing.googlegroups.com/web/circles.jpg
where the darker colored circles define the first set and the ligther
colored ones the second set. I am interested in knowing if such an
area exists; if so out of how many clusters it is made; what are the
sizes of these clusters; etc.
Thank you,
Steve
Robert Israel
Let the circles have centres c_i and radii r_i, i=1..n, where the first
set is i=1..m and the second set i=m+1..n. I'll assume for simplicity that
none of the circles coincide. A point p on circle #j is on the boundary of
your region if dist(p, c_i) < r_i for j <> i <= m and dist(p,c_i) > r_i for j
<> i > m. For each j this determines a finite set of arcs on circle #j, and
these arcs will join up to produce the boundary of your region. The areas can
easily be computed, e.g. using the line integral of x dy around the boundary
(counterclockwise).
--
Robert Israel isr...@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
stev...@gmail.com
Thank you for your answer! The approach you propose is very similar to
what I was actually using. I found it easier to determine first all
the intersection points between all pairs of circles and then remove
the ones that are not part of the group i=1..m (in your notation).
second step was separating the nodes in clusters by simply moving
along the arcs. For the area I was not performing integration per se
but developed a recursive approach to compute the intersection area of
n circles based on the intersection areas of pairs of n-1 circles.
This approach is fine for one-shot analysis, but I asked my question
from a slightly different perspective. I was interested if there is
any theory that can say something about these areas and number of
cluster before hand (or any of their characteristics), without having
to go through this procedure for every topology.
The reason for which I asked is that the centers of the circles are
fixed, but the radii of the circles can vary (I am modeling wireless
communication algorithms with variable transmission range). One of the
problems I am facing is to compute what is the maximum area and the
maximum number of clusters I can expect when r_i are varied. Finding
these numbers by performing optimization using the procedure described
above is very costly. I was wondering if any properties of the
intersection areas can be deducted without having to go through the
procedure itself.
Kind regards,
Steve
On Feb 18, 3:30 am, Robert Israel
<isr...@math.MyUniversitysInitials.ca> wrote:
> University of British Columbia Vancouver, BC, Canada- Hide quoted text -
>
> - Show quoted text -
Ian Parker
wrote:
>
> Let the circles have centres c_i and radii r_i, i=1..n, where the first
> set is i=1..m and the second set i=m+1..n. I'll assume for simplicity that
> none of the circles coincide. A point p on circle #j is on the boundary of
> your region if dist(p, c_i) < r_i for j <> i <= m and dist(p,c_i) > r_i for j
> <> i > m. For each j this determines a finite set of arcs on circle #j, and
> these arcs will join up to produce the boundary of your region. The areas can
> easily be computed, e.g. using the line integral of x dy around the boundary
> (counterclockwise).
> --
Area of segment of circle of radius r and angle TH = r^2.TH/2 if TH is
in radians.
Area of triangle = r^2 Sin(TH/2)Cos(TH/2) (twice0.5*base*height)= rSin
(TH)/2 (Compound angles)
Therefore area under chord = r^2(TH - Sin(TH))/2
If we have two intersecting circles then area of intersection =
(r1^2(TH1 - Sin(TH1))+r2^2(TH2 - Sin(TH2)))/2 is the area you want.
We know r1.Sin(TH1/2) = r2.Sin(TH2/2) Since the chord for both circles
is the same length.
- Ian Parker
Ian Parker
Mariano Suárez-Alvarez
But I think the OP is interested in having many circles.
Your approach would be incredibly complicated...
-- m
Ian Parker
<mariano.suarezalva...@gmail.com> wrote:
>
> But I think the OP is interested in having many circles.
> Your approach would be incredibly complicated...
>
we can calculate theta as follows.
We have a triangle sides r1, r2, X where X is the distance between the
centers.
We know a^2 = b^2 + c^2 -2bcCos A
This gives A as Cos^-1((r1^2 + X^2- r2^2)/2Xr1)
Similarly for B
This is an extremely simple computation. I can't see how you can get
it any simpler.
Area = 0.5(r2^2(A-Sin(A))+r1^2(B-Sin(B))
A program to calculate it can be written in a very few lines.
- Ian Parker
Mariano Suárez-Alvarez
Did you not read the post you were replying to?
The OP is interested in the situation inwhich there are
*many* circles! It is quite clear that for two your
procedure works nicely. Now, can you give us the
formulas for the area of the intersection of 25 circles?
-- m
Ian Parker
>
> - Show quoted text -
Sorry. I don't think there is a deep theory of this. It is a question
of taking each problem as it comes. The algorithmic proceedure I would
use is the following.
1) Find circles which are completely inside each other.
Defined as being when d(O1 - O2) < |r1-r2|. You take the smaller
circle if in first group, the larger circle if in second. If a first
is within a second the problem is impossible.
2) Find d(nm)in all the first group. d(mn) = d(On - Om)if rn+rm<d(mn)
it is impossible (they never intersect)
3) Take smallest circle of first group. Find all points of
intersection. Find common arc. You will now have reduced the problem
to just 3 circles (first group). The smallest circle, and the circles
that cross at the two ends of the common arc. This will give you a
figure to integrate.
4) You then need to check the points of intersection of your second
set of circles to see whether the area defined by the 3 arcs is
totally outside, totally inside of partly outside partly inside the
second set of circles.
Proving impossibility is quite efficient computationally. The hardest
case is when your 3 arcs are partly inside and partly outside the
second set of circles.
- Ian Parker
Mariano Suárez-Alvarez
But this approach is in no way related to the
approach you used for the case of two circles,
and in fact is based on exactly the same idea
than Robert's, but made more complicated.
I can't see what motivated your "I think there
is an even simpler way of looking at this"
in response to Robert :-)
-- m