The locations (centre coordinate x,y) and radii of all the circles are given. How to get the area of the coverage hole (area in green in the figure) ? Radii may not equal to each other. It is a general issue in wireless sensor network.
Looking for your answers. Thank you.
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 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
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.
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
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
- Badges
- Science topic