Thread Subject: circle intersection help

hi all,

   how can i estimate intersection area when four circle meet or intersect?
is there any way to find approx centre for the intersection area?
if someone send me the article for this plz..?


                                       thanks,
                                                      

                                                             bala

If your circles specified with coordinaties of center and radius:
x1 y1 r1
x2 y2 r2

Then there intersect if distance between centers:
d=sqrt((x1-x2)^2+(y1-y2)^2)<(r1+r2)

Intersection center:
xc=(x1+x2)/2
yc=(y1+y2)/2

Area of intersection can be calculated as sum of areas of two
segments:
http://en.wikipedia.org/wiki/Circular_segment

------------------------------------
Maxim Vedenev, Matlab freelancer
vedenev@ngs.ru
http://simulations.narod.ru/

vedenev <vedenev.maxim@gmail.com> wrote in message <63666cc4-6b50-4989-8605-3e0490d71b10@w34g2000yqm.googlegroups.com>...
> If your circles specified with coordinaties of center and radius:
> x1 y1 r1
> x2 y2 r2
>
> Then there intersect if distance between centers:
> d=sqrt((x1-x2)^2+(y1-y2)^2)<(r1+r2)
>
> Intersection center:
> xc=(x1+x2)/2
> yc=(y1+y2)/2
>
> Area of intersection can be calculated as sum of areas of two
> segments:
> http://en.wikipedia.org/wiki/Circular_segment
>
> ------------------------------------
> Maxim Vedenev, Matlab freelancer
> vedenev@ngs.ru
> http://simulations.narod.ru/

hi vedenev,

thanks for reply.....i hav gone through the artice wat if four circle intersect?how i can find center of intersection area?.....

intersection center for two circle is
xc=(x1+x2)/2;
yc=(y1+y2)/2;
how?thanks for u'r reply
bala

"bala " <b.ece87@GMAIL.COM> wrote in message <go5moa$2e2$1@fred.mathworks.com>...
> hi all,
>
> how can i estimate intersection area when four circle meet or intersect?
> is there any way to find approx centre for the intersection area?
> if someone send me the article for this plz..?
>

Four circles? Are the radii of the circles known?
If not, then you cannot make any statement at
all about area of intersection. Are the radii all
the same values?

There will probably be no unique point of
intersection of all 4 circles. You can estimate
that point easily enough though, but I would
need to know the answers to the questions
above first.

The area of intersection will be more difficult
to quantify. Again, the radii MUST be known.

One could write a code to approximate each circle
by a polygon with many edges. Then find the
intersection of the first two such circles, as a
second polygon. Intersect that with the third,
and repeat with the fourth circle. This is fine, as
long as there is any finite overall intersection.

However, the probability is reasonable that the
intersection of 4 circles is the null set.

John

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <go60fh$d9g$1@fred.mathworks.com>...
> "bala " <b.ece87@GMAIL.COM> wrote in message <go5moa$2e2$1@fred.mathworks.com>...
> > hi all,
> >
> > how can i estimate intersection area when four circle meet or intersect?
> > is there any way to find approx centre for the intersection area?
> > if someone send me the article for this plz..?
> >
>
> Four circles? Are the radii of the circles known?
> If not, then you cannot make any statement at
> all about area of intersection. Are the radii all
> the same values?
>
> There will probably be no unique point of
> intersection of all 4 circles. You can estimate
> that point easily enough though, but I would
> need to know the answers to the questions
> above first.
>
> The area of intersection will be more difficult
> to quantify. Again, the radii MUST be known.
>
> One could write a code to approximate each circle
> by a polygon with many edges. Then find the
> intersection of the first two such circles, as a
> second polygon. Intersect that with the third,
> and repeat with the fourth circle. This is fine, as
> long as there is any finite overall intersection.
>
> However, the probability is reasonable that the
> intersection of 4 circles is the null set.
>
> John

yes,four circles n radii is known.....all are different radii also......can u tell me the algorithm for it......i must find center for the intersection area also..........i hav an image to show the intersection area made by four circle but i don know how to post it.....recommend any site to post pic for view......

"bala"
> i hav an image to show the intersection area made by four circle but i don know how to post it... recommend any site to post pic for view...

one of the many possibilities

http://picasaweb.google.com

us

"bala " <b.ece87@GMAIL.COM> wrote in message <go61sh$gnh$1@fred.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in message <go60fh$d9g$1@fred.mathworks.com>...
> > "bala " <b.ece87@GMAIL.COM> wrote in message <go5moa$2e2$1@fred.mathworks.com>...
> > > hi all,
> > >
> > > how can i estimate intersection area when four circle meet or intersect?
> > > is there any way to find approx centre for the intersection area?
> > > if someone send me the article for this plz..?
> > >
> >
> > Four circles? Are the radii of the circles known?
> > If not, then you cannot make any statement at
> > all about area of intersection. Are the radii all
> > the same values?
> >
> > There will probably be no unique point of
> > intersection of all 4 circles. You can estimate
> > that point easily enough though, but I would
> > need to know the answers to the questions
> > above first.
> >
> > The area of intersection will be more difficult
> > to quantify. Again, the radii MUST be known.
> >
> > One could write a code to approximate each circle
> > by a polygon with many edges. Then find the
> > intersection of the first two such circles, as a
> > second polygon. Intersect that with the third,
> > and repeat with the fourth circle. This is fine, as
> > long as there is any finite overall intersection.
> >
> > However, the probability is reasonable that the
> > intersection of 4 circles is the null set.
> >
> > John
>
> yes,four circles n radii is known.....all are different radii also......can u tell me the algorithm for it......i must find center for the intersection area also..........i hav an image to show the intersection area made by four circle but i don know how to post it.....recommend any site to post pic for view......

Ok, if the radii are known, then just do this. We
know the equations of each circle.

(x - x1)^2 + (y-y1)^2 = R1^2
(x - x2)^2 + (y-y2)^2 = R2^2
(x - x3)^2 + (y-y3)^2 = R3^2
(x - x4)^2 + (y-y4)^2 = R4^2

Subtract one from the rest. Thus

2*(x2 - x1)*x + 2*(y2 - y1)*y = R2^2 - R1^2 + x1^2 - x2^2
2*(x3 - x1)*x + 2*(y3 - y1)*y = R3^2 - R1^2 + x1^2 - x3^2
2*(x4 - x1)*x + 2*(y4 - y1)*y = R4^2 - R1^2 + x1^2 - x4^2

This is a linear system of 3 equations in the two
unknowns (x,y). Solve using backslash.

A = 2*[(x2 - x1),(y2 - y1);(x3 - x1),(y3 - y1);(x4 - x1),(y4 - y1)];
rhs = [R2^2 - R1^2 + x1^2 - x2^2; ...
         R3^2 - R1^2 + x1^2 - x3^2; ...
         R4^2 - R1^2 + x1^2 - x4^2];

xy = A\rhs

This is an estimate of the center coordinates.

HTH,
John

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <go6369$do2$1@fred.mathworks.com>...

> Ok, if the radii are known, then just do this. We
> know the equations of each circle.
>
> (x - x1)^2 + (y-y1)^2 = R1^2
> (x - x2)^2 + (y-y2)^2 = R2^2
> (x - x3)^2 + (y-y3)^2 = R3^2
> (x - x4)^2 + (y-y4)^2 = R4^2
>
> Subtract one from the rest. Thus
>
> 2*(x2 - x1)*x + 2*(y2 - y1)*y = R2^2 - R1^2 + x1^2 - x2^2
> 2*(x3 - x1)*x + 2*(y3 - y1)*y = R3^2 - R1^2 + x1^2 - x3^2
> 2*(x4 - x1)*x + 2*(y4 - y1)*y = R4^2 - R1^2 + x1^2 - x4^2
>
> This is a linear system of 3 equations in the two
> unknowns (x,y). Solve using backslash.
>
> A = 2*[(x2 - x1),(y2 - y1);(x3 - x1),(y3 - y1);(x4 - x1),(y4 - y1)];
> rhs = [R2^2 - R1^2 + x1^2 - x2^2; ...
> R3^2 - R1^2 + x1^2 - x3^2; ...
> R4^2 - R1^2 + x1^2 - x4^2];

Sorry. I left out one part of this, obviously
as an exercise for the student.

rhs = [R2^2 - R1^2 + x1^2 - x2^2 + y1^2 - y2^2; ...
         R3^2 - R1^2 + x1^2 - x3^2 + y1^2 - y3^2; ...
         R4^2 - R1^2 + x1^2 - x4^2 + y1^2 - y4^2];

John

"us " <us@neurol.unizh.ch> wrote in message <go629m$dum$1@fred.mathworks.com>...
> "bala"
> > i hav an image to show the intersection area made by four circle but i don know how to post it... recommend any site to post pic for view...
>
> one of the many possibilities
>
> http://picasaweb.google.com
>
> us


http://picasaweb.google.com/lh/photo/xQ70r3BK0FkzA7okcheNDw?authkey=_sKc4mJ_WLk&feat=directlink

this is link....u can see it
thanks for reply
i trying wat u hav given.......i cannot understand the method or principle behind it......
would u explain it to me or any article which explain about it....

thanks,

bala

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <go64f1$95b$1@fred.mathworks.com>...

Note: there is no assurance that the point
found will even be inside all the circles.

John


function [x0,y0] = circleintersect(X,Y,R)
% circleintersect: find the best point of intersection of 3 or more circles in the plane
% usage: [x0,y0] = circleintersect(X,Y,R)
%
% X,Y,R are all vectors, listing the centers
% and radii of each circle. All must be the
% same size arrays. There must be at least 3
% circles supplied.
%
% (x0,y0) forms the best estimate of the point
% of intersection.
%
% Example:
% X = rand(4,1);
% Y = rand(4,1);
% R = ones(4,1)*.5;
% [x0,y0] = circleintersect(X,Y,R)
%
% x0 =
% 0.23423
% y0 =
% 0.55481
%
% See also:
%
% Author: John D'Errico
% e-mail: woodchips@rochester.rr.com
% Release: 1.0
% Release date: 2/26/09

if nargin~= 3
  error('You must supply X, Y, R as separate vectors')
end

X = X(:);
Y = Y(:);
R = R(:);

n = length(X);
if (n ~= length(Y)) || (n ~= length(R))
  error('X, Y, R must all have the same number of elements')
end

if n < 3
  error('Must have at least 3 circles to find the overall intersection')
end

% time to do some actual work.
% Pick one circle, subtract the equation
% of that circle from the rest. This will
% be a linear system in the intersection
% point coordinates. When n > 3, the result
% is not unique, depending on which circle
% you choose to subtract from the remainder.

% preallocate A and rhs so as not to grow
% them in the loop.
A = zeros((n-2)*(n-1),2);
rhs = zeros((n-2)*(n-1),1);

% loop over the circle to use as the
% reference. This makes the solution unique,
% thus finding the best overall point of near
% intersection.
k = 1:(n-1);
for i = 1:n
  % the others are...
  j = setdiff(1:n,i);
  
  % build up the system of equations
  A(k,:) = 2*[X(i) - X(j),Y(i) - Y(j)];

  % and the right hand sides. Be careful here.
  % While I could have just squared these
  % elements, this can result in numerical
  % problems. Numerically more stable is to
  % do it this way, using the identity
  % A^2 - B^2 = (A-B)*(A+B)
  Xsq = (X(i) - X(j)).*(X(i) + X(j));
  Ysq = (Y(i) - Y(j)).*(Y(i) + Y(j));
  Rsq = (R(j) - R(i)).*(R(j) + R(i));
  rhs(k) = Rsq + Xsq + Ysq;
  
  % increment k until the last time through
  if i < n
    k = k + (n-1);
  end
end

% solve. backslask is best.
xy0 = A\rhs;
x0 = xy0(1);
y0 = xy0(2);

% plot the circles and the point found
 t = linspace(0,2*pi)';
 figure
 for i = 1:n
   plot(X(i) + R(i)*cos(t),Y(i) + R(i)*sin(t),'-')
   hold on
 end
 plot(x0,y0,'rx')
 hold off

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <go67dn$sr8$1@fred.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in message <go64f1$95b$1@fred.mathworks.com>...
>
> Note: there is no assurance that the point
> found will even be inside all the circles.
>
> John

thanks for u'r code......but,the point must be inside intersection area.........its like that u find intersection area n estimate center point of intersection area u can approx the intersect area as any known figure say triangle or square

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <go67dn$sr8$1@fred.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in message <go64f1$95b$1@fred.mathworks.com>...
>
> Note: there is no assurance that the point
> found will even be inside all the circles.
>
> John
>
>
hi all of u,

http://www.mathworks.com/matlabcentral/fileexchange/5313

see this file it calculates intersection area but i want to find center of the intersection area..........i saw the code but i can't understand anything....if anybody explain the code it would be grateful

to calculate intersection points of circle matlab has a command CIRCCIRC which give u point of intersection........but i saw the code but i can't understand the mathematics behind it.....plz explain it....plz....it's urgent

               thanks,

                                      bala

"bala " <b.ece87@GMAIL.COM> wrote in message <go5moa$2e2$1@fred.mathworks.com>...
> hi all,
> how can i estimate intersection area when four circle meet or intersect?
> is there any way to find approx centre for the intersection area?
> if someone send me the article for this plz..?
> thanks, bala

  When you say the "intersection area when four circles meet", do you mean the set of all points lying in the disk interior of each of the circles? In that case your intersection region is bound to be convex. For each possible pair of circles there are two possible points of intersection. Your convex region will therefore have a boundary consisting of anywhere from one to six circular conjoined arc segments delineated by some of these circle intersection points.

  To find the area of this region, you can calculate it in terms of the algebraic sum of the areas of each of the arc segments projected onto a common point within the region. There is a formula, which I could work out for you if this approach interests you, which expresses each of these projected areas in terms of a simple expression involving the coordinates of the circle intersection points on the region boundary, the circular centers, and the areas of the corresponding separate circular sectors. Actually I believe this common point need not lie within the region but could simply be, say, the coordinate origin.

  My intuition tells me that an analogous formula can also be devised for calculating the centroid of this intersection region. The centroid of a convex region will always lie somewhere within its interior and it seems like a natural "center".

  The point of all this is, does this method seem useful to you? In particular, will a centroid qualify for your "approx centre"? It will take a bit of head-scratching to work out the details or, better still, perhaps it is already worked out somewhere in the literature. Undoubtedly many people have encountered this particular problem.

Roger Stafford

hi roger,

thanks for u'r reply....plz help me out...i'm bit dull in this topic..

>When you say the "intersection area when four circles meet", do you mean the >set of all points lying in the disk interior of each of the circles?

i don't know wat set of points u r referring....i hav centres n radius of four circle only....isn't enough to calculate intersection area?

>The point of all this is, does this method seem useful to you? In particular, will a >centroid qualify for your "approx centre"?

yes,i hav sent a file exchange link which calculates only the intersection area but i need to find the centroid of intersection area......i don't understand that code which has written there.....plz help out

the method u talked is based on this:it would be grateful to hav that method
d = sqrt((x2-x1)^2+(y2-y1)^2); % Distance between centers
s = (r1+r2+d)/2; % Half the sum of the sides of the triangle
ta = sqrt(s*(s-r1)*(s-r2)*(s-d)); % Triangle's area
a1 = acos((d^2+r1^2-r2^2)/(2*d*r1)); % Angle at first center
a2 = acos((d^2+r2^2-r1^2)/(2*d*r2)); % Angle at second center
area = r1^2*a1+r2^2*a2-2*ta; % Area of intersection

"bala " <b.ece87@GMAIL.COM> wrote in message <go6qpd$gah$1@fred.mathworks.com>...
> ......
> the method u talked is based on this:it would be grateful to hav that method
> d = sqrt((x2-x1)^2+(y2-y1)^2); % Distance between centers
> s = (r1+r2+d)/2; % Half the sum of the sides of the triangle
> ta = sqrt(s*(s-r1)*(s-r2)*(s-d)); % Triangle's area
> a1 = acos((d^2+r1^2-r2^2)/(2*d*r1)); % Angle at first center
> a2 = acos((d^2+r2^2-r1^2)/(2*d*r2)); % Angle at second center
> area = r1^2*a1+r2^2*a2-2*ta; % Area of intersection

  Bala, those six lines of code you described above are for computing the intersection area of just two circles. What I had in mind is rather different: the area projected onto an arbitrary point from a circular arc, not necessarily onto its center. Imagine first drawing two lines from the endpoints of a circular arc down to that arc's center. Then move the center point off to some arbitrary location while dragging the two lines along with it. The question is, by now much has the projected area changed? It's a simple calculation involving the distance between the arc endpoints and the distance moved orthogonally to the line between them. Using such a calculation one can combine these to compute the total area of the convex region of intersection of all four circles, or for that matter, of arbitrarily many circular disks.

  I think this can also be modified to compute the region's centroid. It should be quite similar to the well-known method of computing the centroid of the interior of a polygon in terms of triangular areas projected onto some arbitrary point for each segment of the polygon. You can think of your region's boundary as being a kind of circular arc segment "polygon".

  By the way, if the coordinates of the centers are made available, there is a more robust way of calculating the area of the two-circle intersection you described which uses 'atan2' instead of 'acos'. The latter runs into accuracy difficulties for angles that are near zero or pi.

  I will try to work out the centroid details for you. Warning: at my age my thought processes have slowed down quite a bit so it may take a while.

Roger Stafford

"bala " <b.ece87@GMAIL.COM> wrote in message <go6j5m$2at$1@fred.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in message <go67dn$sr8$1@fred.mathworks.com>...
> > "John D'Errico" <woodchips@rochester.rr.com> wrote in message <go64f1$95b$1@fred.mathworks.com>...
> >
> > Note: there is no assurance that the point
> > found will even be inside all the circles.
> >
> > John
>
> thanks for u'r code......but,the point must be inside intersection area.........its like that u find intersection area n estimate center point of intersection area u can approx the intersect area as any known figure say triangle or square

As I have already stated and you must realize,
it is entirely possible that the intersection area
is the null set.

John

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <go6tn6$42k$1@fred.mathworks.com>...
> "bala " <b.ece87@GMAIL.COM> wrote in message <go6qpd$gah$1@fred.mathworks.com>...
> > ......
> > the method u talked is based on this:it would be grateful to hav that method
> > d = sqrt((x2-x1)^2+(y2-y1)^2); % Distance between centers
> > s = (r1+r2+d)/2; % Half the sum of the sides of the triangle
> > ta = sqrt(s*(s-r1)*(s-r2)*(s-d)); % Triangle's area
> > a1 = acos((d^2+r1^2-r2^2)/(2*d*r1)); % Angle at first center
> > a2 = acos((d^2+r2^2-r1^2)/(2*d*r2)); % Angle at second center
> > area = r1^2*a1+r2^2*a2-2*ta; % Area of intersection
>
> Bala, those six lines of code you described above are for computing the intersection area of just two circles. What I had in mind is rather different: the area projected onto an arbitrary point from a circular arc, not necessarily onto its center. Imagine first drawing two lines from the endpoints of a circular arc down to that arc's center. Then move the center point off to some arbitrary location while dragging the two lines along with it. The question is, by now much has the projected area changed? It's a simple calculation involving the distance between the arc endpoints and the distance moved orthogonally to the line between them. Using such a calculation one can combine these to compute the total area of the convex region of intersection of all four circles, or for that matter, of arbitrarily many circular disks.
>
> I think this can also be modified to compute the region's centroid. It should be quite similar to the well-known method of computing the centroid of the interior of a polygon in terms of triangular areas projected onto some arbitrary point for each segment of the polygon. You can think of your region's boundary as being a kind of circular arc segment "polygon".
>
> By the way, if the coordinates of the centers are made available, there is a more robust way of calculating the area of the two-circle intersection you described which uses 'atan2' instead of 'acos'. The latter runs into accuracy difficulties for angles that are near zero or pi.
>
> I will try to work out the centroid details for you. Warning: at my age my thought processes have slowed down quite a bit so it may take a while.
>
> Roger Stafford

Roger, you too must realize that there is very
possibly no common intersection of all 4 circles.
Computation of the centroid will be more difficult
then.

John

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <go6uqp$ish$1@fred.mathworks.com>...
> "bala " <b.ece87@GMAIL.COM> wrote in message
> >
> > thanks for u'r code......but,the point must be inside intersection area.........its like that u find intersection area n estimate center point of intersection area u can approx the intersect area as any known figure say triangle or square
>
> As I have already stated and you must realize,
> it is entirely possible that the intersection area
> is the null set.
>
> John

i can't understand why intersection area must be null set..........see the file exchange i hav referred.....from the code if u understand plz explain to me....i can't understand anything

hi roger,
         thanks man,those code which i wrote is based on this link
http://mathworld.wolfram.com/Circle-CircleIntersection.html


 Using such a calculation one can combine these to compute the total area of the convex region of intersection of all four circles, or for that matter, of arbitrarily many circular disks.

can u give code for u'r idea.....take u'r own time....don't rush....

    
> I think this can also be modified to compute the region's centroid. It should be quite similar to the well-known method of computing the centroid of the interior of a polygon in terms of triangular areas projected onto some arbitrary point for each segment of the polygon. You can think of your region's boundary as being a kind of circular arc segment "polygon".

if u find the code which i hav sent can be modified....plz explain the code i understand anything from it
                              
                           thanks,
                                                       bala

"bala " <b.ece87@GMAIL.COM> wrote in message <go6vmt$i4r$1@fred.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in message <go6uqp$ish$1@fred.mathworks.com>...
> > "bala " <b.ece87@GMAIL.COM> wrote in message
> > >
> > > thanks for u'r code......but,the point must be inside intersection area.........its like that u find intersection area n estimate center point of intersection area u can approx the intersect area as any known figure say triangle or square
> >
> > As I have already stated and you must realize,
> > it is entirely possible that the intersection area
> > is the null set.
> >
> > John
>
> i can't understand why intersection area must be null set..........see the file exchange i hav referred.....from the code if u understand plz explain to me....i can't understand anything

No. It is not that it MUST be the null set.

However, the probability is reasonably high
enough that it will be the null set. In fact,
if the 4 circles come at all close to an actual
point of intersection, then the probability
of a null intersection will be significant.

John

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <go70oo$73$1@fred.mathworks.com>...
> "bala " <b.ece87@GMAIL.COM> wrote in message <go6vmt$i4r$1@fred.mathworks.com>...
> > "John D'Errico" <woodchips@rochester.rr.com> wrote in message <go6uqp$ish$1@fred.mathworks.com>...
> > > "bala " <b.ece87@GMAIL.COM> wrote in message
> > > >
> > > > thanks for u'r code......but,the point must be inside intersection area.........its like that u find intersection area n estimate center point of intersection area u can approx the intersect area as any known figure say triangle or square
> > >
> > > As I have already stated and you must realize,
> > > it is entirely possible that the intersection area
> > > is the null set.
> > >
> > > John
> >
> > i can't understand why intersection area must be null set..........see the file exchange i hav referred.....from the code if u understand plz explain to me....i can't understand anything
>
> No. It is not that it MUST be the null set.
>
> However, the probability is reasonably high
> enough that it will be the null set. In fact,
> if the 4 circles come at all close to an actual
> point of intersection, then the probability
> of a null intersection will be significant.
>
> Jhon

http://www.mathworks.com/matlabcentral/fileexchange/5313

did u check this link.....if u understand this plz explain to me......thanks for u'r time

                                thanks,
                                                    bala

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <go6uuh$qbj$1@fred.mathworks.com>...
> Roger, you too must realize that there is very
> possibly no common intersection of all 4 circles.
> Computation of the centroid will be more difficult
> then.
>
> John

  John, if my understanding of Bala's statement is correct, he isn't looking for a common intersection of the four circles, but rather the intersection of four disks, which is a different matter. This intersection set will be convex and bounded by a series of presumably no more than six circular arcs with varying radii and centers. From among the possible intersections of each pair of circles, those which are not on or inside both other circles can be eliminated, thereby arriving at the endpoints of the arc segments which form the region's boundary. The challenge is then to use these to compute the area contained within the region and the location of its centroid.

  I am certain that this area can be successfully computed in terms of the locations of the arc endpoints and centers of the arcs by a simple process involving signed areas of projections from the arcs to some common point (though admittedly I haven't written these out yet,) but a few hen-scratchings have also convinced me that the centroid computations of these projected areas should follow along rather similar lines.

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <go731p$9q3$1@fred.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in message <go6uuh$qbj$1@fred.mathworks.com>...
> > Roger, you too must realize that there is very
> > possibly no common intersection of all 4 circles.
> > Computation of the centroid will be more difficult
> > then.
> >
> > John
>
> John, if my understanding of Bala's statement is correct, he isn't looking for a common intersection of the four circles, but rather the intersection of four disks, which is a different matter.

Roger,

I completely disagree. My point is that the intersection
of two circular disks (if you wish to call it a disk, I care
not. It is what I meant anyway) will be defined by a
pair of circular arcs. If you will forgive me for doing so,
I'll call it a circugon, with two edges. A single circle, by
this naming convention is a circugon with only one
edge.

Now add a third circlular disk to that mix. Assuming that
the third circle has some intersection with the circugon
formed from circles 1 and 2, the result will be a new
circugon, with a smaller area of intersection. It will
now have either 2, 3, or 4 edges, each of which is a
circular arc.

Finally, intersect that with a 4th circular disk. This will
have a yet smaller area, and be defined by somewhere
between 2 and 6 edges, if it is not the null set. The
problem arises when the 4 circles are arranged so that
their circumferences come close to intersecting in a
single point. Is this a likely event? YES!

Typically these applications come from triangulation.
Imagine a set of cell towers arranged on a nice
regular lattice. Now, plunk down some point inside
that grid, and measure the distance from the point to
each close cell tower. The 4 towers that are closest
to our point of interest will be the four nearest lattice
points in the 2-d lattice.

Assume that each distance measurement is made with
some noise. There may even be some noise in our
knowledge of the tower locations.

My point is, the intersection circugon will be very
small in these circumstances, and

As an example, consider the case of four circles with
centers [0 0], [1 0], [0 1], [1 1]. Assume each circle
has radius sqrt(2)/2 plus some small noise component.

Ask yourself what the probability is that the intersection
of these four disks is the null set? It is significant.
Certainly large enough that you must consider what to
do when it is null.

John

hi john,

    yes,i am trying to stimulate that kind of thing in matlab.....
i.e i hav 4 tower and a receiver....i know center of tower and distance to receiver
to find receiver location i need to draw circles with distance between them as radius
and find the intersection area....identically it must be a point but it would be...it would be in some intersecting area of circle n i hav taken centroid of these intersection as my location of receiver........if u understand the code which the link i send u plz explain it to me......plz see to it

"bala " <b.ece87@GMAIL.COM> wrote in message <go7bdu$esi$1@fred.mathworks.com>...
> hi john,
>
> yes,i am trying to stimulate that kind of thing in matlab.....
> i.e i hav 4 tower and a receiver....i know center of tower and distance to receiver
> to find receiver location i need to draw circles with distance between them as radius
> and find the intersection area....identically it must be a point but it would be...it would be in some intersecting area of circle n i hav taken centroid of these intersection as my location of receiver........if u understand the code which the link i send u plz explain it to me......plz see to it

As I suggested, this problem comes from
triangulation. As such, there may be as large
as a 50% probability of a null set intersection
of 4 such circles. (This is only a wild guess,
but it is likely not far off.) You need to deal
with the problem of a null intersection.

Or, not. After all, this is your homework, not
mine.

John

hi john,
    
    thanks for u'r replies man.......if i know mathamatical background for it.....i would hav done myself....if u come across any theory related to find centroid of polygan or centroid of irregular area give me from that i will develop my code

anyway thanks for spending u'r time on this problem
        
bala

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <go78e9$n56$1@fred.mathworks.com>...
> I completely disagree. ......
> ......
> The problem arises when the 4 circles are arranged so that
> their circumferences come close to intersecting in a
> single point. Is this a likely event? YES!
> .......

  "Circugon"! I like that word. I'll have to find an excuse to use it someday in the future.

  I have read your article carefully, John, and find myself in agreement with it right up to, but not including, the point where you say, "The problem arises when the 4 circles are arranged so that their circumferences come close to intersecting in a single point. Is this a likely event? YES!"

  It is the "YES" answer I don't necessarily agree with. Whether that event is likely or unlikely depends on the kind of problem that leads to the four circles. There could well be a situation in which such an event would be decidedly unlikely. Given the appropriate circles this does in fact constitute a well-defined problem. The intersection region can easily have a definite area and centroid.

  In any event, in the algorithm I envision, it would soon become evident that no circle intersection point between any pair of circles lies inside both other circles (aside from possible noise,) and the algorithm could then stop and complain "tilt" or "bad input" if a valid region were expected. In your example with all four radii equal to or even in the near neighborhood of 1/sqrt(2), that would be a good point to stop. But what if all the radii were equal to 1? Then you would have a very well-defined region with a definite non-zero area and centroid (in this case at (.5,.5). Who is to say that this couldn't be a real problem with solution sorely needed in some conceivable situation?

Roger Stafford

hi roger,

> > I think this can also be modified to compute the region's centroid. It should be >>quite similar to the well-known method of computing the centroid of the interior of >>a polygon in terms of triangular areas projected onto some arbitrary point for each >>segment of the polygon. You can think of your region's boundary as being a kind >>of circular arc segment "polygon"

how to find centroid of polygon?give some mathamatical formulas.......how could get the region boundry

thanks
bala