Упорядочить и подобрать 3d-точки в координатной сетке с Numpy

Question

У меня есть список 3d очков, таких как

np.array([
    [220, 114, 2000],
    [125.24, 214, 2519],
    ...
    [54.1, 254, 1249]
])

Точки не в значимом порядке. Я хотел бы отсортировать и изменить форму массива так, чтобы он лучше представлял координатную сетку (чтобы у меня были известные ширина и высота и я мог получить значения Z по индексу). Я также хотел бы уменьшить выборку точек, скажем, целых чисел для обработки столкновений. Применение минимума, максимума или среднего значения во время нисходящей выборки.

Я знаю, что могу сэмплировать массив 1d, используя np.mean и np.shape

Подход, который я сейчас использую, находит минимальное и максимальное значения в X, Y, а затем помещает значения Z в двумерный массив, выполняя при этом дискретизацию вручную.

Это многократно повторяет гигантский массив, и мне интересно, есть ли способ сделать это с помощью np.meshgrid или какой-нибудь другой функциональности, которую я пропускаю.

Спасибо

Answer 1

Вы можете использовать метод binning из Самый эффективный способ сортировки массива по бинам, заданным индексным массивом? Чтобы получить индексный массив из y,x координат, вы можете использовать np.searchsorted и np.ravel_multi_index

Вот пример реализации, модуль stb - это код из связанного поста.

import numpy as np
from stb import sort_to_bins_sparse as sort_to_bins

def grid1D(u, N):
    mn, mx = u.min(), u.max()
    return np.linspace(mn, mx, N, endpoint=False)

def gridify(yxz, N):
    try:
        Ny, Nx = N
    except TypeError:
        Ny = Nx = N
    y, x, z = yxz.T
    yg, xg = grid1D(y, Ny), grid1D(x, Nx)
    yidx, xidx = yg.searchsorted(y, 'right')-1, xg.searchsorted(x, 'right')-1
    yx = np.ravel_multi_index((yidx, xidx), (Ny, Nx))
    zs = sort_to_bins(yx, z)
    return np.concatenate([[0], np.bincount(yx).cumsum()]), zs, yg, xg

def bin(yxz, N, binning_method='min'):
    boundaries, binned, yg, xg = gridify(yxz, N)
    result = np.full((yg.size, xg.size), np.nan)
    if binning_method == 'min':
        result.reshape(-1)[:len(boundaries)-1] = np.minimum.reduceat(binned, boundaries[:-1])
    elif binning_method == 'max':
        result.reshape(-1)[:len(boundaries)-1] = np.maximum.reduceat(binned, boundaries[:-1])
    elif binning_method == 'mean':
        result.reshape(-1)[:len(boundaries)-1] = np.add.reduceat(binned, boundaries[:-1]) / np.diff(boundaries)
    else:
        raise ValueError
    result.reshape(-1)[np.where(boundaries[1:] == boundaries[:-1])] = np.nan
    return result

def test():
    yxz = np.random.uniform(0, 100, (100000, 3))
    N = 20
    boundaries, binned, yg, xg = gridify(yxz, N)
    binmin = bin(yxz, N)
    binmean = bin(yxz, N, 'mean')
    y, x, z = yxz.T
    for i in range(N-1):
        for j in range(N-1):
            msk = (y>=yg[i]) & (y<yg[i+1]) & (x>=xg[j]) & (x<xg[j+1])
            assert (z[msk].min() == binmin[i, j]) if msk.any() else np.isnan(binmin[i, j])
            assert np.isclose(z[msk].mean(), binmean[i, j]) if msk.any() else np.isnan(binmean[i, j])