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

Вычисление Выпуклой оболочки Использование convhull и convhulln

The convhull и convhulln функции берут набор точек и выводят индексы точек, которые лежат на контуре выпуклой оболочки. Основанное на индексе точек представление выпуклой оболочки поддержек графического изображения и удобный доступ к данным. Следующие примеры иллюстрируют расчет и представление выпуклой оболочки.

Первый пример использует набор точек 2-D из набора данных seamount в качестве входных данных в функцию convhull.

Загрузите данные.

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);

The 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 размерностях создают проблемы из-за быстро растущих требований к памяти.

The convhull функция превосходит convhulln в 2-D и 3-D, поскольку он является более устойчивым и обеспечивает лучшую эффективность.

Выпуклая оболочка Расчета с использованием класса delaunayTriangulation

Этот пример показывает связь между триангуляцией Делоне набора точек в 2-D и выпуклая оболочка этого набора точек.

The delaunayTriangulation класс поддерживает расчет триангуляций Делоне в 2-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 способ. Однако подход, основанный на триангуляции, подходит, если:

Выпуклая оболочка Расчета с использованием alphaShape

В этом примере показано, как вычислить выпуклую оболочку набора точек 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)