Nearest Neighbor Interpolation

Introduction

• Nearest neighbor interpolation is the most simple type of interpolation.
• To find the value of a point which is not in the given set of points:
  1. Find the closest point for which you do have a value.
  2. Use its value.

Example

• If we are given a set of data points:

  X	1	2	3	4	5	6	7
  y	28	21	96	96	120	87	50

  Find the value for y when x is 2.4

1. The point which has the closest x to 2.4 is (2, 21)
2. When x is 2.4, y is 21

Visualization

Code (using SciPy)

from scipy import interpolate

dataPoints = [
    [1, 28],
    [2, 21],
    [3, 96],
    [4, 96],
    [5, 120],
    [6, 87],
    [7, 50]
]

interpolator = interpolate.interp1d(
    [dataPoint[0] for dataPoint in dataPoints],
    [dataPoint[1] for dataPoint in dataPoints],
    'nearest')

print(interpolator(2.4)) # prints 21
print(interpolator(2.6)) # prints 96

Code (using NumPy)

import numpy as np

class NearestNeighborInterpolator:
    # an array of x values, in order
    _sortedDomain = []

    # a dictionary of x, y values
    _dataPointsDict = {}

    def __init__(self, dataPoints):
        for dataPoint in dataPoints:
            self._dataPointsDict[dataPoint[0]] = dataPoint[1]

        self._sortedDomain = [dataPoint[0] for dataPoint in dataPoints]
        self._sortedDomain = np.sort(self._sortedDomain)

    def interpolate(self, x):
        # find the index of the smallest element larger than x
        closest = np.searchsorted(self._sortedDomain, x)

        # either 'closest' or 'closest - 1' will be closest to x
        if abs(self._sortedDomain[closest - 1] - x) < abs(self._sortedDomain[closest] - x):
            closest -= 1

        # look up the corresponding y value for our value closest to x
        y = self._dataPointsDict[self._sortedDomain[closest]]

        return y


dataPoints = [
    [1, 28],
    [2, 21],
    [3, 96],
    [4, 96],
    [5, 120],
    [6, 87],
    [7, 50]
]

interpolator = NearestNeighborInterpolator(dataPoints)

print(interpolator.interpolate(2.4)) # prints 21
print(interpolator.interpolate(2.6)) # prints 96