3D Natural Neighbor Interpolation

Innolitics Open Source

The Problem

We required a fast, 3D, natural-neighbor interpolation library for a client project. None existed.

The Solution

With the permission of the client, we developed an open source solution.

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 this paper introducing discrete sibson interpolation for details on the algorithm. You can find the repository for our implementation here.

An example Voroni Diagram with a whitened area in the middle showing how the values of the nearest neighboring points are sampled to produce an interpolated “nearest neighbor” value.
An example of natural neighbor interpolation on a set of points.

Let's Talk

Every great partnership starts with a conversation. Fill out the form below for a discovery call, and an Innolitics team member will contact you soon.