NEAREST_ND_INTERP

Overview

The NEAREST_ND_INTERP function performs nearest-neighbor interpolation for scattered data in N-dimensional space (where N > 1). Given a set of known data points with associated values, the function estimates values at new query points by assigning each query point the value of its closest known data point.

This implementation uses SciPy’s NearestNDInterpolator, which internally constructs a k-d tree data structure via scipy.spatial.cKDTree for efficient nearest-neighbor lookup. The k-d tree is a space-partitioning binary tree that recursively subdivides the data space along alternating axes, enabling queries in approximately O(\log n) time complexity for well-distributed data, compared to O(n) for brute-force search.

Nearest-neighbor interpolation is particularly useful when:

  • Data is irregularly spaced or scattered across multiple dimensions
  • Preserving original data values exactly at sample points is required (no smoothing)
  • A simple, fast interpolation method is preferred over smoother alternatives

The algorithm assigns the value f(\mathbf{x}_i) to a query point \mathbf{q} where \mathbf{x}_i is the data point minimizing the Euclidean distance:

\mathbf{x}_i = \underset{\mathbf{x} \in X}{\arg\min} \|\mathbf{q} - \mathbf{x}\|_2

Unlike linear or spline interpolation methods, nearest-neighbor interpolation produces a piecewise-constant surface with discontinuities at the boundaries between regions. For smoother results, consider LinearNDInterpolator or CloughTocher2DInterpolator. For data on regular grids, interpn provides a more efficient alternative.

This example function is provided as-is without any representation of accuracy.

Excel Usage

=NEAREST_ND_INTERP(points, values, xi)
  • points (list[list], required): Data point coordinates (n_points, n_dims)
  • values (list[list], required): Data values (n_points, 1)
  • xi (list[list], required): Query points (n_new_points, n_dims)

Returns (list[list]): A 2D list of interpolated values, or an error message (str) if invalid.

Example 1: Nearest-neighbor on 2D unit square

Inputs:

points values xi
0 0 0 0.1 0.1
1 0 1
0 1 1
1 1 2

Excel formula:

=NEAREST_ND_INTERP({0,0;1,0;0,1;1,1}, {0;1;1;2}, {0.1,0.1})

Expected output:

0

Example 2: Multiple query points in 2D

Inputs:

points values xi
0 0 0 0.1 0.1
1 0 1 0.9 0.9
0 1 1
1 1 2

Excel formula:

=NEAREST_ND_INTERP({0,0;1,0;0,1;1,1}, {0;1;1;2}, {0.1,0.1;0.9,0.9})

Expected output:

Result
0
2
Example 3: Nearest-neighbor in 3D tetrahedron

Inputs:

points values xi
0 0 0 10 0.2 0.1 0.1
1 0 0 20
0 1 0 30
0 0 1 40

Excel formula:

=NEAREST_ND_INTERP({0,0,0;1,0,0;0,1,0;0,0,1}, {10;20;30;40}, {0.2,0.1,0.1})

Expected output:

10

Example 4: Multiple queries on 2D grid pattern

Inputs:

points values xi
0 0 5 0.4 0.4
2 0 10 1.6 0.4
0 2 15 1.6 1.6
2 2 20

Excel formula:

=NEAREST_ND_INTERP({0,0;2,0;0,2;2,2}, {5;10;15;20}, {0.4,0.4;1.6,0.4;1.6,1.6})

Expected output:

Result
5
10
20

Python Code

Show Code 
import numpy as np
from scipy.interpolate import NearestNDInterpolator as scipy_NearestNDInterpolator

def nearest_nd_interp(points, values, xi):
    """
    Nearest neighbor interpolation in N > 1 dimensions.

    See: https://docs.scipy.org/doc/scipy/reference/generated/scipy.interpolate.NearestNDInterpolator.html

    This example function is provided as-is without any representation of accuracy.

    Args:
        points (list[list]): Data point coordinates (n_points, n_dims)
        values (list[list]): Data values (n_points, 1)
        xi (list[list]): Query points (n_new_points, n_dims)

    Returns:
        list[list]: A 2D list of interpolated values, or an error message (str) if invalid.
    """
    try:
        def to2d(x):
            return [[x]] if not isinstance(x, list) else x

        # Normalize inputs to 2D lists
        points = to2d(points)
        values = to2d(values)
        xi = to2d(xi)

        # Validate inputs are lists
        if not isinstance(points, list) or not isinstance(values, list) or not isinstance(xi, list):
            return "Error: Invalid input: points, values, and xi must be 2D lists."

        # Validate all elements are lists
        if not all(isinstance(row, list) for row in points):
            return "Error: Invalid input: points must be a 2D list."
        if not all(isinstance(row, list) for row in values):
            return "Error: Invalid input: values must be a 2D list."
        if not all(isinstance(row, list) for row in xi):
            return "Error: Invalid input: xi must be a 2D list."

        # Validate non-empty
        if len(points) == 0 or len(values) == 0 or len(xi) == 0:
            return "Error: Invalid input: points, values, and xi must be non-empty."

        # Validate consistent dimensions
        if len(points) != len(values):
            return "Error: Invalid input: points and values must have the same number of rows."

        # Validate all rows have same length
        n_dims = len(points[0])
        if n_dims == 0:
            return "Error: Invalid input: points must have at least one column."
        if not all(len(row) == n_dims for row in points):
            return "Error: Invalid input: all rows in points must have the same length."

        n_dims_xi = len(xi[0])
        if n_dims_xi == 0:
            return "Error: Invalid input: xi must have at least one column."
        if not all(len(row) == n_dims_xi for row in xi):
            return "Error: Invalid input: all rows in xi must have the same length."

        if n_dims != n_dims_xi:
            return "Error: Invalid input: points and xi must have the same number of columns."

        # Validate values is single column
        if not all(len(row) == 1 for row in values):
            return "Error: Invalid input: values must have exactly one column."

        # Convert to numpy arrays and validate numeric values
        try:
            points_arr = np.array(points, dtype=float)
            values_arr = np.array(values, dtype=float).flatten()
            xi_arr = np.array(xi, dtype=float)
        except (ValueError, TypeError):
            return "Error: Invalid input: all elements must be numeric."

        # Check for NaN or inf values
        if np.any(np.isnan(points_arr)) or np.any(np.isinf(points_arr)):
            return "Error: Invalid input: points contains non-finite values."
        if np.any(np.isnan(values_arr)) or np.any(np.isinf(values_arr)):
            return "Error: Invalid input: values contains non-finite values."
        if np.any(np.isnan(xi_arr)) or np.any(np.isinf(xi_arr)):
            return "Error: Invalid input: xi contains non-finite values."

        # Perform interpolation
        try:
            interp = scipy_NearestNDInterpolator(points_arr, values_arr)
            result = interp(xi_arr)
        except Exception as exc:
            return f"Error: scipy.interpolate.NearestNDInterpolator error: {exc}"

        # Validate result
        if not isinstance(result, np.ndarray):
            return "Error: scipy.interpolate.NearestNDInterpolator error: unexpected result type."

        # Check for NaN or inf in result
        if np.any(np.isnan(result)) or np.any(np.isinf(result)):
            return "Error: scipy.interpolate.NearestNDInterpolator error: result contains non-finite values."

        # Convert to 2D list
        result_2d = [[float(val)] for val in result]

        return result_2d
    except Exception as e:
        return f"Error: {str(e)}"

Online Calculator

Data point coordinates (n_points, n_dims)
Data values (n_points, 1)
Query points (n_new_points, n_dims)