Finding Index of Nearest Point in Numpy Arrays of X and Y Coordinates

Finding index of nearest point in numpy arrays of x and y coordinates

scipy.spatial also has a k-d tree implementation: scipy.spatial.KDTree.

The approach is generally to first use the point data to build up a k-d tree. The computational complexity of that is on the order of N log N, where N is the number of data points. Range queries and nearest neighbour searches can then be done with log N complexity. This is much more efficient than simply cycling through all points (complexity N).

Thus, if you have repeated range or nearest neighbor queries, a k-d tree is highly recommended.

Finding nearest xy-point in numpy array and second nearest with condition

With help from @unutbu's comment I found this solution which works quite good also in those cases where the orangeline goes not through the field.

Here are the functions for the grid:

import matplotlib.mlab as mlab
import numpy as np
import scipy

def define_grid(rawdata):
xmin, xmax = np.amin(rawdata[:, 1]), np.amax(rawdata[:,1])
ymin, ymax = np.amin(rawdata[:, 2]), np.amax(rawdata[:,2])

x, y, z = rawdata[:, 1], rawdata[:, 2], rawdata[:, 0]

# Size of regular grid
ny, nx = (ymax - ymin), (xmax - xmin)

# Generate a regular grid to interpolate the data.
xi = np.linspace(xmin, xmax, nx)
yi = np.linspace(ymin, ymax, ny)
xi, yi = np.meshgrid(xi, yi)

# Interpolate using delaunay triangularization
zi = mlab.griddata(x,y,z,xi,yi)
return xi, yi, zi

def grid_as_array(xi,yi,zi):
xi_flat, yi_flat, zi_flat = np.ravel(xi), np.ravel(yi), np.ravel(zi)

# reduce arrays for faster calculation, take only every second element
xi_red, yi_red, zi_red = xi_flat[1::2], yi_flat[1::2], zi_flat[1::2]

# stack to array with elements [x y z], but there are z values that are 'nan'
xyz_with_nan = np.hstack((xi_red[:, np.newaxis], yi_red[:, np.newaxis],
zi_red[:, np.newaxis]))

# sort out those elements with 'nan'
xyz = xyz_with_nan[~np.isnan(xyz_with_nan).any(axis=1)]
return xyz

Another function to find the closest point from the grid for the values from orangeline:

def closest_node(points, datafield):
mytree = scipy.spatial.cKDTree(datafield)
dist, indexes = mytree.query(points)
return indexes

And now the code:

# use function to create from the raw data an interpolated datafield
xi, yi, zi = define_grid(datafield)

# rearrange those values to bring them in the form of an array with [x y z]
xyz = grid_as_array(xi, yi, zi)

# search closest values from grid for the points of the orangeline
# orangeline_xy is the array with elements [x y]
indexes = self.closest_node(orangeline_xy, xyz[:,0:2])

# take z values from the grid which we found before
orangeline_z = xyz[indexes, 2]

# add those z values to the points of the orangeline
orangeline_xyz = np.hstack((orangeline_xy,orangeline_z[:, np.newaxis]))

Find nearest value in numpy array

import numpy as np
def find_nearest(array, value):
array = np.asarray(array)
idx = (np.abs(array - value)).argmin()
return array[idx]

Example usage:

array = np.random.random(10)
print(array)
# [ 0.21069679 0.61290182 0.63425412 0.84635244 0.91599191 0.00213826
# 0.17104965 0.56874386 0.57319379 0.28719469]

print(find_nearest(array, value=0.5))
# 0.568743859261

Get nearest coordinate in a 2D numpy array

I assume you mean euclidean distance. Try this:

a = np.array([[77.62881735, 12.91172607],          
[77.6464534, 12.9230648],
[77.65330961,12.92020244],
[77.63142413 ,12.90909731]])

b = np.array([77.64000112, 12.91602265])

idx_min = np.sum( (a-b)**2, axis=1, keepdims=True).argmin(axis=0)
idx_min, a[idx_min]

Output:

(array([1], dtype=int64), array([[77.6464534, 12.9230648]]))

Finding closest x,y,z points from x,y coordinates

I found my answer here: Finding index of nearest point in numpy arrays of x and y coordinates

and did some editing to make it fit on my problem.

import scipy
outer_points = [[1.44, 0.48, 0.600* 6],[-1.26, -1.02, 0.600* 6],[-1.26, 0.48, 0.600* 6],[1.44, -1.02, 0.600* 6]]
mytree = scipy.spatial.cKDTree(np.asarray(point_cloud.points))
dist, indexes = mytree.query(outer_points)
points_with_height = [np.asarray(point_cloud.points)[idx] for idx in indexes]

I needed the height of the corner points to do some trigonometry, so when I knew the four points, I had to figure out which is the top left, right and bottom left, right corners.

top_left = [0,0,0]
top_right = [0,0,0]
bottom_left = [0,0,0]
bottom_right = [0,0,0]
for point in points_with_height:
if point[0] < top_left[0] and point[1] > top_left[1]:
top_left = point
if point[0] > top_left[0] and point[1] > top_right[1]:
top_right = point
if point[0] < bottom_left[0] and point[1] < bottom_left[1]:
bottom_left = point
if point[0] > bottom_right[0] and point[1] < bottom_right[1]:
bottom_right = point

I don't think it's pretty, but it works. So if anyone has a more elegant way of doing this, then feel free to edit or comment.
Thanks for all the help, pointing me in the right direction.

Find closest k points for every point in row of numpy array

Construct a kdtree with scipy.spatial.cKDTree for each row of your data.

import numpy as np
import scipy.spatial

def nearest_neighbors(arr, k):
k_lst = list(range(k + 2))[2:] # [2,3]
neighbors = []

for row in arr:
# stack the data so each element is in its own row
data = np.vstack(row)
# construct a kd-tree
tree = scipy.spatial.cKDTree(data)
# find k nearest neighbors for each element of data, squeezing out the zero result (the first nearest neighbor is always itself)
dd, ii = tree.query(data, k=k_lst)
# apply an index filter on data to get the nearest neighbor elements
closest = data[ii].reshape(-1, k)
neighbors.append(closest)
return np.stack(neighbors)

N = 1000
k = 5
A = np.random.random((N, N))
nearest_neighbors(A, k)

How to find the closests points of two numpy arrays in python

using np.where(np.min(X)) doesn't give you the correct answer as min returns the minimum value (rather than the index of the minimum value) and where will return all nonzeros. I think what you are looking for is argmin:

from scipy.spatial import distance
ids = cord_id[np.argmin(distance.cdist(cord_only, cord_id[:,:-1]),axis=1)][:,-1]
new_arr = np.hstack([cord_only,ids.reshape(-1,1)])


Related Topics



Leave a reply



Submit