Найти ближайшую точку в сетке Matlab

Обычный метод - пойти:

for every blue point {
    for every red point {
        is this the closest so far
    }
}

Но лучший способ — поместить красные данные в дерево kd. Это дерево, которое разбивает данные по их среднему значению, затем разбивает два набора данных по их среднему значению и т. д., пока вы не разделите их в древовидную структуру.

Это изменит эффективность поиска с O(n*m) до O(log(n)*m).

Вот библиотека:

http://www.mathworks.com.au/matlabcentral/fileexchange/4586-kd-tree

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

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

Убедитесь, что самый большой набор данных (в данном случае ваши красные точки) входит в дерево, так как это обеспечит наибольшее сокращение времени.

Я думаю, что нашел способ сделать это, используя флаг nearest для griddata.

Я создаю матрицу того же размера, что и матрицы сетки x и y, но заполняемую линейными индексами соответствующего элемента матрицы. Это формируется путем изменения формы вектора (который равен 1:size(x,1)*size(x,2)) до тех же размеров, что и x.

Затем я использую griddata и флаг nearest, чтобы найти линейный индекс точки, ближайшей к каждой точке моего контура (синие точки). Затем, простое преобразование обратно в нотацию индекса с помощью ind2sub оставляет мне 2 вектора-строки, описывающие индексы матрицы для точек, ближайших к каждой точке на контуре с синими точками.

На приведенном ниже графике показан контур (синие точки), сетка (красные точки) и ближайшие точки сетки (зеленые точки).

Это фрагмент кода, который я использовал:

index_matrix1 = 1:size(x,1)*size(x,2); 
index_matrix1 = reshape(index_matrix1,size(x));
lin_ind = griddata(x,y,index_matrix1,CX,CY,'nearest'); % where CX and CY are the coords of the contour
[sub_ind(1,:),sub_ind(2,:)] = ind2sub(size(x),lin_ind);

Я предполагаю, что в стереографическом представлении ваши точки образуют аккуратную сетку в координатах r-theta. (Я не слишком знаком с этим, так что поправьте меня, если я ошибаюсь. Мое предложение все еще может быть применимо).

Для построения вы конвертируете из стереографического изображения в широту-долготу, что искажает сетку. Однако для нахождения ближайшей точки рассмотрите возможность преобразования широты и долготы точек синего контура в стереографические координаты, где легко определить ячейку для каждой точки, используя ее значения r и theta.

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

Основное требование состоит в том, что при некотором преобразовании узлы сетки определяются двумя векторами, X и Y, так что для любых x в X и y в Y (x, y) является точкой сетки. Затем преобразуйте сетку и точки контура с помощью этого преобразования. Затем, учитывая произвольную точку (x1, y1), мы можем найти соответствующую ячейку сетки, найдя ближайшую точку x к x1 и ближайшую точку y к y1. Преобразуйте обратно, чтобы получить точки в нужной системе координат.

dsearchn: Поиск ближайшей точки N-D.

[k, d] = dsearchn(A,B) : возвращает расстояния d до ближайших точек. d является вектор-столбцом длины p.

http://au.mathworks.com/help/matlab/ref/dsearchn.html?s_tid=gn_loc_drop