<p>Triangulate the Voronoi cell then write the integral as a sum over the triangles:</p>

<p><span class="math-container">$$\int_{\Omega}\|P - Pi\|\,dP = \sum_{k=1}^{N}\int_{\Delta_k}\|P-P_i\|\,dP.$$</span></p>

<p>Write the integration over the triangle in barycebtric coordinates. Let the Jacobian of the transformation, from barycentric coordinates to physical coordinates, for triangle <span class="math-container">$k$</span> be <span class="math-container">$J_k$</span>, and <span class="math-container">$|det(J_k)| = 2|Area_{\Delta_k}|$</span>. Then <span class="math-container">$\int_{\Delta_k}f(P)\,dP = |det(J_k)|\int_0^1\int_0^{1-\beta}f(P(\alpha, \beta))\,d\beta\,d\alpha$</span>, where <span class="math-container">$\alpha, \beta$</span> are two of the barycentric coordinates.</p>

<p>Now we need only evaluate (let <span class="math-container">$\vec{v}_i$</span> be the vertices of the current triangle):
<span class="math-container">$$\int_0^1\int_0^{1-\beta}\|\vec{v}_1 + \alpha (\vec{v}_2 - \vec{v}_1) + \beta (\vec{v}_3 - \vec{v}_1) - \vec{P}_i\|^2\,d\alpha\,d\beta$$</span></p>

<p>Expand this and integrate the polynomials. The absolute value of the Jacobian determinant is: <span class="math-container">$$|det(J)| = \|(v_2-v_1) \times (v_3 - v_1)\|$$</span>.
If you are working in 3D, <span class="math-container">$\times$</span> is the cross product here. If it's 2D then augment the vectors with a <span class="math-container">$0$</span> for <span class="math-container">$Z$</span> and perform the cross product.</p>

<p>Another option is to use a quadrature rule to compute this. For example you can still triangulate, but evaluate the integral over a triangle (let <span class="math-container">$f(P) =\|P - P_i\|^2$</span>) through samples at the edge midpoints:
<span class="math-container">$$\int_{\Delta}f(P)\,dP = \frac{|det(J)|}{6}\sum_{k=1}^{3}f\left(\frac{\vec{v}_k + \vec{v}_{k+1}}{2}\right).$$</span></p>

<p>If memory serves me right, the above quadrature is exact for polynomials of up to degree 2 (which is what you have, and the reason I wrote <span class="math-container">$=$</span> instead of <span class="math-container">$\approx$</span>). Note that <span class="math-container">$k+1$</span> is taken to wrap around, that is, for <span class="math-container">$k = 3$</span> I use <span class="math-container">$\vec{v}_4 = \vec{v}_1$</span>.</p>

CC BY-SA 4.0
2020-06-14T08:26:27.077Z
2020-06-16T18:01:14.110Z
2020-06-16T18:01:14.110Z
lightxbulb
<p>I am implementing an algorithm which requires me to compute the following integral,
<span class="math-container">$$\int_{Poly(P_i)}||P-P_i||^2 dP$$</span>
where <span class="math-container">$P_i=(X_i, Y_i)$</span> is a point in 2D and <span class="math-container">$Poly(P_i)$</span> is a polygon containing <span class="math-container">$P_i$</span> (it is the Voronoi Cell of <span class="math-container">$P_i$</span> with a certain weight). Could anyone give me some indications on how to compute this quantity?</p>

<polygon><integral>
How to compute the following integral over a polygon?
Student
# How to compute the following integral over a polygon?

(Asked by: username_0 on 2020-06-14)

I am implementing an algorithm which requires me to compute the following integral,
$$\int\_{Poly(P\_i)}||P-P\_i||^2 dP$$
where $P\_i=(X\_i, Y\_i)$ is a point in 2D and $Poly(P\_i)$ is a polygon containing $P\_i$ (it is the Voronoi Cell of $P\_i$ with a certain weight). Could anyone give me some indications on how to compute this quantity?

**Tags:** polygon, integral


---

## 1 answers

### Answer by username_1 on 2020-06-14. Score: 5 | Accepted answer

Triangulate the Voronoi cell then write the integral as a sum over the triangles:

$$\int\_{\Omega}\|P - Pi\|\,dP = \sum\_{k=1}^{N}\int\_{\Delta\_k}\|P-P\_i\|\,dP.$$

Write the integration over the triangle in barycebtric coordinates. Let the Jacobian of the transformation, from barycentric coordinates to physical coordinates, for triangle $k$ be $J\_k$, and $|det(J\_k)| = 2|Area\_{\Delta\_k}|$. Then $\int\_{\Delta\_k}f(P)\,dP = |det(J\_k)|\int\_0^1\int\_0^{1-\beta}f(P(\alpha, \beta))\,d\beta\,d\alpha$, where $\alpha, \beta$ are two of the barycentric coordinates.

Now we need only evaluate (let $\vec{v}\_i$ be the vertices of the current triangle):
$$\int\_0^1\int\_0^{1-\beta}\|\vec{v}\_1 + \alpha (\vec{v}\_2 - \vec{v}\_1) + \beta (\vec{v}\_3 - \vec{v}\_1) - \vec{P}\_i\|^2\,d\alpha\,d\beta$$

Expand this and integrate the polynomials. The absolute value of the Jacobian determinant is: $$|det(J)| = \|(v\_2-v\_1) \times (v\_3 - v\_1)\|$$.
If you are working in 3D, $\times$ is the cross product here. If it's 2D then augment the vectors with a $0$ for $Z$ and perform the cross product.

Another option is to use a quadrature rule to compute this. For example you can still triangulate, but evaluate the integral over a triangle (let $f(P) =\|P - P\_i\|^2$) through samples at the edge midpoints:
$$\int\_{\Delta}f(P)\,dP = \frac{|det(J)|}{6}\sum\_{k=1}^{3}f\left(\frac{\vec{v}\_k + \vec{v}\_{k+1}}{2}\right).$$

If memory serves me right, the above quadrature is exact for polynomials of up to degree 2 (which is what you have, and the reason I wrote $=$ instead of $\approx$). Note that $k+1$ is taken to wrap around, that is, for $k = 3$ I use $\vec{v}\_4 = \vec{v}\_1$.


---

