Fast, discrete natural neighbor interpolation in 3D on a CPU.

## Project description ## Discrete Sibson (Natural Neighbor) Interpolation

Natural neighbor interpolation is a method for interpolating scattered data (i.e. you know the values of a function at scattered locations). It is often superior to linear barycentric interpolation, which is a commonly used method of interpolation provided by Scipy’s griddata function.

There are several implementations of 2D natural neighbor interpolation in Python. We needed a fast 3D implementation that could run without a GPU, so we wrote an implementation of Discrete Sibson Interpolation (a version of natural neighbor interpolation that is fast but introduces slight errors as compared to “geometric” natural neighbor interpolation).

See https://doi.org/10.1109/TVCG.2006.27 for details.

### Dependencies

• Python 2.7 or 3.4+
• Numpy (has been tested with 1.13+)

### Usage

This module exposes a single function, `griddata`.

The API for `naturalneighbor.griddata` is similar to `scipy.interpolate.griddata`. Unlike Scipy, the third argument is not a dense mgrid, but instead is just the ranges that would have been passed to `mgrid`. This is because the discrete Sibson approach requires the interpolated points to lie on an evenly spaced grid.

```import scipy.interpolate
import numpy as np

import naturalneighbor

num_points = 10
num_dimensions = 3
points = np.random.rand(num_points, num_dimensions)
values = np.random.rand(num_points)

grids = tuple(np.mgrid[0:100:1, 0:50:100j, 0:100:2])
scipy_interpolated_values = scipy.interpolate.griddata(points, values, grids)

grid_ranges = [[0, 100, 1], [0, 50, 100j], [0, 100, 2]]
nn_interpolated_values = naturalneighbor.griddata(points, values, grid_ranges)
```

### Future Work

• Provide options for extrapolation handling
• Support floats and complex numbers (only support doubles at the moment)
• Support 2D (only support 3D)
• Add documentation with discussion on limitations of discrete sibson’s method
• Uncomment cpplint from tox.ini and cleanup C++ code

## Project details

This version 0.2.1 0.2.0 0.1.8 0.1.7 0.1.6 0.1.5 0.1.4 0.1.3 0.1.2 0.1.1 0.1