евклидово расстояние для каждой точки в облаке точек

Question

Я хочу вычислить минимальное евкидово расстояние между каждой точкой в ​​одном облаке точек и всеми другими точками во втором облаке точек.
Мои облака точек называются pc1 и pc2.Np - матрица нормальных векторов для каждой точки.

sofar Я использую следующий код:

dist = zeros(size(pc2,1),1);
sign = zeros(size(pc2,1),1);

for i = 1:size(pc2,1)
     d = (pc1(:,1)-pc2(i,1)).^2 + (pc1(:,2)-pc2(i,2)).^2 + (pc1(:,3) - pc2(i,3)).^2;
    [d, ind] = min(d);
    dist(i,1) = sqrt(d);
    sign(i,1) = Np(ind,:)*(pc2(i,:)-pc1(ind,:))';
end

последний бит со «знаком» от этой бумаги.Я добавил его, потому что хочу знать, лежит ли моя точка внутри или за пределами другого облака точек.(Я получил облака точек из файлов STL, и они представляют поверхности)

Так как я работаю с довольно большими облаками точек от 200 000 до 3 000 000 точек, вычисление занимает некоторое время, и мне было интересно, может ли кто-нибудь предложить оптимизациюдля моего кода.Может быть, это может быть векторизация, и я не вижу этого.
Все ваши предложения приветствуются.Заранее благодарим вас за ваше время и помощь.

edit: просто чтобы прояснить.Каждая строка в моей матрице облака точек - это точка.первый столбец - это x-, второй - y, третий - значение z.

Answer 1

Другой альтернативой является использование KdTree .Это также подход PCL .

При таком подходе вы в основном создаете KdTree из облака опорных точек, а затем выполняете поиск ближайшего соседа для каждой точки из облака точек запроса.

Этот подход будет на величины быстрее, чем метод грубой силы.

Answer 2

Вы, безусловно, можете сделать это в векторизованной форме, используйте pdist2 и min, как показано ниже.

dmat = pdist2(pc1, pc2);
[dist, ind] = min(dmat);

Я полагаю, что следующее будет работать для знака, но вы должны проверить результаты.Возможно, придется немного подправить в зависимости от формы матрицы.

sign = sum(Np(ind,:).*(pc2-pc1(ind,:)), 2);