I need to measure the 2D space that multiple arbitrary polygons occupy. To do so, I need to add the area of all polygons and subtract the overlap. I already have written a function that takes in only 2 polygons and returns the overlap in the form of an array of polygons visually shown as an example here:
function polygonOverlaps(polygon1, polygon2) -> [polygon]
In this case, two polygons are returned here to show the overlap.
However, this only works for 2 polygons.
Consider this scenario:
What logic can I use to determine the total overlap using only my function that takes 2 polygons at a time?
Let's say you have $N$ polygons, with $A_i$ being the area of polygon $i$, and $P_{i\,k}$ is the area of the overlap between polygons $i$ and $k$.
Total area of the union of $N$ polygons is then $$A_U = \sum_{i=1}^{N} A_n - \sum_{i=1}^{N-1} \sum_{k=i+1}^{N} P_{i\,k}$$
In other words, if you have say four polygons, and you know their areas $A_1$, $A_2$, $A_3$, and $A_4$, and the areas of their pairwise overlaps $P_{1\,2}$, $P_{1\,3}$, $P_{1\,4}$, $P_{2\,3}$, $P_{2\,4}$, and $P_{3\,4}$, you sum the areas, but substract the pairwise overlaps.
When we add the areas of the individual polygons, we need to substract each pairwise overlap exactly once. This means that while $P_{i\,k} = P_{k\,i}$, we only want to apply each unique pair $i\,k$ once. The easiest way to do this is to only subtract $P_{i\,k}$ for all $i \in \mathbb{N}$ and $k \in \mathbb{N}$ where $1 \le i \lt k \le N$.