MATLAB® предоставляет необходимые функции для выполнения пространственного поиска с использованием триангуляции Делоне или общей триангуляции. Ниже перечислены поисковые запросы, поддерживаемые MATLAB:
Поиск по ближайшему соседу (иногда называется поиском по ближайшей точке или поиском близости).
Поиск местоположения точки (иногда называемый поиском точка в треугольнике или поиском точка в симплексе, где симплекс является треугольником, тетраэдром или более высоким размерным эквивалентом).
Учитывая набор точек X и точку запроса q в евклидовом пространстве поиск по ближайшему соседу находит точку p в X что ближе к q чем в любую другую точку в X. Учитывая триангуляцию Xпоиск местоположения точки определяет местоположение треугольника или тетраэдра, содержащего точку запроса q. Поскольку эти методы работают как для Делоне, так и для общих триангуляций, можно использовать их, даже если изменение точек нарушает критерий Делоне. Можно также искать общую триангуляцию, представленную в матричном формате.
В то время как MATLAB поддерживает эти схемы поиска в N размерности, точные пространственные поиски обычно становятся запретительными, так как количество измерений выходит за пределы 3-D. Вы должны рассмотреть приблизительные альтернативы для больших задач в до 10 размерностях.
Существует несколько способов вычисления ближайших соседей в MATLAB, в зависимости от размерности задачи:
Для 2-D и 3-D поиска используйте nearestNeighbor метод, предоставленный triangulation класс и унаследованный delaunayTriangulation класс.
Для 4-D и выше используйте delaunayn функция для построения триангуляции и комплементарной dsearchn функция для выполнения поиска. Хотя эти N-D функции поддерживают 2-D и 3-D, они не такие общие и эффективные, как методы поиска триангуляции.
В этом примере показано, как выполнить поиск по ближайшему соседу в 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);
X использование dsearchn функция:q = rand(5,4); xi = dsearchn(X,tri, q)
nearestNeighbor метод и dsearchn функция позволяет вернуть евклидово расстояние между точкой запроса и ее ближайшим соседом в качестве необязательного аргумента. В 4-D примере можно вычислить расстояния, dnn, следующим образом:[xi,dnn] = dsearchn(X,tri, q)
Поиск местоположения точки является алгоритмом поиска триангуляции, который находит симплекс (треугольник, тетраэдр и так далее), заключающий в себя точку запроса. Как и в случае поиска по ближайшему соседу, существует несколько подходов к выполнению поиска по местоположению точки в MATLAB, в зависимости от размерности задачи:
Для 2-D и 3-D используйте основанный на классах подход с pointLocation метод, предоставленный triangulation класс и унаследованный delaunayTriangulation класс.
Для 4-D и выше используйте delaunayn функция для построения триангуляции и комплементарной tsearchn функция для выполнения поиска по местоположению точки. Несмотря на поддержку 2-D и 3-D, эти N-D функции не такие общие и эффективные, как методы поиска триангуляции.
В этом примере показано, как использовать 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);
tsearchn функция:q = rand(5,4); ti = tsearchn(X,tri,q)
pointLocation метод и tsearchn функция позволяет возвращать соответствующие барицентрические координаты в качестве необязательного аргумента. В 4-D примере можно вычислить барицентрические координаты следующим образом:[ti,bc] = tsearchn(X,tri,q)
delaunay | delaunayn | delaunayTriangulation | dsearchn | nearestNeighbor | pointLocation | triangulation | triangulation | tsearchn