3
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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$.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.