Compute the area "inside" a set of polygons

Question

I have a set of disjoint polygons $\cal P$.

I want to compute the area of:

$$\left\{ (x, y), \qquad \exists P_w \in {\cal P}, \exists (x_w, y) \in P_w, x_w \ge x \qquad \text{and} \qquad \exists P_h \in {\cal P}, \exists (x, y_h) \in P_h, y_h \ge y \right\}$$

That is, a point is in this set if and only if there exists a point belonging to a polygon with the same $y$-coordinate and a greater $x$-coordinate and there exists a point belonging to a polygon with the same $x$-coordinate and a greater $y$-coordinate.

This set should be included inside the convex hull, but might be different.

Here is an example with three (black) U-shaped polygons. I would like to compute the area in red:

Is there a known way to compute this?

Answer 1

Let $S$ be the union of polygons $P_w$.

The set $T$ you are describing can be seen as $V \cap H$ (what I call here "shadow sets", this terminology being non-official)

• a vertical shadow set $V$ when the "sun" is placed at infinity above $S$,

• a horizontal shadow set $H$ when the "sun" is placed at infinity on the right of $S$.

It will be good to limit the extension of these shadow sets to the ordinate of the lowest point of $S$ for $V$ and to the abscissa of the leftmost point of $S$ for $H$.

Now, you don't say exactly how your shapes are given.

• If they are pixels on a digital grid, the computation of its area can be obtained by

$area(V \cap H) \ = \ area (V)+area(H)-area(V \cup H)$

• Otherwise, if your polygons are given by the coordinates of their vertices, you could consider for example the computation of area(V) by first constructing the "epigraph" (upper limit of the constitutive upper sides of polygons $P_k$), and then take the integral of the function having this epigraph.