forum.alglib.net

Hi Alglib

A general question. We are looking for a library to interpolate point values in 3D space to a 2D surfaces (X,Y,Z) . Like a digital elevation model, generated from a series of point measurements.

Are there functionalities for this in ALGLIB?

Which types of interpolation rutines would you suggest?

We are currently using IDW and Kriging to generate 2D surfaces, but are looking for a set of more flexible, robust and fast interpolators to offer to our customers.

Please advice

Thank you for providing a fantastic library - and thank you for the release of the new Delphi versio - we wil llook into this :-)

Best
Torben

Hi!

Yes, ALGLIB has such functionality - hierarchical RBFs. It supports both modelling Z(x,y) and F(x,y,z). You should use rbf subpackage - http://www.alglib.net/translator/man/manual.delphi.html#unit_rbf - and activate/tweak HRBF algorithm with rbfsetalgohierarchical() function.

NOTE: from your words I assume that you want to use Delphi version :) if you want to use C++ or C#, replace "delphi" in URL with "cpp" or "csharp" for appropriate manual file.

NOTE 2: if you want, you can write to me - sergey.bochkanov at alglib.net - and I can help you to tune HRBFs to your specific task. The most important points are: typical number of points, spatial extent (in meters) and typical search radius (in meters).

Sergey,

Have you considered possibilities for generalizing the Spline2D and Spline3D routines, themselves, to irregular grids; possibly with the help of Delaunay Triangulation (as well as adding routines for triangulation, itself)?

A suitably-defined generalization may be sufficiently power to enable one to combine RBF, IDW and Spline{2,3}D into a single form.

I use the following modification for IDW, by the way: f(r) = (R - r)/(R + kr), for |r| < R; f(r) = 0, for |r| >= R, where k is an adjustable parameter in the range 0 to 1. This regularizes IDW by removing the singularity from 1/r (since it is equivalent to f(r) = 1/(r + e) - 1/(R + e) up to scale) and it removes the long-distance tail with the upper bound R.

It might be worth keeping IDW around and adding this modification in the routines.

Hi!

Do you have telepathic abilities? :))))) For the last month I am thinking on implementation of 2D and 3D penalized regression splines similar to spline1dfitpenalized(), but generalized to 2D/3D (and on speeding up single dimensional penalized regression splines). It is possible to implement them quite efficiently (avoiding need to solve large NxN or NxNxN dense linear systems) by splitting problem to smaller ~20x20 or ~20x20x20 chunks.

However, I did not thought on merging them with RBFs.... in my opinion, both options are quite powerful alone.

On the issue of scattered-point multi-dimensional splines, following up on your latest revisions to 2D splines:

It is still an open problem under active research to find a way to generalize the 1-dimensional C2 splines to irregularly spaced point clouds in 2 or more dimensions. But the common element that all methods have is that they involve basis functions.
However, the basis functions are not ad hoc, but are determined by the distribution of points. The difference with RBFs is that there are no magic numbers of conditioning parameters involved. It may be possible to adapt the method used to create morphed maps.

Computational Statistics and Data Analysis 55 (2011) 2962–2974
Kernel interpolation; Thomas M?hlenst?dt, Sonja Kuhnt

Surrogate interpolation models for time-consuming computer experiments are being increasingly used in scientific and engineering problems. A new interpolation method, based on Delaunay triangulations and related to inverse distance weighting, is introduced.

This method not only provides an interpolator but also uncertainty bands to judge the local fit, in contrast to methods such as radial basis functions. Compared to the classical Kriging approach, it shows a better performance in specific cases of small data sets and data with non-stationary behavior.

Map Morphing: Making Sense of Incongruent Maps
Derek F. Reilly, Kori M. Inkpen

In the past, I tried interpolation with 2D point clouds by restricting to holomorphic functions and then just using 1D (complex) polynomial curve fitting - with mixed results (instability is the main problem). It might work better with complex rational function curve fitting and meromorphic functions, if that's possible.

For 3D and 4D, it may still be possible to use curve fitting ... with support provided for quaternion arithmetic. But analytic, holomorphic, harmonic, conformal are no longer the same as each other, as they are with complex functions, and may each require separate treatments.