# [GRASS-user] Re: r.surf.nnbathy interpolation to whole region

Luigi Ponti lponti at infinito.it
Tue Aug 28 18:55:34 EDT 2007

```Maciej Sieczka wrote:
> Luigi Ponti wrote:
>
>> Maciej Sieczka wrote:
>>
>
> nnbathy performs Delaunay triangulation, not Voronoi tesselation. I
> (darkly) understand there is a mathematical relation between the two,
> but I don't see how it could apply in your example. If this is just my
>

The Voronoi cells and Delaunay triangles are said to be 'dual' to one
another and once one is known the other is completely defined (Sambridge
et al. 1995). Natural neighbor interpolation relies on the construction
of Voronoi diagrams for determining the areas used in computing weights.
What Sakov did was to use the Triangle software to compute the
underlying Delaunay triangulation (Fan et al. 2005). Or at least this is
my understanding after a brief immersion into the available online refs!
To be true, I haven't been able to find out where Voronoi polygons show
up in the nnbathy source code.

* Sambridge M., Braun J., McQueen H., 1995. Geophysical
parameterization and interpolation of irregular data using natural
neighbours. Geophysical Journal International 122: 837-857.
Available at http://wwwrses.anu.edu.au/geodynamics/nn/SBM95/SBM.html
* Fan Q., Efrat A., Koltun V., Krishnan S., Venkatasubramanian S.,
2005. Hardware-assisted natural neighbor interpolation. Workshop
on Algorithm Engineering and Experiments (ALENEX). Available at
www.cs.arizona.edu/~alon/papers/ast.ps

> Anyway - what could be done to overcome the trimming to convex hull
> effect: you need to make sure that the convex hull for your input cells
> covers your whole area of interest - ie. enlarge region enough for
> important input cells not to be omitted. If cells in the input raster
> are distributed so that a convex hull covering the whole area of
> interest is not possible, you need to enhance your input raster.
>

OK -- got it: my input raster are weather stations, so it is going to be
hard...

> r.to.vect -z feature=point followed by v.hull might be faster for
> testing than trial and error with r.surf.nnabthy itself.
>