Вычисление выпуклой оболочки

MATLAB® обеспечивает несколько способов вычислить выпуклую оболочку:

Функция convhull поддерживает вычисление выпуклых оболочек в 2D и 3-D. Функция convhulln поддерживает вычисление выпуклых оболочек в N-D (N ≥ 2). Функция convhull рекомендуется для 2D или 3-D вычислений из-за лучшей робастности и производительности.

Класс delaunayTriangulation поддерживает 2D или 3-D вычисление выпуклой оболочки от Триангуляции Делоне. Это вычисление не так эффективно как специализированный convhull и функции convhulln. Однако, если вы имеете delaunayTriangulation набора точки и требуете выпуклой оболочки, метод convexHull может вычислить выпуклую оболочку более эффективно из существующей триангуляции.

Функция alphaShape также поддерживает 2D или 3-D вычисление выпуклой оболочки путем установки альфа-входного параметра радиуса на Inf. Как delaunayTriangulation, однако, вычисляя выпуклую оболочку с помощью alphaShape менее эффективно, чем использование convhull или convhulln непосредственно. Исключение - когда вы работаете с ранее созданным альфа-объектом фигуры.

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

Скрипт Open Live Script

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

Скрипт Open Live Script

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

Класс delaunayTriangulation поддерживает вычисление Триангуляций Делоне на 2D и 3-D пробеле. Этот класс также предоставляет метод 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. Однако основанный на триангуляции подход является соответствующим если:

  • У вас уже есть delaunayTriangulation набора точки, и выпуклая оболочка также требуется.

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

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

Скрипт Open Live Script

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

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