Searching for the numpy array ((x, y, z) ...) for z matching the closest x, y

I have a very large array, similar to the format height data:

triplets = ((x0, y0, z0), 
            (x1, y1, z1), 
            ... ,
            (xn, yn, zn))

where x, y, z are all floats in meters. You can create suitable test data that matches this format with

x = np.arange(20, 40, dtype=np.float64)
y = np.arange(30, 50, dtype=np.float64)
z = np.random.random(20) * 25.0
triplets = np.hstack((x, y, z)).reshape((len(x),3))

I want to be able to efficiently find the corresponding z value for a given pair (x, y). So far, my research leads to more questions. Here is what I have:

  • Iterate through all triplets:

    query = (a, b) # where a, b are the x and y coordinates we're looking for
    for i in triplets:
      if i[0] == query[0] and i[1] == query[1]:
        result = i[2]
    

    Disadvantages: slow; a, bmust exist, which is a problem when comparing floats.

  • Use scipy.spatial.cKDTreeto find the closest:

    points = triplets[:,0:2] # drops the z column
    tree = cKDTree(points)
    idx = tree.query((a, b))[1] # this returns a tuple, we want the index
    query = tree.data[idx]
    result = triplets[idx, 2]
    

    Disadvantages: returns the closest point, rather than interpolating.

  • Using interp2daccording to the comment:

    f = interp2d(x, y, z)
    result = f(a, b)
    

    : . OverflowError: Too many data points to interpolate . ( 11 .)

, : - , ? ?

+4
3

, z , , - :

  • k-d (x, y)
  • (xi, yi) k
  • z, (xi, yi)

:

import numpy as np
from scipy.spatial import cKDTree

# some fake (x, y, z) data
XY = np.random.rand(10000, 2) - 0.5
Z = np.exp(-((XY ** 2).sum(1) / 0.1) ** 2)

# construct a k-d tree from the (x, y) coordinates
tree = cKDTree(XY)

# a random point to query
xy = np.random.rand(2) - 0.5

# find the k nearest neighbours (say, k=3)
distances, indices = tree.query(xy, k=3)

# the z-values for the k nearest neighbours of xy
z_vals = Z[indices]

# take the average of these z-values, weighted by 1 / distance from xy
dw_avg = np.average(z_vals, weights=(1. / distances))

k, - . , k "", z-. k .

, , (xi, yi), , , z x, y. , (1 / distances ** 2), (1 / distances).

k-d . , , , (N, 2) tree.query().

, FLANN, , , .

+4

cKDTree, idx, for ? result = triplets[idx, 2].

from scipy.spatial import cKDTree

x = np.arange(20, 40, dtype=np.float64)
y = np.arange(30, 50, dtype=np.float64)
z = np.random.random(20) * 25.0
triplets = np.hstack((x, y, z)).reshape((len(x),3))

a = 30.1
b = 40.5

points = triplets[:,0:2] # drops the z column
tree = cKDTree(points)
idx = tree.query((a, b))[1] # this returns a tuple, we want the index
result = triplets[idx, 2]
+3

You can create a sparse matrix and use simple indexing.

In [1]: import numpy as np
In [2]: x = np.arange(20, 40, dtype=np.float64)
In [3]: y = np.arange(30, 50, dtype=np.float64)
In [4]: z = np.random.random(20) * 25.0
In [9]: from scipy.sparse import coo_matrix
In [12]: m = coo_matrix((z, (x, y))).tolil()
In [17]: m[25,35]
Out[17]: 17.410532044604292
0
source

Source: https://habr.com/ru/post/1541335/


All Articles