# Efficiently estimate a 2D integral from irregularly sampled, limited data

I have measured data of the following form:

$f(3.2, 2.5) = 10$

$f(3.7, 2.6) = 9$

$f(3.1, 2.8) = 9.1$

(etc)...

That is, I know $f(x, y)$ for certain irregularly spaced values of $x$ and $y$. I want to estimate the integral $\int f(x, y) dx dy$. Is there a standard method to estimate this integral?

Details:

I cannot make additional measurements, I have to give my best estimate with the measurements at hand. I do not need especially high accuracy; the data is somewhat noisy anyway. A fast solution would be very helpful, since I will eventually need to repeat this estimation for millions or billions of inputs. If there happens to be a Python solution, that would be excellent.

EDIT:

I should mention that $f(x, y)$ is only nonzero in the local neighborhood that I'm sampling. For some fixed value $a$, if $x^2 + y^2 > a$, then $f(x, y) = 0$.

-
Are the points $(x_i,y_i)$ fixed and only the values of $f(x_i,y_i)$ vary, or do both vary? – Rahul Aug 28 '12 at 3:18
Both will vary. – Andrew Aug 28 '12 at 3:49

Some ideas:

a) If it makes sense to assume that the data points are roughly uniformly distributed in the integration region, a very quick estimate would be the average of the function values times the total area.

b) You could triangulate the set of data points and give each point the weight of one third of the areas of all triangles it participates in. The problem is that you have to somehow deal with the part of the integration region that's outside the convex hull of the data points – you could add external points and either estimate their function values or distribute their weight in the external triangles onto the internal points.

c) You could weight the points according to the areas of their Voronoi cells.

d) You could randomly generate points uniformly distributed in the region of integration and use the function value of the closest data point; this would be a Monte Carlo version of c) in case you don't want to bother with computing the Voronoi diagram.

-
Very nice! This is the type of help I'm looking for. I'll try these out. Don't suppose you know of any computer packages that perform these functions? – Andrew Aug 28 '12 at 6:32
@Andrew: Sorry, I don't, but I suspect others here do. – joriki Aug 28 '12 at 6:40
@Andrew, joriki: I wouldn't recommend option (b) because it can be discontinuous with respect to the point locations. Option (c) is quite nice, though option (a) is almost certainly best if the uniformity assumption holds. To compute Voronoi diagrams, you could try the Qhull library, which has a Python binding called Delny. – Rahul Aug 28 '12 at 7:13
Ok, looks like the bounty didn't attract much attention. Thanks for your help, joriki. – Andrew Sep 5 '12 at 20:09
@Andrew: You're welcome! – joriki Sep 5 '12 at 21:06