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

Введение

MATLAB^® предоставляет необходимые функции для выполнения пространственного поиска с использованием триангуляции Делоне или общей триангуляции. Ниже перечислены поисковые запросы, поддерживаемые MATLAB:

Учитывая набор точек X и точку запроса q в евклидовом пространстве поиск по ближайшему соседу находит точку p в X что ближе к q чем в любую другую точку в X. Учитывая триангуляцию Xпоиск местоположения точки определяет местоположение треугольника или тетраэдра, содержащего точку запроса q. Поскольку эти методы работают как для Делоне, так и для общих триангуляций, можно использовать их, даже если изменение точек нарушает критерий Делоне. Можно также искать общую триангуляцию, представленную в матричном формате.

В то время как MATLAB поддерживает эти схемы поиска в N размерности, точные пространственные поиски обычно становятся запретительными, так как количество измерений выходит за пределы 3-D. Вы должны рассмотреть приблизительные альтернативы для больших задач в до 10 размерностях.

Поиск по ближайшему соседу

Существует несколько способов вычисления ближайших соседей в MATLAB, в зависимости от размерности задачи:

В этом примере показано, как выполнить поиск по ближайшему соседу в 2-D с 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];

Постройте графики точек и добавьте аннотации для отображения меток идентификаторов.

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 является прямым расширением 2-D примера, основанного на delaunayTriangulation.

Для 4-D и выше используйте delaunayn и dsearchn функции, проиллюстрированные в следующем примере:

Создайте случайную выборку точек в 4-D и триангулируйте точки используя delaunayn:

X = 20*rand(50,4) -10;
tri = delaunayn(X);

q = rand(5,4);
xi = dsearchn(X,tri, q)

[xi,dnn] = dsearchn(X,tri, q)

Поиск местоположения точки

Поиск местоположения точки является алгоритмом поиска триангуляции, который находит симплекс (треугольник, тетраэдр и так далее), заключающий в себя точку запроса. Как и в случае поиска по ближайшему соседу, существует несколько подходов к выполнению поиска по местоположению точки в MATLAB, в зависимости от размерности задачи:

В этом примере показано, как использовать delaunayTriangulation класс, чтобы выполнить поиск местоположения точки в 2-D.

Начнем с набора 2-D точек.

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];

Создайте триангуляцию и постройте график с указанием меток идентификаторов треугольников в центрах вписанной окружности треугольников.

 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 является прямым расширением выполнения поиска местоположения точки в 2-D с delaunayTriangulation.

Для 4-D и выше используйте delaunayn и tsearchn функции, проиллюстрированные в следующем примере:

Создайте случайную выборку точек в 4-D и триангулируйте их с помощью delaunayn:

X = 20*rand(50,4) -10;
tri = delaunayn(X);

q = rand(5,4);
ti = tsearchn(X,tri,q)

[ti,bc] = tsearchn(X,tri,q)