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 для выполнения поиска местоположения точки. Хотя эти N-D функции поддерживают 2-D и 3-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