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?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.
