Оптимизация алгоритма поиска ближайших объектов

[bamasa]

Есть следующее предложение. Сейчас мы считаем reward и check_collision вычисляя Евклидово расстояние до всех объектов и беря минимальные. Используется следующая функция:

def euclidean_distance(xyz_main, xyz_other, rev_sort=True):
    """ Return array of (reverse sorted) Euclidean distances between main object and other
    Args:
        xyz_main: np.array shape (1, 3) - coordinates of main object
        xyz_other: np.array shape (n_objects, 3) - coordinates of other object
    Returns:
        np.array shape (n_objects)
    """
    # distances array
    distances = np.sum(
        (xyz_main - xyz_other) ** 2,
        axis=1) ** 0.5
    if rev_sort:
        distances = np.sort(distances)[::-1]
    return distances

Просчитывать все объекты долго. Предлагаю определить опасную область, и считать расстояние только для объектов в этой области. Тогда мы сможем делать это не сразу по всем координатам, а поочередно. Такой алгоритм явно быстрее и простой (идея из kd-дерева).

В связи с этим вопрос - какого размера, примерно, должна быть такая область и есть ли какие-то замечания по предложенному методу?

[kazeevn]

Предлагаю отложить. Пока планируется <10 объектов, расчёт расстояний скорее всего будет занимать небольшую часть от общего времени (можно проверить профайлером!), плюс я не уверен, что при таком числе объектов накладные расходы на сложную структуру данных будут того стоить.

[kazeevn]

Решили отложить много объектов.

[bamasa]

Решили отложить много объектов.

@kazeevn , у нас будет один debris?

[kazeevn]

Пока планируется <10 объектов, расчёт расстояний скорее всего будет занимать небольшую часть от общего времени (можно проверить профайлером!), плюс я не уверен, что при таком числе объектов накладные расходы на сложную структуру данных будут того стоить.