---
AI Summary: "\\- Developed a fast, 3D natural neighbor interpolation library for scattered\
  \ data.  \n- Implemented Discrete Sibson Interpolation in Python/C++.  \n- Created\
  \ an open-source solution for the Innolitics Open Source project.  \n- Repository\
  \ available on GitHub."
Anonymous: false
Assignee:
- J. David Giese
Last Edited Time: '2024-10-08T14:37:00+00:00'
client_logo: []
client_name: Innolitics Open Source
date: '2017-01-27'
featured: false
medical_panel: Tooling
name: 3D Natural Neighbor Interpolation
services: []
summary: High-speed python/C++ module for a superior interpolation algorithm
tags:
- Open-Source
testimonials: []
---

## 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](https://doi.org/10.1109/TVCG.2006.27) for details on the algorithm. You can find the repository for our implementation [here](https://github.com/innolitics/natural-neighbor-interpolation).

<figure>
  <img src="/img/portfolio/3D_Natural_Neighbor_Interpolation-76c6cdda940046a5b9f6ca1c32d3fff4.png">
  <figcaption>
    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.
  </figcaption>
</figure>

<figure>
  <img src="/img/portfolio/3D_Natural_Neighbor_Interpolation-84af6c50df1040e4939298ac6cc88af0.png">
  <figcaption>
    An example of natural neighbor interpolation on a set of points.
  </figcaption>
</figure>