Interpolate неструктурированных X, Y, данные Z по лучшей сетке на основе ближайших соседей расстояния для каждой точек

Question

Этот вопрос был отредактированных после ответов на окончательное решение шоу я использовал

У меня есть неструктурированные 2D наборов данных, поступающих из различных источников, как, например,: Данные наборов данных 3 numpy.ndarray (координаты X, Y и значение Z).

Моя конечная цель - интерполировать данные тезисов на сетку для преобразования в изображение/матрицу. Итак, мне нужно найти «наилучшую сетку» для интерполяции данных тезисов. И для этого мне нужно найти лучшие шаги X и Y между пикселями этой сетки.

Наличного шаг на основе евклидова расстояния между точками:

Используйте средние евклидов расстояний между каждой точкой и ее ближайшим соседом.

• Использование KDTree/cKDTree из scipy.spacial для построения дерева X, Y DATAS.
• Используйте метод query с k=2 для получения расстояний (если k=1, расстояния равны нулю, потому что запрос для каждой найденной точки).

    # Generate KD Tree 
    xy = np.c_[x, y] # X,Y data converted for use with KDTree 
    tree = scipy.spacial.cKDTree(xy) # Create KDtree for X,Y coordinates. 

    # Calculate step 
    distances, points = tree.query(xy, k=2) # Query distances for X,Y points 
    distances = distances[:, 1:] # Remove k=1 zero distances 
    step = numpy.mean(distances) # Result 

подстройка Производительность:

• Использование scipy.spatial.cKDTree и не scipy.spatial.KDTree, потому что это действительно быстрее.
• Использование balanced_tree=False с scipy.spatial.cKDTree: Большая скорость в моем случае, но может быть неверной для всех данных.
• Используйте n_jobs=-1 с cKDTree.query для использования многопоточности.
• Использование p=1 с cKDTree.query для использования Манхэттенское расстояние вместо евклидова расстояния (p=2): Быстрее, но может быть менее точным.
• Запросить расстояние только для случайной подвыборки точек: Большая скорость с большими наборами данных, но может быть менее точной и менее повторяемой.

интерполировать точки на сетке:

Interpolate набор данных точек на сетке, используя просчитанный шаг.

    # Generate grid 
    def interval(axe): 
     '''Return numpy.linspace Interval for specified axe''' 
     cent = axe.min() + axe.ptp()/2 # Interval center 
     nbs = np.ceil(axe.ptp()/step) # Number of step in interval 
     hwid = nbs * step/2 # Half interval width 
     return np.linspace(cent - hwid, cent + hwid, nbs) # linspace 

    xg, yg = np.meshgrid(interval(x), interval(y)) # Generate grid 

    # Interpolate X,Y,Z datas on grid 
    zg = scipy.interpolate.griddata((x, y), z, (xg, yg)) 

Набора NaN, если пиксель слишком далеко от точек инициалов:

Набора NaN в пиксели из сетки, которые слишком далеко (Расстояние> шаг) из точек от начального X, Y, Z данных. Используется предыдущий созданный KDTree.

    # Calculate pixel to X,Y,Z data distances 
    dist, _ = tree.query(np.c_[xg.ravel(), yg.ravel()]) 
    dist = dist.reshape(xg.shape) 

    # Set NaN value for too far pixels 
    zg[dist > step] = np.nan 

Answer 1

Предлагаю вам пойти с KDTree.query.

Вы ищете из carachteristic расстояния масштабировать биннинг: Я предлагаю вам взять только случайное подмножество ваших точек и использовать Манхэттен расстояния, еще потому KDTree.query очень медленно (и все же это сложность * log (n)).

Вот мой код:

# CreateTree 
tree=scipy.spatial.KDTree(numpy.array(points)) # better give it a copy? 
# Create random subsample of points 
n_repr=1000 
shuffled_points=numpy.array(points) 
numpy.random.shuffle(shuffled_points) 
shuffled_points=shuffled_points[:n_repr] 
# Query the tree 
(dists,points)=tree.query(shuffled_points,k=2,p=1) 
# Get _extimate_ of average distance: 
avg_dists=numpy.average(dists) 
print('average distance Manhattan with nearest neighbour is:',avg_dists) 

Я предлагаю вам использовать Манхэттен расстояние (https://en.wikipedia.org/wiki/Taxicab_geometry), потому что это было быстрее вычислить, чем расстояние евклидовой. А так как вам нужна только оценка среднего расстояния, этого должно быть достаточно.

Answer 2

Проблема, которую вы хотите решить, называется проблемой «все ближайшие соседи». См. Эту статью, например: http://link.springer.com/article/10.1007/BF02187718

Я считаю, что решениями являются O (N log N), поэтому в том же порядке, что и KDTree.query, но на практике намного, намного быстрее, чем куча отдельных запросов. Извините, я не знаю о реализации python этого.