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

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

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

Первый пример использует 2D набор точки от набора данных подводной горы, как введено к функции 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 может вычислить выпуклую оболочку и 2D и 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 в 2D и 3-D, когда это более устойчиво и дает лучшую эффективность.

Нахождение выпуклой оболочки с использованием Класс delaunayTriangulation

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

delaunayTriangulation класс поддерживает расчет Триангуляций Делоне в 2D и трехмерном пространстве. Этот класс также обеспечивает convexHull метод, чтобы вывести выпуклую оболочку из триангуляции.

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

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

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

alphaShape вычисляет упорядоченную альфа-форму из набора 2D или 3-D точек. Можно задать альфа-радиус, который определяет, как плотно или свободно альфа-форма окутывает набор точки. Когда альфа-радиус установлен в Inf, получившаяся альфа-форма является выпуклой оболочкой набора точки.

Создайте набор 2D точек.

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)