Nearest neighbor

Nearest neighbor

• Nearest neighbor
  • Algorithm made with Python
  • See also

Nearest-neighbor interpolation (also known as proximal interpolation or, in some contexts, point sampling) is a simple method of multivariate interpolation in one or more dimensions. The nearest neighbor algorithm selects the value of the nearest point and does not consider the values of neighboring points at all, yielding a piecewise-constant interpolant. The algorithm is very simple to implement and is commonly used (usually along with mipmapping) in real-time 3D rendering to select color values for a textured surface.

in wikipedia - en
see also wikipedia - pt

Algorithm made with Python

The algorithm below can be split in three parts. The first is the imports (made in Python 2.7 so we import division) where you can see we use numpy (numerical library) and matplotlib (for 2d plots).

The idea is to check for every node on the grid (see nested loops in the code below) which of the point data (given by x and y) is closer. The function "argmin" gives us the index of the minimum in the distance array which has the same arranging of the "v" array (the actual variable). So the minimum distance array position can give us the true variable value (in "v") of the closest point. This is the concept for the "nearest_neighbor" function.

In the last part (after we've generated the random data for testing) we use "imshow" function to view the grid (we use the transpose because arrays start on top while points start on bottom)

from __future__ import division # import command
import numpy as np # we use numpy for arrays and calculations
import matplotlib.pyplot as plt # we use matplotlib to view the result

# This is the actual nearest neighbor function
def nearest_neighbor(x,y,v,grid):
    for i in xrange(grid.shape[0]):
        for j in xrange(grid.shape[1]):
            distance = np.sqrt((x-i)**2+(y-j)**2)
            grid[i,j] = v[distance.argmin()] # argmin gives us the index of the minimum value.
    return grid

np.random.seed(123433789) # GIVING A SEED NUMBER FOR THE EXPERIENCE TO BE REPRODUCIBLE
grid = np.zeros((100,100),dtype='uint8') # TO SAVE MEMORY I PUT uint8 (0 to 255).
x,y = np.random.randint(0,100,10),np.random.randint(0,100,10) # CREATE POINT SET.
v = np.random.randint(0,10,10) # THIS IS MY VARIABLE

grid = nearest_neighbor(x,y,v,grid)
plt.imshow(grid.T,origin='lower',interpolation='nearest',cmap='jet')
plt.scatter(x,y,c=v,cmap='jet',s=120)
plt.xlim(0,grid.shape[0])
plt.ylim(0,grid.shape[1])
plt.grid()
plt.show()

The result is the following:

See also

• Inverse weighted distance
• Kriging