Interpolation of scattered data: What could I do?

Question

Hi! I need your help.

I'm working on a 3D chart in Java using Java 3D. It should be able to display a bunch of measured values. As measured, the data I get is scattered. This means I will have to interpolate the missing points in order to get my surface plotted nicely.

I didn't study all that 3D-Geometry stuff yet and I don't know where to start. My idea is to triangulate the points to a surface and then, based on the triangulation, interpolate the missing points. (see this to have a rough idea of what I want to achieve)

Does someone have experiences with the interpolation of scattered data? Is my approach the right one? If yes, what kind of data structures and algorithms will I need in order to triangulate my points cloud?

Answer 1

You need to use an interpolation function, basically it takes your data points as input and will return a z value for any (x,y).

For instance you can use a spline interpolation, as implemented in apache commons math

Answer 2

Triangulation is very fast if you need to do a lot of interpolation on a large data irregular dataset, for example, contouring a ground surface. The interpolation is linear and discrete, based solely on the three points of the triangle in which you are interpolating. In also supports constraints such as break lines, e.g. think of a ground surface defined by points that includes a line defining a ridge or cliff.

Splines give a smoother result across all the input, but can be very slow on larger data sets and may give unusual results on poorly spaced data. You may also want to look up NURBS (a type of spline surface) and Bezier patches.

Answer 3

If you don't want the burden of triangulating, you may want to look at kriging or radial basis function interpolation.