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:
Best Answer
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}.$$