Skip to main content

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 for details.


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


Natural neighbor interpolation can be more accurate than linear barycentric interpolation (Scipy’s default) for smoothly varying functions.

Also, the final result looks better.

Note that the natural neighbor values usually are extrapolated; they were cut off in the demo to fairly compare with Scipy’s linear barycentric method, which does not extrapolate.


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
  • Generalize the threading model (currently it uses 8 threads—one for each quadrant)

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

naturalneighbor-0.2.1.tar.gz (10.5 kB view hashes)

Uploaded source

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Huawei Huawei PSF Sponsor Microsoft Microsoft PSF Sponsor NVIDIA NVIDIA PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page