Создание и редактирование триангуляций Делоне

В этом примере показано, как создать, отредактируйте и запросите Триангуляции Делоне с помощью delaunayTriangulation класс. Триангуляция Делоне является наиболее широко используемой триангуляцией в научных вычислениях. Свойства, сопоставленные с триангуляцией, обеспечивают базис для решения множества геометрических проблем. Конструкцию ограниченных Триангуляций Делоне также показывают, вместе с приложения, касающиеся среднего расчета оси и превращающейся mesh.

Пример один: создайте и постройте 2D триангуляцию Делоне

Этот пример показывает вам, как вычислить 2D Триангуляцию Делоне и затем построить триангуляцию вместе с вершиной и треугольными метками.

rng default
x = rand(10,1);
y = rand(10,1);
dt = delaunayTriangulation(x,y)
dt = 
  delaunayTriangulation with properties:

              Points: [10x2 double]
    ConnectivityList: [11x3 double]
         Constraints: []

triplot(dt)

Отобразите вершину и треугольные метки на графике.

hold on
vxlabels = arrayfun(@(n) {sprintf('P%d', n)}, (1:10)');
Hpl = text(x,y,vxlabels,'FontWeight','bold','HorizontalAlignment',...
   'center','BackgroundColor','none');
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

Figure contains an axes. The axes contains 22 objects of type line, text.

Пример два: создайте и постройте 3-D триангуляцию Делоне

Этот пример показывает вам, как вычислить и построить 3-D Триангуляцию Делоне.

rng default
X = rand(10,3);
dt = delaunayTriangulation(X)
dt = 
  delaunayTriangulation with properties:

              Points: [10x3 double]
    ConnectivityList: [18x4 double]
         Constraints: []

tetramesh(dt)
view([10 20])

Figure contains an axes. The axes contains 18 objects of type patch.

Чтобы отобразить большие четырехгранные сетки, используйте convexHull метод, чтобы вычислить граничную триангуляцию и построить его с помощью trisurf. Например:

triboundary = convexHull(dt);
trisurf(triboundary, X(:,1), X(:,2), X(:,3),'FaceColor','cyan')

Пример три: доступ к структуре данных триангуляции

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

Создайте 2D Триангуляцию Делоне из 10 случайных точек.

rng default
X = rand(10,2);
dt = delaunayTriangulation(X)
dt = 
  delaunayTriangulation with properties:

              Points: [10x2 double]
    ConnectivityList: [11x3 double]
         Constraints: []

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

dt.ConnectivityList
ans = 11×3

     8     2     3
     6     7     3
     5     2     8
     7     8     3
     7     5     8
     7     6     1
     4     7     1
     9     5     4
     4     5     7
     9     2     5
      ⋮

Индексация является кратким способом запросить триангуляцию. Синтаксисом является dt(i,j), где j jвершина th iтреугольник th. Стандартные правила индексации применяются.

Запросите структуру данных триангуляции с индексацией.

dt(:,:)
ans = 11×3

     8     2     3
     6     7     3
     5     2     8
     7     8     3
     7     5     8
     7     6     1
     4     7     1
     9     5     4
     4     5     7
     9     2     5
      ⋮

Второй треугольник:

dt(2,:)
ans = 1×3

     6     7     3

Третья вершина второго треугольника:

dt(2,3)
ans = 3

Первые три треугольника:

dt(1:3,:)
ans = 3×3

     8     2     3
     6     7     3
     5     2     8

Пример четыре: отредактируйте триангуляцию Делоне, чтобы вставить или удалить точки

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

Создайте Триангуляцию Делоне из 10 случайных точек в модульном квадрате.

rng default
x = rand(10,1);
y = rand(10,1);
dt = delaunayTriangulation(x,y)
dt = 
  delaunayTriangulation with properties:

              Points: [10x2 double]
    ConnectivityList: [11x3 double]
         Constraints: []

Вставьте 5 дополнительных случайных точек.

dt.Points(end+(1:5),:) = rand(5,2)
dt = 
  delaunayTriangulation with properties:

              Points: [15x2 double]
    ConnectivityList: [20x3 double]
         Constraints: []

Замените пятую точку.

dt.Points(5,:) = [0 0]
dt = 
  delaunayTriangulation with properties:

              Points: [15x2 double]
    ConnectivityList: [20x3 double]
         Constraints: []

Удалите четвертую точку.

dt.Points(4,:) = []
dt = 
  delaunayTriangulation with properties:

              Points: [14x2 double]
    ConnectivityList: [18x3 double]
         Constraints: []

Пример пять: создайте ограниченную триангуляцию Делоне

Этот пример показывает вам, как создать ограниченную Триангуляцию Делоне и иллюстрирует эффект ограничений.

Создайте и постройте ограниченную Триангуляцию Делоне.

X = [0 0; 16 0; 16 2; 2 2; 2 3; 8 3; 8 5; 0 5];
C = [1 2; 2 3; 3 4; 4 5; 5 6; 6 7; 7 8; 8 1];
dt = delaunayTriangulation(X,C);
subplot(2,1,1)
triplot(dt)
axis([-1 17 -1 6])
xlabel('Constrained Delaunay triangulation','FontWeight','b')

Постройте ограниченные ребра красного цвета.

hold on
plot(X(C'),X(C'+size(X,1)),'-r','LineWidth',2)
hold off

Теперь удалите ограничения и постройте неограниченную Триангуляцию Делоне.

dt.Constraints = [];
subplot(2,1,2)
triplot(dt)
axis([-1 17 -1 6])
xlabel('Unconstrained Delaunay triangulation','FontWeight','b')

Figure contains 2 axes. Axes 1 contains 9 objects of type line. Axes 2 contains an object of type line.

Пример шесть: создайте ограниченную триангуляцию Делоне географической карты

Загрузите карту периметра совпадающих Соединенных Штатов. Создайте ограниченную Триангуляцию Делоне, представляющую многоугольник. Эта триангуляция охватывает область, которая ограничена выпуклой оболочкой набора точек. Отфильтруйте треугольники, которые являются в области многоугольника и строят их. Примечание: набор данных содержит дублирующиеся точки данных; то есть, две или больше точки данных имеют то же расположение. Дублирующиеся точки отклоняются и delaunayTriangulation переформатировал ограничения соответственно.

clf
load usapolygon

Задайте ограничение ребра между двумя последовательными точками, которые составляют многоугольный контур и создают Триангуляцию Делоне.

nump = numel(uslon);
C = [(1:(nump-1))' (2:nump)'; nump 1];
dt = delaunayTriangulation(uslon,uslat,C);
Warning: Duplicate data points have been detected and removed.
 The Triangulation indices and constraints are defined with respect to the unique set of points in delaunayTriangulation.
Warning: Intersecting edge constraints have been split, this may have added new points into the triangulation.
io = isInterior(dt);
patch('Faces',dt(io,:),'Vertices',dt.Points,'FaceColor','r')
axis equal
axis([-130 -60 20 55])
xlabel('Constrained Delaunay Triangulation of usapolygon','FontWeight','b')

Figure contains an axes. The axes contains an object of type patch.

Пример семь: изогните реконструкцию от облака точек

Этот пример подсвечивает использование Триангуляции Делоне, чтобы восстановить многоугольный контур от облака точек. Реконструкция основана на изящном алгоритме Корки.

Ссылка: N. Сережки, M. Берн, и Д. Эппштайн. Корка и бета скелет: комбинаторная реконструкция кривой. Графические Модели и Обработка изображений, 60:125-135, 1998.

Создайте набор точек, представляющих облако точек.

numpts = 192;
t = linspace( -pi, pi, numpts+1 )';
t(end) = [];
r = 0.1 + 5*sqrt( cos( 6*t ).^2 + (0.7).^2 );
x = r.*cos(t);
y = r.*sin(t);
ri = randperm(numpts);
x = x(ri);
y = y(ri);

Создайте Триангуляцию Делоне набора точки.

dt = delaunayTriangulation(x,y);
tri = dt(:,:);

Вставьте местоположение вершин Voronoi в существующую триангуляцию.

V = voronoiDiagram(dt);

Удалите бесконечную вершину и отфильтруйте дублирующиеся точки с помощью unique.

V(1,:) = [];
numv = size(V,1);
dt.Points(end+(1:numv),:) = unique(V,'rows');

Ребра Delaunay, которые соединяют пары точек выборки, представляют контур.

delEdges = edges(dt);
validx = delEdges(:,1) <= numpts;
validy = delEdges(:,2) <= numpts;
boundaryEdges = delEdges((validx & validy),:)';
xb = x(boundaryEdges);
yb = y(boundaryEdges);
clf
triplot(tri,x,y)
axis equal
hold on
plot(x,y,'*r')
plot(xb,yb,'-r')
xlabel('Curve reconstruction from point cloud','FontWeight','b')
hold off

Figure contains an axes. The axes contains 194 objects of type line.

Пример восемь: вычислите аппроксимированную среднюю ось многоугольной области

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

Создайте ограниченную Триангуляцию Делоне из выборки точек на доменном контуре.

load trimesh2d
dt = delaunayTriangulation(x,y,Constraints);
inside = isInterior(dt);

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

tr = triangulation(dt(inside,:),dt.Points);

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

numt = size(tr,1);
T = (1:numt)';
neigh = neighbors(tr);
cc = circumcenter(tr);
xcc = cc(:,1);
ycc = cc(:,2);
idx1 = T < neigh(:,1);
idx2 = T < neigh(:,2);
idx3 = T < neigh(:,3);
neigh = [T(idx1) neigh(idx1,1); T(idx2) neigh(idx2,2); T(idx3) neigh(idx3,3)]';

Постройте доменные треугольники зеленого цвета, доменный контур синего цвета и среднюю ось красного цвета.

clf
triplot(tr,'g')
hold on
plot(xcc(neigh), ycc(neigh), '-r','LineWidth',1.5)
axis([-10 310 -10 310])
axis equal
plot(x(Constraints'),y(Constraints'),'-b','LineWidth',1.5)
xlabel('Medial Axis of Polygonal Domain','FontWeight','b')
hold off

Figure contains an axes. The axes contains 364 objects of type line.

Пример девять: превратите 2D Mesh в модифицированный контур

В этом примере показано, как превратить сетку 2D области, чтобы вместить модификацию к доменному контуру.

Шаг 1: Загрузите данные. Mesh, которая будет превращена, задана trife, xfe, и yfe, который является триангуляцией в формате вершины поверхности.

load trimesh2d
clf
triplot(trife,xfe,yfe)
axis equal
axis([-10 310 -10 310])
axis equal
xlabel('Initial Mesh','FontWeight','b')

Figure contains an axes. The axes contains an object of type line.

Шаг 2: Создайте фоновую триангуляцию - Ограниченная Триангуляция Делоне набора точек, представляющего контур mesh. Для каждой вершины mesh вычислите дескриптор, который задает его местоположение относительно фоновой триангуляции. Дескриптор является треугольником включения вместе с барицентрическими координатами относительно того треугольника.

dt = delaunayTriangulation(x,y,Constraints);
clf
triplot(dt)
axis equal
axis([-10 310 -10 310])
axis equal
xlabel('Background Triangulation','FontWeight','b')

Figure contains an axes. The axes contains an object of type line.

descriptors.tri = pointLocation(dt,xfe,yfe);
descriptors.baryCoords = cartesianToBarycentric(dt,descriptors.tri,[xfe yfe]);

Шаг 3: Отредактируйте фоновую триангуляцию, чтобы включить желаемую модификацию к доменному контуру.

cc1 = [210 90];
circ1 = (143:180)';
x(circ1) = (x(circ1)-cc1(1))*0.6 + cc1(1);
y(circ1) = (y(circ1)-cc1(2))*0.6 + cc1(2);
tr = triangulation(dt(:,:),x,y);
clf
triplot(tr)
axis([-10 310 -10 310])
axis equal
xlabel('Edited Background Triangulation - Hole Size Reduced','FontWeight','b')

Figure contains an axes. The axes contains an object of type line.

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

Xnew = barycentricToCartesian(tr,descriptors.tri,descriptors.baryCoords);
tr = triangulation(trife,Xnew);
clf
triplot(tr)
axis([-10 310 -10 310])
axis equal
xlabel('Morphed Mesh','FontWeight','b')

Figure contains an axes. The axes contains an object of type line.

Для просмотра документации необходимо авторизоваться на сайте