2D Nearest Neighbor Interpolation in Python

Question

Suppose that we have the following look up table

        | 1.23    2.63    4.74    6.43    5.64
 -------|--------------------------------------
 -------|--------------------------------------
 2.56   |  0       0      1        0       1
 4.79   |  0       1      1        1       0
 6.21   |  1       0      0        0       0

This table contains a labeling matrix (having only 0 and 1s), x values and y values. How one can have nearest-neighbor interpolation for this look up table?

Example:

Input: (5.1, 4.9)
Output: 1

Input: (3.54, 6.9)
Output: 0

Vaios

Why is it tagged with scipy and numpy? Does the answer have to use those libs? Also: what did you try? – Marcelenemarcelia

@FilipMalczak I generally wanted to see if there are special functions in these libraries. I was thinking of implementing it with scipy.interpolate.NearestNDInterpolator. However, I was wondering how good and efficient it is for my problem. – Vaios

So you do know how to implement it, but you're wondering if it is already implemented? If it so, then I think that this question - however interesting - is out of scope of SO. See: stackoverflow.com/help/on-topic and stackoverflow.com/help/dont-ask ; I think that this question is too close to point 4 from first of those links. I'm not flagging it though - it may get constructive answers that will be useful for some people. – Marcelenemarcelia

@Vaios this answer might give you some insight – Syncrisis

@SaulloCastro Thanks Saullo :) – Vaios

Answer 1

Look up table

If you have the complete table you don't need interpolation, you just need to look up the index of the nearest (x, y) value and use it on the table

In [1]: import numpy
   ...: x = numpy.array([1.23, 2.63, 4.74, 6.43, 5.64])
   ...: y = numpy.array([2.56, 4.79, 6.21])
   ...: data = numpy.array([[0, 0, 1, 0, 1],
   ...:                     [0, 1, 1, 1, 0],
   ...:                     [1, 0, 0, 0, 0]])
   ...: 
   ...: def lookupNearest(x0, y0):
   ...:     xi = numpy.abs(x-x0).argmin()
   ...:     yi = numpy.abs(y-y0).argmin()
   ...:     return data[yi,xi]

In [2]: lookupNearest(5.1, 4.9)
Out[2]: 1

In [3]: lookupNearest(3.54, 6.9)
Out[3]: 0

Nearest-neighbor interpolation

scipy.interpolate.NearestNDInterpolator will be really useful if your data is composed by scattered points

For example, for data like:

with red = 1, blue =0

In [4]: points = numpy.array([[1.1, 2.5], 
   ...:                       [1.5, 5.2], 
   ...:                       [3.1, 3.0], 
   ...:                       [2.0, 6.0], 
   ...:                       [2.8, 4.7]])
   ...: values = numpy.array([0, 1, 1, 0, 0])

In [5]: from scipy.interpolate import NearestNDInterpolator
   ...: myInterpolator = NearestNDInterpolator(points, values)

In [6]: myInterpolator(1.7,4.5)
Out[6]: 1

In [7]: myInterpolator(2.5,4.0)
Out[7]: 0

Cotenant

First part of the answer is wrong. Consider points: A=(0, 0), B=(1, 100), C=(2, 2). Your code would state that nearest neighbour of A is B, even though it's not true. Try something like min(data, key=lambda point: (point.x-your_point.x)**2 + (point.y-your_point.y)**2) (it's a general idea, I know that you won't be able to get coordinates as properties). No downvote, because second, scipy/numpy related part seems to be more important. – Marcelenemarcelia

@FilipMalczak The first part of my answer will work if the data is arranged in a rectangular grid (a complete table) – Cotenant

Fair enough, I've generalized it to example from second part of the post. – Marcelenemarcelia