В этом примере показано, как создавать, редактировать и запрашивать триангуляции Delaunay с помощью delaunayTriangulation класс. Триангуляция Делоне является наиболее широко используемой триангуляцией в научных вычислениях. Свойства, связанные с триангуляцией, обеспечивают основу для решения множества геометрических задач. Также показана конструкция ограниченных триангуляций Делоне вместе с приложениями, охватывающими вычисления медиальной оси и морфирование сетки.
Этот пример показывает Вам, как вычислить 2-ю триангуляцию Delaunay и затем подготовить триангуляцию вместе с этикетками треугольника и вершиной.
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
Этот пример показывает Вам, как вычислить и подготовить 3D триангуляцию Delaunay.
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])
Для отображения больших четырехгранных сетей используйте convexHull метод для вычисления граничной триангуляции и построения ее графика с использованием trisurf. Например:
triboundary = convexHull(dt); trisurf(triboundary, X(:,1), X(:,2), X(:,3),'FaceColor','cyan')
Существует два способа доступа к структуре данных триангуляции. Один из способов - через Triangulation другим способом является использование индексации.
Создайте 2-ю триангуляцию Delaunay из 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-я вершина iТый треугольник. Применяются стандартные правила индексирования.
Запрос структуры данных триангуляции с индексированием.
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')
Загрузите карту периметра граничащих США. Создайте ограниченную триангуляцию Делоне, представляющую многоугольник. Эта триангуляция охватывает область, ограниченную выпуклым корпусом набора точек. Отфильтруйте треугольники, находящиеся в пределах области многоугольника, и постройте их график. Примечание.Набор данных содержит повторяющиеся точки данных; то есть две или более точек данных имеют одно и то же расположение. Дублированные точки отклоняются, и 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')
В этом примере показано использование триангуляции Делоне для восстановления полигональной границы из облака точек. Реконструкция основана на элегантном алгоритме Crust.
Справка: Н. Амента, М. Берн и Д. Эппштейн. Корка и бета-скелет: комбинаторная кривая реконструкции. Графические модели и обработка изображений, 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(:,:);
Вставьте расположение вершин Вороного в существующую триангуляцию.
V = voronoiDiagram(dt);
Удаление бесконечной вершины и фильтрация повторяющихся точек с помощью unique.
V(1,:) = [];
numv = size(V,1);
dt.Points(end+(1:numv),:) = unique(V,'rows');Кромки Делоне, соединяющие пары точек образца, представляют границу.
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
В этом примере показано, как создать приблизительную медиальную ось полигонального домена с помощью ограниченной триангуляции Делоне. Медиальная ось многоугольника определяется локусом центра максимального диска внутри многоугольника.
Создайте ограниченную триангуляцию Делоне образца точек на границе домена.
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
В этом примере показано, как использовать сетку 2-D домена для адаптации изменения границы домена.
Шаг 1: Загрузка данных. Сетка, которая будет преобразована, определяется trife, xfe, и yfe, которая является триангуляцией в формате грань-вершина.
load trimesh2d clf triplot(trife,xfe,yfe) axis equal axis([-10 310 -10 310]) axis equal xlabel('Initial Mesh','FontWeight','b')
Шаг 2. Построение фоновой триангуляции - триангуляция ограниченного Делоне набора точек, представляющих границу сетки. Для каждой вершины сетки вычислите дескриптор, который определяет ее расположение относительно фоновой триангуляции. Дескриптор является охватывающим треугольником вместе с барицентрическими координатами относительно этого треугольника.
dt = delaunayTriangulation(x,y,Constraints); clf triplot(dt) axis equal axis([-10 310 -10 310]) axis equal xlabel('Background Triangulation','FontWeight','b')
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')
Шаг 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')
