5
$\begingroup$

Let's say I have a polygon defined by a set of coordinates. I also have the radius and (x, y) coordinates of the centre of $n$ circles. I am looking for a function to find the total area of the circles within the polygon, i.e if there are circle segments outside of the polygon, they are not counted towards the area.

My initial thought was to simply find the area of union of the circles, but I am stuck in subtracting the areas of the segments outside of the main polygon. I know I can find the area using the shoelace method, but I am unable to see how this will assist me in getting a result.

Here's an image to demonstrate - I want to find the area of the green space, using only the labelled points and distances as input:

diagram

$\endgroup$
2
  • $\begingroup$ Could you include a picture? $\endgroup$
    – Michael Burr
    Aug 12, 2019 at 20:49
  • 1
    $\begingroup$ @MichaelBurr see now. $\endgroup$
    – Geza Kerecsenyi
    Aug 12, 2019 at 21:12

1 Answer 1

Reset to default
3
$\begingroup$

You could use the inclusion-exclusion principle to reduce the problem to finding the intersection of some subset of your circles with the polygon. Using $P$ to denote the set of points in the polygon, $C_i$ to denote the points in the $i$-th circle, and the function $\mu$ to mean area, that would look mathematically like $$\mu(P\cap(C_1\cup...\cup C_n))=\mu((P\cap C_1)\cup...\cup(P\cap C_n))=\sum_{i=1}^n \mu (P\cap C_i) - \sum_{1\leq i \leq j \leq n} \mu(P\cap C_i \cap C_j) + \sum_{1\leq i \leq j \leq k \leq n} \mu(P\cap C_i \cap C_j \cap C_k)-...+(-1)^{n-1}\mu(P\cap C_1 \cap C_2 \cap ... \cap C_n).$$ But then you would still have to calculate the intersection of an arbitrary subset of the circles with the polygon which still seems excessively difficult. If random numbers don't bother you, I think the best solution to this problem computationally speaking is to draw a box around the polygon and then pick a large number of points randomly from that box. Count each point that falls inside the polygon and at least one of the circles. Then you can calculate the area of the desired region by the formula $$\frac{\textrm{successfulTrials}}{\textrm{totalTrials}}\approx \frac{\textrm{regionArea}}{\textrm{totalArea}}$$ which gives you $$\frac{\textrm{successfulTrials}}{\textrm{totalTrials}}\cdot \textrm{totalArea}\approx \textrm{regionArea}.$$

$\endgroup$
1
  • 1
    $\begingroup$ This seems great! Thanks for the detailed explanation. As per the SE guidelines, it's better to "give the community an adequate chance to fully answer your question", so I'll probably wait a bit before accepting. $\endgroup$
    – Geza Kerecsenyi
    Aug 12, 2019 at 21:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .