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

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

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

Figure contains an axes object. The axes object contains 2 objects of type line.

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

Figure contains an axes object. The axes object contains an object of type patch.

Объем, ограниченный 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'))

Figure contains 2 axes objects. Axes object 1 with title Convex hull with simplify set to false contains an object of type patch. Axes object 2 with title Convex hull with simplify set to true contains an object of type patch.

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

Figure contains an axes object. The axes object contains 2 objects of type line.

В 3-D фасеты триангуляции, которые совместно используются только одним четырехгранником, представляют контур выпуклой оболочки.

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

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

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

Нахождение выпуклой оболочки с использованием 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)

Figure contains an axes object. The axes object contains an object of type patch.

Смотрите также

| | | |

Похожие темы

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