MATLAB ® предоставляет несколько способов вычисления выпуклого корпуса:
Использование convexHull метод, предоставляемый delaunayTriangulation класс
Использование alphaShape функция с альфа-радиусом Inf.
convhull функция поддерживает вычисление выпуклых корпусов в 2-D и 3-D. convhulln функция поддерживает вычисление выпуклых корпусов в N-D (N ≥ 2). convhull функция рекомендуется для 2-D или 3-D вычислений из-за лучшей надежности и производительности.
delaunayTriangulation класс поддерживает 2-D или 3-D вычисление выпуклого корпуса из триангуляции Делоне. Это вычисление не так эффективно, как выделенное convhull и convhulln функции. Однако, если у вас есть delaunayTriangulation точки, установленной и требующей выпуклого корпуса, convexHull способ может более эффективно вычислять выпуклый корпус из существующей триангуляции.
alphaShape функция также поддерживает вычисление 2-D или 3-D выпуклого корпуса, задав для входного параметра альфа-радиуса значение Inf. Как delaunayTriangulation, однако, вычисление выпуклого корпуса с использованием alphaShape менее эффективен, чем использование convhull или convhulln непосредственно. Исключение составляет работа с ранее созданным объектом альфа-фигуры.
convhull и convhulln функции берут набор точек и выводят индексы точек, лежащих на границе выпуклого корпуса. Представление выпуклого корпуса на основе индекса точек поддерживает печать и удобный доступ к данным. Следующие примеры иллюстрируют вычисление и представление выпуклого корпуса.
В первом примере используется набор точек 2-D из набора данных подводной горы в качестве входных данных для функции выпуклости.
Загрузите данные.
load seamountВычислите выпуклый корпус набора точек.
K = convhull(x,y);
K представляет собой индексы точек, расположенных в цикле против часовой стрелки вокруг выпуклого корпуса.
Постройте график данных и его выпуклого корпуса.
plot(x,y,'.','markersize',12) xlabel('Longitude') ylabel('Latitude') hold on plot(x(K),y(K),'r')
Добавление меток точек к точкам на выпуклом корпусе для наблюдения за структурой K.
[K,A] = convhull(x,y);
convhull может вычислять выпуклый корпус как 2-D, так и 3-D наборов точек. Набор данных подводной горы можно использовать повторно, чтобы проиллюстрировать вычисление выпуклого корпуса 3-D.
Включите отметки координат подводной горы по оси Z.
close(gcf) K = convhull(x,y,z);
В 3-D границы выпуклого корпуса, K, представлен триангуляцией. Это набор треугольных фасетов в матричном формате, который индексируется относительно массива точек. Каждая строка матрицы K представляет треугольник.
Поскольку граница выпуклого корпуса представлена в виде триангуляции, можно использовать функцию триангуляции печати trisurf.
trisurf(K,x,y,z,'Facecolor','cyan')
Объем, ограниченный 3-D выпуклым корпусом, необязательно может быть возвращен convhull, синтаксис следующий.
[K,V] = convhull(x,y,z);
convhull функция также предоставляет возможность упрощения представления выпуклого корпуса путём удаления вершин, не вносящих вклад в площадь или объём. Например, если граничные грани выпуклого корпуса коллинеарны или компланарны, их можно объединить для получения более краткого представления. Следующий пример иллюстрирует использование этой опции.
[x,y,z] = meshgrid(-2:1:2,-2:1:2,-2:1:2); x = x(:); y = y(:); z = z(:); K1 = convhull(x,y,z); subplot(1,2,1) defaultFaceColor = [0.6875 0.8750 0.8984]; trisurf(K1,x,y,z,'Facecolor',defaultFaceColor) axis equal title(sprintf('Convex hull with simplify\nset to false')) K2 = convhull(x,y,z,'simplify',true); subplot(1,2,2) trisurf(K2,x,y,z,'Facecolor',defaultFaceColor) axis equal title(sprintf('Convex hull with simplify\nset to true'))
MATLAB обеспечивает convhulln функция поддержки вычисления выпуклых корпусов и гиперобъемов в более высоких измерениях. Хотя convhulln поддерживает N-D, проблемы более чем в 10 измерениях создают проблемы из-за быстро растущих требований к памяти.
convhull функция превосходит convhulln в 2-D и 3-D, поскольку она более надежна и обеспечивает более высокую производительность.
В этом примере показана взаимосвязь между триангуляцией Делоне набора точек в 2-D и выпуклым корпусом этого набора точек.
delaunayTriangulation класс поддерживает вычисление триангуляций Делоне в пространстве 2-D и 3-D. Этот класс также предоставляет convexHull способ получения выпуклого корпуса из триангуляции.
Создайте триангуляцию Делоне набора точек в 2-D.
X = [-1.5 3.2; 1.8 3.3; -3.7 1.5; -1.5 1.3; 0.8 1.2; ... 3.3 1.5; -4.0 -1.0; -2.3 -0.7; 0 -0.5; 2.0 -1.5; ... 3.7 -0.8; -3.5 -2.9; -0.9 -3.9; 2.0 -3.5; 3.5 -2.25]; dt = delaunayTriangulation(X);
Постройте график триангуляции и выделите кромки, которые являются общими только для одного треугольника, чтобы раскрыть выпуклый корпус.
triplot(dt) fe = freeBoundary(dt)'; hold on plot(X(fe,1), X(fe,2), '-r', 'LineWidth',2) hold off
В 3-D грани триангуляции, которые являются общими только для одного тетраэдра, представляют границу выпуклого корпуса.
Специальное convhull функция, как правило, более эффективна, чем вычисление, основанное на convexHull способ. Однако подход, основанный на триангуляции, уместен, если:
У вас есть delaunayTriangulation уже поставленной точки и требуется также выпуклый корпус.
Необходимо добавлять или удалять точки из набора постепенно, а также часто пересчитывать выпуклый корпус после редактирования точек.
В этом примере показано, как вычислить выпуклый корпус 2-D точки, установленной с помощью alphaShape функция.
alphaShape вычисляет регуляризованную альфа-форму из набора 2-D или 3-D точек. Можно задать альфа-радиус, который определяет, насколько плотно или свободно альфа-форма охватывает набор точек. Если для альфа-радиуса задано значение Infрезультирующая альфа-форма представляет собой выпуклый корпус набора точек.
Создайте набор 2-D точек.
X = [-1.5 3.2; 1.8 3.3; -3.7 1.5; -1.5 1.3; 0.8 1.2; ... 3.3 1.5; -4.0 -1.0; -2.3 -0.7; 0 -0.5; 2.0 -1.5; ... 3.7 -0.8; -3.5 -2.9; -0.9 -3.9; 2.0 -3.5; 3.5 -2.25];
Вычислите и постройте график выпуклого корпуса набора точек, используя альфа-форму с альфа-радиусом, равным Inf.
shp = alphaShape(X,Inf); plot(shp)
alphaShape | convexHull | convhull | convhulln | delaunayTriangulation