Dear Lie Kong ,

The answer is based on the including - excluding principle.

You have 10 discs (Di, ri), i=1,2,...10, ri is the radius, that cover

partially the green region R.

Step1: Compute the following areas. (simple task)

(Di, ri) ∩ R = Ai, i=1,2,3,..10.

Step(2): Compute the areas (Di, ri) ∩ (Dj, rj) where i≠j.(simple task)

step(3): Add all answers in step(1) = ∑Ai = S₁

Step(4): Add all answers in step(2) = S₂

Finally, the coverage region (hidden by discs)

is equal to S₁ - S₂.

The seen part of the green region has the area

(area of R) - (S₁ - S₂).

Best regards

I would iterate an approximation:

-step1 fit the biggest disk possible in the hole

-step2 repeat: the next biggest disk possible in remaining hole

-etc

Doing this you get a lower bound of the surface of the hole.

You need to find an upper bound..

Upper bound (not necessarily tight).

-find the disks on the border of the region of interest.

-Identify closest neighbour disks in this set.

-one first approach

Get the center Cij of each segment Ci Cj, for any two pairs of disk centers, then rij= d(Ci, Cj) /2

Add the surface of all disks (Cij, rij)...

It should be an upper bound.

Any better?

Dear Renaud Di Francesco ,

The exact answer can be determined, see reply(1).

So, don't need any approximations!

Best regards

Dear Issam Kaddoura,

Thanks for you answer. However, the area to be obtained is the hollow region that excludes any part of the discs. How can we define the R mentioned in your answer.

Thank you.

Lie

Dear Renaud Di Francesco,

I suppose there could be an analytic solution for the problem since all the variables are given. Do you have any ideas?

Thank you.

Lie

Dear Lie Kong ,

R is the whole region, which is already defined by the given vertices.

Its area is an elementary problem.

So, the area of the green (seen hole) S = Area of R - (S1 - S2 ).

Best regards

Dear Lie Kong ,

R is the whole region, which is already defined by the given vertices.

Its area is an elementary problem.

So, the area of the green (seen hole) S = Area of R - (S1 - S2 ).

Best regards

Hi Issam,

Is the R refering to the polygon area? However, S2 contains part of the area excluding R. So the R- S1 + S2 =S+X. Where X might be the portion of discs intersecting area that lies out of the polygon. Do you think so?

Cheers,

Lie

Dear Lie Kong ,

I agree with your correction. I missed writing

in step (2): Compute the areas (Di, ri) ∩ (Dj, rj) ∩ R, where i≠j .

Best regards

Thank you Issam. Actually I tried to devide the polygon into several triangles by connecting an additional point on area S, and then used the including and excluding idea. However there will be too many cases with different triangle-circles positions, which makes the way very complicated.

I divided the polygon area into several triangles and calculated areas of these green arcs in each triangle. However, the various possibilities of triangle-discs comparative positions in the sub_sections make it very complicated. Any one have new ideas?

Dear Lie Kong ,

Let starts with only two discs and then you can apply the method for

any number of discs. It is direct and simple.

We have a polygon R.

Two intersecting discs D1 (r1 ) and D2 (r2)

Calculate the following:

1. D₁∩R = A₁

2. D₂∩R = A₂

3. D₁∩D₂∩R = B₁

Therefore the area of the seen part of R (Green hole)

= Area of (R)- Area(A₁)-Area(A₂)+Area(B₁).

Similarly, for the 10 discs D₁, D₂,...,D₁₀.

Best regards

Hi Issam,

Thank you for the discussion. The logic is quite straight forward. However, there will by many cases as list in the attached figures. I am confronted with troubles to identify each case in the codes.

Dear Lie Kong ,

I hope you find the following links are helpful:

(The last one contains an excellent interpretation.)

(1) mathworld.wolfram.com/Circle-CircleIntersection.html

(2) https://www.xarg.org/2016/07/calculate-the-intersection-area-of-two-circles/

(3) https://diego.assencio.com/?index=8d6ca3d82151bad815f78addf9b5c1c6

(4) https://www.engineeringtoolbox.com/area-intersecting-circles-d_1571.html

(5) https://onlinelibrary.wiley.com/doi/full/10.1002/wcm.2305

Best regards

Well, you have two ways to look at this:

-analytical mathematics

You assume you know all disks D, you know the space in which they are fitted S.

Then you know the surface of the space of interest S, you know the surface occupied by the disks of family D (you could do this by defining on your plane front and back: some disks are in front, and their whole surface is counted. Some disks are partly in the back, and only the part visible in frontis counted).

It's clumsy, but you seem to want something analytical, so you can deal with it.

Algorithm (clumsy):

-for every disk in family D, do

-is disk in front? If yes increment surface of D family by disk surface

-is disk in back (partly)? Then determine which disks are in front of it, and compute by difference the regions still visible from this back disk (in set theory, it's the symmetric difference intersection with this disk, defined as the complement of intersections in reunion).

Once you have done it for all disks, you have s(D) the surface occupied by your disks, and you have s(S) the surface of the region of interest and the holes have then surface s(S)-s(D)

EASY but brute force and probably very impractical if you get to a distribution of random disks as will be the case in today's big data problems.

THEREFORE, be practical. You may just want a lower bound and an upper bound of the hold surface, which is elegantly and cheaply computable (not an analytical but clumsy and dead-heavy method, with high computational complexity).

-method:

determine the disks "at the border", meaning without other disks intersecting all around. More precisely a border segment of a disk is an arc of circle beloging only to this disk and to no other disk.

If a disk has a border segment, it is said to be a border disk.

Then consider all border disks.

Repeat for each border disk D:

-find the closest border disk D'. Build the segment between the two centers C and C' of these neighbour disks D and D' Define centroid C" as the center of segment P and P' defined as intersections of limiting circle of D resp. D' with segment [C, C'].

the disk centered in C" with limiting circle passing through P and P' has maximum fitted surface all within the hole. The surface of this "maximum-within hole" disk contributes to the lower bound.

Once you have defined all such disks, you look at front/back parts, and you get a lower bound of the hole.

You can get an upper bound by replacing the "maximum within hole" by the minimum disk enclosing D and D': this disk intersects the hole,and contains the disks D and D'. The reunion of all such disks, looking at front and back parts, gives an upper bound of the hole. It is similar to "rounding up" the surface by including the thickness of the pen drawing the border (the pen is the border disks...).

This method is very robust, and fast, low complexity if the border is simpler than the whole set of disks...

Now, it all depends on what problem you really want to solve.

What is the meaning behind your disk problem?