Как найти ближайшую точку к линии?

Question

Облако точек хранится в виде массива numpy. Через это облако точек также проходит линия, обозначенная двумя точками.

Как я могу получить самую близкую точку к этой линии в самой оптимизированной версии?

Я вычислил расстояние до каждой точки одну за другой, но вычисление этого занимает много времени, и мое приложение зависает ....

Пожалуйста, помогите мне оптимизировать это; (

Вот как я делал это для каждой точки:

def isectSphere(self, p0, p1, cpt):

        # normalized ray direction
        r_dir = np.subtract(p0, p1)
        r_dir = r_dir / np.linalg.norm(r_dir)

        # nearest point on the ray to the sphere
        p0_cpt = np.subtract(p0, cpt)
        near_pt = np.subtract(p0, r_dir * np.dot(p0_cpt, r_dir))

        # distance to center point
        return np.linalg.norm(np.subtract(near_pt, cpt))

После итерации этого кода в каждой точке a вынимал из нее минимальное значение.

In Облако точек составляет около 6 000 000 точек.

Answer 1

Вы можете использовать векторизованные вычисления:

Предполагая, что p0 и p1 имеют форму (m,), а pc - это ваш массив облаков точек формы (N, m), вы можете использовать np.cross чтобы вычислить векторизованное расстояние:

closest_point = pc[np.argmin(np.linalg.norm(np.cross(p1-p0, p0-pc, axisb=1), axis=1)/np.linalg.norm(p1-p0))]

Это в персональной системе занимает менее секунды для более чем 6 000 000 точек.

Answer 2

import numpy as np


def isectSphere(p0, p1, cloud):
        """
        >>> isectSphere([1, 0], [3, 0], [[0, -4], [2, 3]])
        1
        >>> isectSphere([1, 0, 0], [3, 0, 0], [[0, -4, 0], [2, 3, 0]])
        1
        """
        p0 = np.asarray(p0)
        p1 = np.asarray(p1)
        cloud = np.asarray(cloud)
        product = np.cross(cloud - p0, p1 - p0)
        if product.ndim == 2:
            distances = np.linalg.norm(product, axis=1)
        else:
            distances = np.abs(product)
        return distances.argmin()