Skip to main content

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

Project description

https://travis-ci.org/innolitics/natural-neighbor-interpolation.svg?branch=master

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 3.4+
  • Numpy (has been tested with 1.13+)

Demonstration

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

Also, the final result looks better.

https://raw.githubusercontent.com/innolitics/natural-neighbor-interpolation/master/demo/linear_comparison.png https://raw.githubusercontent.com/innolitics/natural-neighbor-interpolation/master/demo/sin_sin_comparison.png

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.

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

Project details


Release history Release notifications

History Node

0.1.8

This version
History Node

0.1.7

History Node

0.1.6

History Node

0.1.5

History Node

0.1.4

History Node

0.1.3

History Node

0.1.2

History Node

0.1.1

History Node

0.1

Download files

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

Filename, size & hash SHA256 hash help File type Python version Upload date
naturalneighbor-0.1.7.tar.gz (9.1 kB) Copy SHA256 hash SHA256 Source None Sep 14, 2017

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging CloudAMQP CloudAMQP RabbitMQ AWS AWS Cloud computing Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page