Integrating polynomials over polygonal curves in 2D

Posted by Diego Assencio on 2014.01.01 under Computer science (Numerical methods)

Frequently in Scientific Computing one needs to integrate polynomials over polygonal curves. This post derives a general formula for the integral of polynomial functions over two-dimensional polygonal curves.

Let $p_d(x,y)$ be a polynomial of degree $d$: $$ p_d(x,y) = \sum_{m,n = 0}^{d} c_{mn}x^m y ^n $$ For instance, if $d=2$: $$ p_2(x,y) = c_{00} + c_{10}x + c_{01}y + c_{20}x^2 + c_{11}xy + c_{02}y^2 \label{post_c6d2b27efe4c87b1cc24686bf8793c0f_eq_polyn_deg_2} $$ Let $S$ be a two-dimensional polygonal curve (in what follows, $S$ can actually be an arbitrary set of segments). We wish to compute the line integral of $p_d(x,y)$ over $S$: $$ \int_{S} p_d(x,y) dl $$ The curve $S$ is a collection of $n$ segments $S_i$, $i = 1,2,\ldots,n$. Let $L_i$ be the length of $S_i$ and $(x_i,y_i)$ and $(x_i + \Delta{x_i},y_i + \Delta{y_i})$ be the coordinates of its end nodes (see figure 1). We can parameterize the $i$-th segment of $S$ as shown below: $$ {\bf r}_i(s) = \left( \tilde{x}_i(s),\tilde{y}_i(s) \right) = (x_i + s\Delta{x_i}, y_i + s\Delta{y_i}),\quad s \in [0,1] \label{post_c6d2b27efe4c87b1cc24686bf8793c0f_eq_param_segm} $$

Fig. 1: A polygonal curve $S$; $(x_{i+1},y_{i+1}) =$ $(x_i + \Delta{x_i}, y_i + \Delta{y_i})$ for $i = 1,2,3$.

Let ${\bf r}_i'(s)$ be the derivative of ${\bf r}_i(s)$ with respect to $s$. The length of ${\bf r}_i'(s)$ is: $$ \big\|{\bf r}'_i(s)\big\| = \big\|(\Delta{x_i},\Delta{y_i})\big\| = \sqrt{\Delta{x_i}^2 + \Delta{y_i}^2} = L_i\ $$ We can now use the parameterization from equation \eqref{post_c6d2b27efe4c87b1cc24686bf8793c0f_eq_param_segm} directly to compute the desired line integral: $$ \begin{eqnarray} \label{post_c6d2b27efe4c87b1cc24686bf8793c0f_polyg_integ_param} \int_{S} p_d(x,y) dl &=&\sum_{i=1}^{n} \int_{S_i} p_d(x,y) dl = \nonumber\\[5pt] &=&\sum_{i=1}^{n} \int_0^1 p_d(\tilde{x}_i(s),\tilde{y}_i(s)) \big\|{\bf r}'_i(s)\big\|ds \nonumber\\[5pt] &=& \sum_{i=1}^{n} \int_0^1 p_d( x_i + s\Delta{x_i}, y_i + s\Delta{y_i} ) L_i ds \nonumber\\[5pt] &=& \sum_{i=1}^{n} L_i \int_0^1 \sum_{m,n = 0}^{d} c_{mn} ( x_i + s\Delta{x_i} )^m ( y_i + s\Delta{y_i})^n ds \end{eqnarray} $$ Using the polynomial expansions below: $$ \begin{eqnarray} ( x_i + s\Delta{x_i} )^m &=& \sum_{k = 0}^{m} \binom{m}{k} x_i^{m-k}\Delta{x_i}^k s^k \nonumber\\[5pt] ( y_i + s\Delta{y_i})^n &=& \sum_{p = 0}^{n} \binom{n}{p} y_i^{n-p}\Delta{y_i}^p s^p \end{eqnarray} $$ and doing a bit more algebraic work, one gets: $$ \displaystyle \int_0^1 p_d( \tilde{x}_i(s),\tilde{y}_i(s) ) ds = \sum_{m,n=0}^{d} \sum_{k = 0}^{m} \sum_{p = 0}^{n} \alpha_{mnkp} \frac{x_i^{m-k}\Delta{x_i}^k y_i^{n-p}\Delta{y_i}^p}{k+p+1} \label{post_c6d2b27efe4c87b1cc24686bf8793c0f_eq_poly_int_over_param_seg} $$ where: $$ \displaystyle\alpha_{mnkp} = \binom{m}{k} \binom{n}{p} c_{mn} $$ From the result above, we get: $$ \boxed{ \displaystyle \int_{S} p_d(x,y) dl = \sum_{i=1}^{n} L_i \left(\sum_{m,n=0}^{d} \sum_{k = 0}^{m} \sum_{p = 0}^{n} \alpha_{mnkp} \frac{x_i^{m-k}\Delta{x_i}^k y_i^{n-p}\Delta{y_i}^p}{k+p+1}\right) } \label{post_c6d2b27efe4c87b1cc24686bf8793c0f_eq_symb_integ_poly_over_segm_curve} $$

Unfortunately equation \eqref{post_c6d2b27efe4c87b1cc24686bf8793c0f_eq_symb_integ_poly_over_segm_curve} is not very efficient for numerical computations (although it can be used as a last resource). Whenever possible, it is better to compute the integrals explicitly and hard-code them. For example, if for a given problem all polyomials that must be integrated have degree $d=2$ (as in equation \eqref{post_c6d2b27efe4c87b1cc24686bf8793c0f_eq_polyn_deg_2}), then one can use equation \eqref{post_c6d2b27efe4c87b1cc24686bf8793c0f_eq_symb_integ_poly_over_segm_curve} to obtain a formula which is easy to hard-code: $$ \begin{eqnarray} \int_{S} p_2(x,y) dl = \sum_{i=1}^{n} L_i \Bigg[ \; & &c_{00} \nonumber\\[5pt] \; &+ & c_{10}\left(x_i + \frac{\Delta{x_i}}{2}\right) \nonumber\\[5pt] \; &+ & c_{01}\left(y_i + \frac{\Delta{y_i}}{2}\right) \nonumber\\[5pt] \; &+ &c_{20}\left(x_i^2 + x_i\Delta{x_i} + \frac{\Delta{x_i}^2}{3}\right) \nonumber\\[5pt] \; &+ &c_{11}\left(x_i y_i + \frac{x_i\Delta{y_i}}{2} + \frac{y_i \Delta{x_i}}{2} + \frac{\Delta{x_i} \Delta{y_i}}{3}\right) \nonumber\\[5pt] \; &+ &c_{02}\left(y_i^2 + y_i\Delta{y_i} + \frac{\Delta{y_i}^2}{3}\right) \Bigg] \end{eqnarray} $$


No comments posted yet.