Пространственный поиск

Введение

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)

Барицентрические координаты полезны для выполнения линейной интерполяции. Эти координаты предоставляют вам веса, которые можно использовать, чтобы масштабировать значения в каждой вершине симплекса включения. См. Интерполяцию данных, имеющих разброс, для получения дальнейшей информации.

Документация