Calculating integration over polygon (area of polygon)

Question

Given a polygon, I am trying to find the area of the polygon intersected with $\mathbf{x}<x$ and $\mathbf{y}<y$. I reckon this can be viewed as an integration of a function where its value is 1 inside polygon. Here is a figure to describe my problem better:

When the polygon and $(x,y)$ is given is there a fast way to calculate the area?

I need to calculate the area for many $(x,y)$ values. I have looked into integral transformation but could not manage to express my problem in terms of it.

We can assume polygon is convex if necessary, but I am interested in non-convex cases too.

There are a lot of similar questions already asked here, but I couldn't transform my problem to apply already mentioned methods.

Answer 1

Note that the area of an arbitrary convex polygon $P$ defined by a set of vertices $\left ( x_k,y_k \right)$, $k \in \{1,2,\ldots,N\}$ is given by

$$A(P) = \sum_{k=1}^N \left (x_k\, y_{k+1} - x_{k+1}\, y_k \right )$$

where $\left ( x_{N+1},y_{N+1} \right) = \left ( x_{1},y_{1} \right)$, and the vertices are listed in counterclockwise order. Essentially, you just need to determine the new polygon defined by the intersection of the two regions. This involves making a list of the coordinates contained within the rectangle $0 \le x' \le x$ and $0 \le y' \le y$ in counterclockwise order. You will need to develop the program logic to determine these points, the intersection of the region with the polygon, and the resulting polygon. Once you determine these, you may then compute the area from the above formula.

Answer 2

Use Stokes Theorem: \begin{align} A &= \int{\rm d}x\,{\rm d}y = {1 \over 2}\int \left[{\partial x\over \partial x} - {\partial\left(-y\right) \over \partial y}\right]\,{\rm d}x\,{\rm d}y = {1 \over 2}\int\hat{z}\cdot\nabla\times\left(-y\,\hat{x} + x\,\hat{y}\right) \,{\rm d}x\,{\rm d}y \\[3mm]&= {1 \over 2}\int\nabla\times\left(-y\,\hat{x} + x\,\hat{y}\right) \cdot{\rm d}\vec{S} \qquad\mbox{where}\qquad {\rm d}\vec{S} \equiv \hat{z}\,{\rm d}x\,{\rm d}y \end{align}

\begin{align} A &= {1 \over 2}\int\left(-y\,\hat{x} + x\,\hat{y}\right)\cdot{\rm d}\vec{r} = {1 \over 2}\int\left(\vec{r}\times{\rm d}\vec{r}\right)_{z} \end{align}

Indeed thea era is $\left\vert A\right\vert > 0$. The expression we got above is quite convenient because $\large\mbox{we integrate over line segments}$.

Let's consider two vertices $\left(~\vec{P}\ \mbox{and}\ \vec{Q}~\right)$ of a polygon which connect two neighbors. Any point $\vec{r}\left(\mu\right)$ of the segment which joins the points $\vec{P}$ and $\vec{Q}$ is given by: $$ \vec{r}\left(\mu\right) \equiv \vec{P} + \mu\left(\vec{Q} - \vec{P}\right)\,, \qquad 0 \leq \mu \leq 1\,; \qquad\qquad {\rm d}\vec{r}\left(\mu\right) \equiv \left(\vec{Q} - \vec{P}\right){\rm d}\mu $$

Since $P_{z} = Q_{z} = 0$, the contribution becomes $\displaystyle{% {1 \over 2} \left\vert\vec{P}\times\vec{Q}\right\vert}$

If $\vec{P}_{1}, \vec{P}_{2}, \ldots, \vec{P}_{n}$ are the polygon vertices where $\vec{P}_{i}$ and $\vec{P}_{i + 1}$ are nearest neighbors; the total area is given by $$ {1 \over 2}\sum_{i = 1}^{n} \left\vert\,\vec{P}_{i}\times\vec{P}_{i + 1}\right\vert\,, \qquad\qquad \vec{P}_{n + 1} \equiv \vec{P}_{1} $$