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

Использование функций delaunay и delaunayn

delaunay и delaunayn функции берут набор точек и создают триангуляцию в матричном формате. Для получения дополнительной информации об этой структуре данных см. Формат Triangulation Matrix. В 2-D, delaunay функция часто используется для создания триангуляции, которая может использоваться для построения графика поверхности, заданной в терминах множества данного , имеющего разброса точек. В этом приложении важно отметить, что этот подход может использоваться только в том случае, если поверхность является односторонней. Для примера его нельзя использовать для построения графика сферической поверхности, поскольку существует два z значения, соответствующие одной (x, y) координата. Простой пример демонстрирует, как delaunay функция может использоваться, чтобы построить график поверхности, представляющей выборочным данным набор.

В этом примере показано, как использовать delaunay функция для создания 2-D триангуляции Делоне из набора данных подводной точки. Подводная гора - подводная гора. Набор данных состоит из набора долготы (x) и широта (y) местоположения и соответствующие повышения подводных гор (z) измеряется в этих координатах.

Загрузите набор данных подводной горы и просмотрите (x, y) данные как график поля точек.

load seamount
plot(x,y,'.','markersize',12)
xlabel('Longitude'), ylabel('Latitude')
grid on

Создайте триангуляцию Делоне из этого набора точек и используйте triplot для построения графика триангуляции на существующем рисунке.

tri = delaunay(x,y);
hold on, triplot(tri,x,y), hold off

Добавьте данные о глубине (z) для подъема вершин и создания поверхности. Создайте новый рисунок и используйте trimesh для построения графика поверхности в каркасном режиме.

figure
hidden on
trimesh(tri,x,y,z)
xlabel('Longitude'),ylabel('Latitude'),zlabel('Depth in Feet');

Если необходимо построить график поверхности в заштрихованном режиме, используйте trisurf вместо trimesh.

3-D Триангуляции Делоне также могут быть созданы с помощью delaunay функция. Эта триангуляция состоит из тетраэдров.

В этом примере показано, как создать 3-D триангуляцию Делоне набора случайных данных. Триангуляция строится с помощью tetramesh, и FaceAlpha опция добавляет прозрачность графику.

rng('default')
X = rand([30 3]);
tet = delaunay(X);
faceColor  = [0.6875 0.8750 0.8984];
tetramesh(tet,X,'FaceColor', faceColor,'FaceAlpha',0.3);

MATLAB обеспечивает delaunayn функция для поддержки создания триангуляций Делоне в размерности 4-D и выше. Две дополнительные функции tsearchn и dsearchn также предусмотрены для поддержки пространственного поиска для N-D триангуляций. Смотрите Пространственный поиск для получения дополнительной информации об основанном на триангуляции поиске.

Использование класса delaunayTriangulation

The delaunayTriangulation класс предоставляет другой способ создать триангуляции Делоне в MATLAB. В то время как delaunay и delaunayTriangulation использовать тот же базовый алгоритм и производить ту же триангуляцию, delaunayTriangulation предоставляет дополнительные методы, которые полезны для разработки основанных на Delaunay алгоритмов. Эти методы аналогичны функциям, которые упаковываются вместе с данными триангуляции в контейнер, называемый классом. Сохранение всего вместе в классе обеспечивает более организованную настройку, которая улучшает простоту использования. Это также улучшает эффективность основанных на триангуляции поисков, таких как местоположение точки и ближайший соседний. delaunayTriangulation поддерживает пошаговое редактирование триангуляции Делоне. Можно также наложить ограничения на ребра в 2-D.

Представления триангуляции вводят triangulation класс, который поддерживает топологические и геометрические запросы для 2-D и 3-D триангуляций. A delaunayTriangulation является особым видом triangulation. Это означает, что вы можете выполнить любое triangulation запрос на delaunayTriangulation в дополнение к специфичным для Delaunay запросам. В более формальных языковых терминах MATLAB, delaunayTriangulation является подклассом triangulation.

В этом примере показано, как создать, запросить и изменить триангуляцию Делоне из seamount данные с использованием delaunayTriangulation. Набор данных подводной горы содержит (x, y) местоположения и соответствующие повышения (z) которые определяют поверхность подводной гряды.

Загрузите и триангулируйте (x, y) данные.

load seamount
DT = delaunayTriangulation(x,y)

DT = 
  delaunayTriangulation with properties:

              Points: [294x2 double]
    ConnectivityList: [566x3 double]
         Constraints: []

The Constraints свойство пустое, поскольку нет никаких наложенных ограничений на ребро. The Points свойство представляет координаты вершин, и ConnectivityList свойство представляет треугольники. Вместе эти два свойства определяют матричные данные для триангуляции.

The delaunayTriangulation класс является оберткой вокруг матричных данных, и он предлагает набор дополнительных методов. Вы получаете доступ к свойствам в delaunayTriangulation таким же образом вы получаете доступ к полям struct.

Доступ к данным вершины.

DT.Points;

Доступ к данным о возможности подключения.

DT.ConnectivityList;

Доступ к первому треугольнику в ConnectivityList свойство.

DT.ConnectivityList(1,:)

ans = 1×3

   205   230   262

delaunayTriangulation обеспечивает простой способ индексации в ConnectivityList матрица свойств.

Доступ к первому треугольнику.

DT(1,:)

ans = 1×3

   205   230   262

Исследуйте первую вершину первого треугольника.

DT(1,1)

ans = 205

Исследуйте все треугольники в триангуляции.

DT(:,:);

Индексация в delaunayTriangulation выход, DT, работает как индексация в вывод массива триангуляции от delaunay. Между ними различие дополнительные методы, которые можно вызвать DT (например, nearestNeighbor и pointLocation).

Использование triplot для построения графика delaunayTriangulation. The triplot функция не является delaunayTriangulation метод, но он принимает и может построить delaunayTriangulation.

triplot(DT); 
axis equal
xlabel('Longitude'), ylabel('Latitude')
grid on

Также можно использовать triplot(DT(:,:), DT.Points(:,1), DT.Points(:,2)); чтобы получить тот же график.

Используйте delaunayTriangulation метод, convexHull, чтобы вычислить выпуклую оболочку и добавить его к графику. Поскольку у вас уже есть триангуляция Делоне, этот метод позволяет вам выводить выпуклую оболочку более эффективно, чем полный расчет с помощью convhull.

hold on
k = convexHull(DT);
xHull = DT.Points(k,1);
yHull = DT.Points(k,2);
plot(xHull,yHull,'r','LineWidth',2); 
hold off

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

Отредактируйте триангуляцию, чтобы удалить точки на выпуклую оболочку из предыдущих расчетов.

figure
plot(xHull,yHull,'r','LineWidth',2); 
axis equal
xlabel('Longitude'),ylabel('Latitude')
grid on

% The convex hull topology duplicates the start and end vertex.
% Remove the duplicate entry.
k(end) = [];

% Now remove the points on the convex hull.
DT.Points(k,:) = []

DT = 
  delaunayTriangulation with properties:

              Points: [274x2 double]
    ConnectivityList: [528x3 double]
         Constraints: []

% Plot the new triangulation.
hold on
triplot(DT); 
hold off

Существует одна вершина, которая находится как раз внутри контура выпуклой оболочки, который не был удален. Тот факт, что это внутренняя часть корпуса, можно увидеть с помощью инструмента Zoom-In на рисунке. Можно построить график меток вершин, чтобы определить индекс этой вершины и удалить ее из триангуляции. Также можно использовать nearestNeighbor способ для более легкой идентификации индекса.

Точка близка к местоположению (211,6, -48,15). Используйте метод nearestNeighbor, чтобы найти ближайшую вершину.

vertexId = nearestNeighbor(DT, 211.6, -48.15)

vertexId = 50

Теперь удалите эту вершину из триангуляции.

DT.Points(vertexId,:) = []

DT = 
  delaunayTriangulation with properties:

              Points: [273x2 double]
    ConnectivityList: [525x3 double]
         Constraints: []

Постройте график новой триангуляции.

figure
plot(xHull,yHull,'r','LineWidth',2); 
axis equal
xlabel('Longitude'),ylabel('Latitude')
grid on
hold on
triplot(DT); 
hold off

Добавьте точки к существующей триангуляции. Добавьте 4 точки, чтобы сформировать прямоугольник вокруг триангуляции.

Padditional = [210.9 -48.5; 211.6 -48.5; ...
     211.6 -47.9; 210.9 -47.9];
DT.Points(end+(1:4),:) = Padditional

DT = 
  delaunayTriangulation with properties:

              Points: [277x2 double]
    ConnectivityList: [548x3 double]
         Constraints: []

Закройте все существующие рисунки.

close all

Постройте график новой триангуляции.

figure
plot(xHull,yHull,'r','LineWidth',2); 
axis equal
xlabel('Longitude'),ylabel('Latitude')
grid on
hold on
triplot(DT); 
hold off

Можно отредактировать точки в триангуляции, чтобы переместить их в новое место. Отредактируйте первый из дополнительного набора точек (вершина ID 274).

DT.Points(274,:) = [211 -48.4];

Закройте все существующие рисунки.

close all

Постройте график новой триангуляции

figure
plot(xHull,yHull,'r','LineWidth',2); 
axis equal
xlabel('Longitude'),ylabel('Latitude')
grid on
hold on
triplot(DT); 
hold off

Используйте метод triangulation класс, vertexAttachments, чтобы найти прикрепленные треугольники. Поскольку количество треугольников, присоединенных к вершине, является переменным, метод возвращает присоединенные идентификаторы треугольников в массиве ячеек. Вам нужны скобки, чтобы извлечь содержимое.

attTris = vertexAttachments(DT,274);
hold on
triplot(DT(attTris{:},:),DT.Points(:,1),DT.Points(:,2),'g')
hold off

delaunayTriangulation также может использоваться, чтобы триангулировать точки в трехмерном пространстве. Получившаяся триангуляция состоит из тетраэдров.

В этом примере показано, как использовать delaunayTriangulation чтобы создать и построить график триангуляции 3-D точек.

rng('default')
P = rand(30,3);
DT = delaunayTriangulation(P)

DT = 
  delaunayTriangulation with properties:

              Points: [30x3 double]
    ConnectivityList: [102x4 double]
         Constraints: []

faceColor  = [0.6875 0.8750 0.8984];
tetramesh(DT,'FaceColor', faceColor,'FaceAlpha',0.3);

The tetramesh графики функций как внутренних, так и внешних граней триангуляции. Для триангуляций больших 3-D построение графиков внутренних граней может быть ненужным использованием ресурсов. График контура может быть более подходящим. Можно использовать freeBoundary метод получения граничной триангуляции в матричном формате. Затем передайте результат в trimesh или trisurf.

Ограниченная триангуляция Делоне

The delaunayTriangulation класс позволяет вам ограничивать ребра в 2-D триангуляции. Это означает, что вы можете выбрать пару точек в триангуляции и ограничить ребро, чтобы соединить эти точки. Вы можете представить это как «принудительное» ребро между одной или несколькими парами точек. В следующем примере показано, как ограничения ребра могут повлиять на триангуляцию.

Триангуляция ниже является триангуляцией Делоне, потому что она уважает критерий пустой окружности.

Триангулируйте набор точек с ограничением ребра, заданным между вершинами V1 и V3.

Задайте набор точек.

P = [2 4; 6 1; 9 4; 6 7];

Задайте ограничение, C, между V1 и V3.

C = [1 3];
DT = delaunayTriangulation(P,C);

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

triplot(DT)

% Label the vertices.
hold on
numvx = size(P,1);
vxlabels = arrayfun(@(n) {sprintf('V%d', n)}, (1:numvx)');
Hpl = text(P(:,1)+0.2, P(:,2)+0.2, vxlabels, 'FontWeight', ...
  'bold', 'HorizontalAlignment','center', 'BackgroundColor', ...
  'none');
hold off


% Use the incenters to find the positions for placing triangle labels on the plot.
hold on
IC = incenter(DT);
numtri = size(DT,1);
trilabels = arrayfun(@(P) {sprintf('T%d', P)}, (1:numtri)');
Htl = text(IC(:,1),IC(:,2),trilabels,'FontWeight','bold', ...
'HorizontalAlignment','center','Color','blue');
hold off

% Plot the circumcircle associated with the triangle, T1.
hold on
[CC,r] = circumcenter(DT);
theta = 0:pi/50:2*pi;
xunit = r(1)*cos(theta) + CC(1,1);
yunit = r(1)*sin(theta) + CC(1,2);
plot(xunit,yunit,'g');
axis equal
hold off

Ограничение между вершинами (V1, V3) был удостоен, однако, критерий Делоне был признан недействительным. Это также делает недействительным отношение ближайшего соседа, которое присуще триангуляции Делоне. Это означает nearestNeighbor метод поиска, предоставленный delaunayTriangulation не может поддерживаться, если триангуляция имеет ограничения.

В типичных приложениях триангуляция может состоять из многих точек, и относительно небольшое количество ребер в триангуляции может быть ограничено. Такая триангуляция называется локально не-Delaunay, потому что многие треугольники в триангуляции могут уважать критерий Delaunay, но локально могут быть некоторые треугольники, которые не делают. Во многих приложениях, локальное расслабление пустого свойства circuccle не является проблемой.

Триангуляции с ограничениями обычно используются для триангуляции неконвексного многоугольника. Ограничения дают нам соответствие между ребрами полигона и ребер триангуляции. Эта связь позволяет вам извлечь триангуляцию, которая представляет область. В следующем примере показано, как использовать ограниченное delaunayTriangulation для триангуляции неконвексного многоугольника.

Задайте и постройте график многоугольника.

figure()
axis([-1 17 -1 6]);
axis equal
P = [0 0; 16 0; 16 2; 2 2; 2 3; 8 3; 8 5; 0 5];
patch(P(:,1),P(:,2),'-r','LineWidth',2,'FaceColor',...
     'none','EdgeColor','r');
 
% Label the points.
hold on
numvx = size(P,1);
vxlabels = arrayfun(@(n) {sprintf('P%d', n)}, (1:numvx)');
Hpl = text(P(:,1)+0.2, P(:,2)+0.2, vxlabels, 'FontWeight', ...
  'bold', 'HorizontalAlignment','center', 'BackgroundColor', ...
  'none');
hold off

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

figure()
subplot(2,1,1);
axis([-1 17 -1 6]);
axis equal

P = [0 0; 16 0; 16 2; 2 2; 2 3; 8 3; 8 5; 0 5];
DT = delaunayTriangulation(P);
triplot(DT)
hold on; 
patch(P(:,1),P(:,2),'-r','LineWidth',2,'FaceColor',...
     'none','EdgeColor','r');
hold off

% Plot the standalone triangulation in a subplot.
subplot(2,1,2);
axis([-1 17 -1 6]);
axis equal
triplot(DT)

Эта триангуляция не может использоваться, чтобы представлять область многоугольника, потому что некоторые треугольники срезаны по контуру. Вы должны наложить ограничение на ребра, которые вырезаны ребрами триангуляции. Поскольку все ребра должны уважаться, необходимо ограничивать все ребра. На шагах ниже показано, как ограничить все ребра.

Введите определение ребра с ограничениями. Наблюдайте из аннотированного рисунка, где вам нужны ограничения (между (V1, V2), (V2, V3), и так далее).

C = [1 2; 2 3; 3 4; 4 5; 5 6; 6 7; 7 8; 8 1];

В общем, если есть N точки в последовательности, которые определяют полигональный контур, ограничения могут быть выражены как C = [(1:(N-1))' (2:N)'; N 1];.

Задайте ограничения при создании delaunayTriangulation.

DT = delaunayTriangulation(P,C);

Кроме того, можно наложить ограничения на существующую триангуляцию, задав Constraints свойство: DT.Constraints = C;.

Постройте график триангуляции и многоугольника.

figure('Color','white')
subplot(2,1,1);
axis([-1 17 -1 6]);
axis equal
triplot(DT)
hold on; 
patch(P(:,1),P(:,2),'-r','LineWidth',2, ...
     'FaceColor','none','EdgeColor','r'); 
hold off

% Plot the standalone triangulation in a subplot.
subplot(2,1,2);
axis([-1 17 -1 6]);
axis equal
triplot(DT)

График показывает, что ребра триангуляции соответствуют контуру многоугольника. Однако триангуляция заполняет вогнутости. Требуется триангуляция, которая представляет полигональную область. Можно извлечь треугольники внутри многоугольника с помощью delaunayTriangulation метод, isInterior. Этот метод возвращает логический массив, true которого и false значения, которые указывают, находятся ли треугольники внутри ограниченной геометрической области. Анализ основан на теореме Кривой Жорданы, и контуры заданы ограничениями ребра. i-й треугольник в триангуляции рассматривается как внутри области, если i-й логический флаг равен true, в противном случае он находится снаружи.

Теперь используйте isInterior метод для вычисления и построения графика набора треугольников области.

% Plot the constrained edges in red.
figure('Color','white')
subplot(2,1,1);
plot(P(C'),P(C'+size(P,1)),'-r','LineWidth', 2);
axis([-1 17 -1 6]);

% Compute the in/out status.
IO = isInterior(DT);
subplot(2,1,2);
hold on;
axis([-1 17 -1 6]);

% Use triplot to plot the triangles that are inside.
% Uses logical indexing and dt(i,j) shorthand
% format to access the triangulation.
triplot(DT(IO, :),DT.Points(:,1), DT.Points(:,2),'LineWidth', 2)
hold off;