Пространственный поиск
Введение
MATLAB® обеспечивает необходимые функции для выполнения пространственного поиска с помощью или Триангуляции Делоне или общей триангуляции. Поисковые запросы, которые поддержки MATLAB:
Поиск ближайшего соседа (иногда названный поиском самой близкой точки или поиском с расстоянием).
Поиск местоположения точки (иногда названный поиском точки в треугольнике или поиском точки в симплексе, где симплекс является треугольником, четырехгранником или более высоким размерным эквивалентом).
Учитывая набор точек X и точка запроса q в Евклидово пространстве, поиск ближайшего соседа определяет местоположение точки p в X, который ближе к q, чем к любой другой точке в X. Учитывая триангуляцию X, поиск местоположения точки определяет местоположение треугольника или четырехгранника, который содержит точку запроса q. Поскольку эти методы работают на оба Delaunay, а также общие триангуляции, можно использовать их, даже если модификация точек нарушает критерий Delaunay. Также можно искать общую триангуляцию, представленную в матричном формате.
В то время как MATLAB поддерживает эти поисковые схемы в размерностях N, точные пространственные поисковые запросы обычно становятся препятствующими, когда количество размерностей расширяет вне 3-D. Необходимо рассмотреть аппроксимированные альтернативы для больших проблем максимум в 10 размерностях.
Поиск ближайшего соседа
Существует несколько способов вычислить самых близких соседей в MATLAB, в зависимости от размерности проблемы:
Для 2D и 3-D поисковых запросов используйте метод
nearestNeighbor, предоставленный классомtriangulationи наследованный классомdelaunayTriangulation.Для 4-D и выше, используйте функцию
delaunayn, чтобы создать триангуляцию и дополнительную функциюdsearchn, чтобы выполнить поиск. В то время как эти функции N-D поддерживают 2D и 3-D, они не являются столь же общими и эффективными как методы поиска триангуляции.
Этот пример показывает, как выполнить поиск ближайшего соседа в 2D с delaunayTriangulation.
Начните путем создания случайного набора 15 точек.
X = [3.5 8.2; 6.8 8.3; 1.3 6.5; 3.5 6.3; 5.8 6.2; 8.3 6.5;... 1 4; 2.7 4.3; 5 4.5; 7 3.5; 8.7 4.2; 1.5 2.1; 4.1 1.1; ... 7 1.5; 8.5 2.75];
Постройте точки и добавьте аннотации, чтобы показать метки ID.
plot(X(:,1),X(:,2),'ob') hold on vxlabels = arrayfun(@(n) {sprintf('X%d', n)}, (1:15)'); Hpl = text(X(:,1)+0.2, X(:,2)+0.2, vxlabels, 'FontWeight', ... 'bold', 'HorizontalAlignment','center', 'BackgroundColor', ... 'none'); hold off
Создайте Триангуляцию Делоне из точек.
dt = delaunayTriangulation(X);
Создайте некоторые точки запроса, и для каждой точки запроса находят индекс ее соответствующего самого близкого соседа в X с помощью метода nearestNeighbor.
numq = 10;
rng(0,'twister');
q = 2+rand(numq,2)*6;
xi = nearestNeighbor(dt, q);Добавьте точки запроса в график и добавьте линейные сегменты, соединяющие точки запроса с их самыми близкими соседями.
xnn = X(xi,:); hold on plot(q(:,1),q(:,2),'or'); plot([xnn(:,1) q(:,1)]',[xnn(:,2) q(:,2)]','-r'); vxlabels = arrayfun(@(n) {sprintf('q%d', n)}, (1:numq)'); Hpl = text(q(:,1)+0.2, q(:,2)+0.2, vxlabels, 'FontWeight', ... 'bold', 'HorizontalAlignment','center', ... 'BackgroundColor','none'); hold off
Выполнение поиска ближайшего соседа в 3-D является прямым расширением 2D примера на основе delaunayTriangulation.
Для 4-D и выше, используйте delaunayn и функции dsearchn, как проиллюстрировано в следующем примере:
Создайте случайную выборку точек в 4-D и триангулируйте точки с помощью delaunayn:
X = 20*rand(50,4) -10; tri = delaunayn(X);
X с помощью функции dsearchn:q = rand(5,4); xi = dsearchn(X,tri, q)
nearestNeighbor и функция dsearchn позволяют Евклидову расстоянию между точкой запроса и его ближайшего соседа быть возвращенным как дополнительный аргумент. В 4-D примере можно вычислить расстояния, dnn, можно следующим образом:[xi,dnn] = dsearchn(X,tri, q)
Поиск местоположения точки
Поиск местоположения точки является алгоритмом поиска триангуляции, который определяет местоположение симплекса (треугольник, четырехгранник, и так далее) включение точки запроса. Как в случае поиска ближайшего соседа, существует несколько подходов к выполнению поиска местоположения точки в MATLAB, в зависимости от размерности проблемы:
Для 2D и 3-D, используйте основанный на классах подход с методом
pointLocation, предоставленным классомtriangulationи наследованным классомdelaunayTriangulation.Для 4-D и выше, используйте функцию
delaunayn, чтобы создать триангуляцию и дополнительную функциюtsearchn, чтобы выполнить поиск местоположения точки. Несмотря на то, что поддерживая 2D и 3-D, эти функции N-D не являются столь же общими и эффективными как методы поиска триангуляции.
Этот пример показывает, как использовать класс delaunayTriangulation, чтобы выполнить поиск местоположения точки в 2D.
Начните с набора 2D точек.
X = [3.5 8.2; 6.8 8.3; 1.3 6.5; 3.5 6.3; 5.8 6.2; ... 8.3 6.5; 1 4; 2.7 4.3; 5 4.5; 7 3.5; 8.7 4.2; ... 1.5 2.1; 4.1 1.1; 7 1.5; 8.5 2.75];
Создайте триангуляцию и постройте ее показывающий треугольные метки ID в центрах вписанной окружности треугольников.
dt = delaunayTriangulation(X); triplot(dt); hold on ic = incenter(dt); numtri = size(dt,1); trilabels = arrayfun(@(x) {sprintf('T%d', x)}, (1:numtri)'); Htl = text(ic(:,1), ic(:,2), trilabels, 'FontWeight', ... 'bold', 'HorizontalAlignment', 'center', 'Color', ... 'blue'); hold off
Теперь создайте некоторые точки запроса и добавьте их в график. Затем найдите индекс соответствующих треугольников включения с помощью метода pointLocation.
q = [5.9344 6.2363;
2.2143 2.1910;
7.0948 3.6615;
7.6040 2.2770;
6.0724 2.5828;
6.5464 6.9407;
6.4588 6.1690;
4.3534 3.9026;
5.9329 7.7013;
3.0271 2.2067];
hold on;
plot(q(:,1),q(:,2),'*r');
vxlabels = arrayfun(@(n) {sprintf('q%d', n)}, (1:10)');
Hpl = text(q(:,1)+0.2, q(:,2)+0.2, vxlabels, 'FontWeight', ...
'bold', 'HorizontalAlignment','center', ...
'BackgroundColor', 'none');
hold off
ti = pointLocation(dt,q);
Выполнение поиска местоположения точки в 3-D является прямым расширением выполнения поиска местоположения точки в 2D с delaunayTriangulation.
Для 4-D и выше, используйте delaunayn и функции tsearchn, как проиллюстрировано в следующем примере:
Создайте случайную выборку точек в 4-D и триангулируйте их использующий delaunayn:
X = 20*rand(50,4) -10; tri = delaunayn(X);
tsearchn:q = rand(5,4); ti = tsearchn(X,tri,q)
pointLocation и функция tsearchn позволяют соответствующим барицентрическим координатам быть возвращенными как дополнительный аргумент. В 4-D примере можно вычислить барицентрические координаты можно следующим образом:[ti,bc] = tsearchn(X,tri,q)