I'm working on some data that'll require a geometry code. Essentially, the data is composed of a number of randomly sized circles on a flat surface. I have to see how much overlap is there and the thickness of overlap:

1. Does anyone know a code (or suggestions on how to write a code) to find the total overlapping areas of a number of randomly sized circles? 

2. Of equal importance, I also need to know how many overlap regions overlap once, twice, thrice,... nXs (where n is the total number of circles) and the corresponding areas of overlap once, twice, thrice, nXs. 

Any help will be much appreciated!

In what form is the input? That is, how are the circles specified? For example, are you starting from some kind of image?

Unless your circles are somewhat transparent, it could be difficult to
determine overlap.  For example, if two circles are 95% overlapped,
they may not look different in shape than a single circle, so you'd
have to go by the intensity within the shape.
Post your image to http://drop.io so we can see it.

"David Young" <d.s.young.notthisbit@sussex.ac.uk> wrote in message <hq4vfs$nbd$1@fred.mathworks.com>...
> In what form is the input? That is, how are the circles specified? For example, are you starting from some kind of image?

It's not some kind of image. Rather, it's xy-coordinates and radiis of thousands of randomly sized and distributed circles on a flat plane. In other words, my inputs are three arrays:

x-coordinate array
y-coordinate array
radius array

ImageAnalyst <imageanalyst@mailinator.com> wrote in message <07e27f97-2a22-442f-a4a4-6001405bba3c@g11g2000yqe.googlegroups.com>...
> Unless your circles are somewhat transparent, it could be difficult to
> determine overlap.  For example, if two circles are 95% overlapped,
> they may not look different in shape than a single circle, so you'd
> have to go by the intensity within the shape.
> Post your image to http://drop.io so we can see it.

No, it's not an image. I have 3 arrays: x-coordinates, y-coordinates, and radii. Those are the inputs.

Also can anyone tell me how to keep everything under one thread? I think I just started a New Message here. That's annoying.

"Shen " <shenge86@yahoo.com> wrote in message <hq53l2$5mj$1@fred.mathworks.com>...
> "David Young" <d.s.young.notthisbit@sussex.ac.uk> wrote in message <hq4vfs$nbd$1@fred.mathworks.com>...
> > In what form is the input? That is, how are the circles specified? For example, are you starting from some kind of image?
> 
> It's not some kind of image. Rather, it's xy-coordinates and radiis of thousands of randomly sized and distributed circles on a flat plane. In other words, my inputs are three arrays:
> 
> x-coordinate array
> y-coordinate array
> radius array

This will be quite computationally intensive to do for
many thousands of circles, especially if you will
compute the area of intersections of multiple circles
at once.

It is easy to specify a problem that looks trivial, yet will
take serious effort to solve, if it is even possible.

John

"Shen " <shenge86@yahoo.com> wrote in message <hq4sv9$er3$1@fred.mathworks.com>...
> I'm working on some data that'll require a geometry code. Essentially, the data is composed of a number of randomly sized circles on a flat surface. I have to see how much overlap is there and the thickness of overlap:
> 
> 1. Does anyone know a code (or suggestions on how to write a code) to find the total overlapping areas of a number of randomly sized circles? 
> 
> 2. Of equal importance, I also need to know how many overlap regions overlap once, twice, thrice,... nXs (where n is the total number of circles) and the corresponding areas of overlap once, twice, thrice, nXs. 
> 
> Any help will be much appreciated!
--------------------------------
  This won't do you much good by itself, but just to get you started in the right direction, here is a malab procedure for determining the overlap area of two circles.  Let their radii be r1 and r2, and their centers be spaced a distance d apart.  Then matlab can compute the area of their overlap as follows:

 t = sqrt((d+r1+r2)*(d+r1-r2)*(d+r2-r1)*(r1+r2-d)); % Twice quad. area
 a1 = atan2(t,d^2+r1^2-r2^2); % Half angle of r1-sector
 a2 = atan2(t,d^2-r1^2+r2^2); % Half angle of r2-sector
 overlaparea = a1*r1^2+a2*r2^2-t/2; % Sector areas minus quad. area

  The above is true provided that all factors in the t expression above are positive.  On the other hand, if r1+r2-d < 0, there is no overlap at all; if d+r1-r2 < 0, the overlap is the entire r1-circle, whose area is pi*r1^2; and finally if d+r2-r1 < 0, the overlap is the entire r2-circle with an area of pi*r2^2.

  As John has indicated, with a very large number of circles it looks as though you have posed a monumentally difficult problem.  Once you have located a single connected region which some subset of the circles all contain, I can conceive of an algorithm that works its way around the region's boundary calculating its area in terms of circular sectors and triangles as it goes.  However identifying such regions would be no small task.

Roger Stafford

A lot depends on the accuracy you need. If you want to get the maximum possible precision, then you will need to develop what Roger Stafford has given above - which looks to me like quite a big programming effort as well as requiring a lot of computational resources for many circles.

If an approximation would be sufficient, it might be worth thinking about another approach, which is in effect to synthesise the image you'd get if the circles were semi-transparent sheets laid above a light source. The synthesis is straightforward in principle: you initialise an array of zeros big enough to contain images of all the circles (with a suitable transformation from problem coordinates to array subscripts), and for each circle increment the elements of the array that fall within it. The analysis is simple too: the histogram of the array tells how many pixels fall within N circles. The problem would be to get the resolution right, trading off memory and time against accuracy.

Whether or not to explore such an approach depends on the details of the problem - experimentation might be needed.