Numerical integration of a function with values known at a given point set (finite and discrete) over an area bounded by discrete points?

Let D be the area bounded by a series of points {x_i,y_i} (1<=i<=N).(The area need not to be convex and the points are supposed to go along the boundary curve.)

Let f be a function defined on D but we only know its values on a given point set (finite and discrete), say {x'_i,y'_i,f(x'_i,y'_i)} (1<=i<=N').(The given data set need not to be "dense" in D.)

How can I do numeric integration of f over D?

Here is what I think:

1) First we should approxi开发者_高级运维mate the boundary of D by segments between those series of points.

2) Then we should do some interpolation on the given data set. However, interpolation in two-dimension is not always possible. Then I get stuck.

Can you please help? Thank you.

If you were able to triangulate your points, the jobs was done: In each triangle, you know the function values at the corner points, and integrate that via

triangle_area * (val1 + val2 + val3) / 3.0

While convex triangulation is a solved problem with lots of tools available (check out qhull, for example), nonconvex triangulation is a lot harder. Anyhow, digging in this direction will probably get you somewhere.

I'd write the solution as a contour integral and use the sum of a Gaussian or log quadrature 1D numerical integration over each piecewise segment on the boundary. Log quadrature is useful if the function is singular at some point on the curve.

You have to know the function values at the endpoints of each piecewise curve. You assume a particular interpolation function (linear to start, higher order if you'd like), and do the numerical integration by interpolating between the end point values.

If you get that far, I'd recommend checking convergence by doubling the number of curves along the contour and re-integrating. If the integral value doesn't change after one or two iterations you can consider yourself converged.

If you're saying you don't know the values of the function anywhere on the curve, then you can't do the integration.