Description of the surfit gridding algorithm

surfit uses originally developed gridding method called CMOFS (consecutive minization of functionals sequence). The CMOFS method described below, allows to strictly determine the influence for each data, used for gridding. To process data with CMOFS algorithm it is necessary to create so-called "gridding rule". Gridding rule is a functional that describes how to use data in gridding. The order of gridding rules defines the priority levels for each data. For example, we can think, what data given in scattered points are most precise and must be taken first. Information about the resulting surface behavior between scattered points is less reliable and we should use it at the last step.

To build resulting surface with CMOFS algorithm surfit determines values in the cells of equidistant grid:

$u(x,y) = \sum_{i=1}^N \sum_{j=1}^M u_{i,j} \phi_{i,j}(x,y),$

where $u_{i,j}$ are cell values, $\phi_{i,j}$ - set of step basis functions:

$\phi_i \left( x \right) = \left\{ 1,x \in \left[ih + a - \frac{h} {2},(i + 1)h + a - \frac{h} {2}\right) \qquad 0, x \notin \left[ih + a - \frac{h} {2},(i + 1)h + a - \frac{h} {2}\right) \hfill \right.$

Here is the breif scheme of CMOFS algorithm:

Classify all data to extent of truth: from less truth until indirect apriori information.
Write functionals sequence
$\Phi_1(u_1,\ldots,u_N),\Phi_2(u_1,\ldots,u_N),\ldots,\Phi_K(u_1,\ldots,u_N).$
These functionals describe the way of taking the data into account. Functionals order must corresponds to data confidence level, determined by user. Resulting surface is founded from functionals minimization.

Then minimizing i-th functional, two situations are possible:

Unconstrained extremum is being searched.

The system of linear equations is being analyzed:

$\frac {\partial \Phi_i(u_1,\ldots,u_N)} {\partial u_j} = 0,$

where $j=1,\ldots,N$ except of numbers of cells with already solved (founded) values. There are two variants under consideration:

The SLE have only one solution. Unknown values are being determined from solution of this system of linear equations.
The SLE have many solutions, or have no solution at all. The SLE isn't being solved. Instead of this, the conditional extremum problem is being solved then i+1'th functional is being minimized.

Constrained extremum is being searched.: This situation appears if previous functional minimization was impossible, or if additional conditions or inequalities are set. For searching of constrained extremum the penalty algorithm is being used.

surfit: open source gridding and contouring software.