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

Выпуклые оболочки по сравнению с невыпуклыми полигонами

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

rng('default')
x = rand(20,1);
y = rand(20,1);
plot(x,y,'r.','MarkerSize',10)
hold on
k = convhull(x,y);
plot(x(k),y(k))
title('The Convex Hull of a Set of Points')
hold off

Выпуклый многоугольник является многоугольником, который не имеет вогнутых вершин, например:

x = rand(20,1);
y = rand(20,1);
k = convhull(x,y);
plot(x(k),y(k))
title('Convex Polygon')

Можно также создать контур набора точки, который невыпукл. Если вы уменьшаете и сжимаете выпуклую оболочку сверху, можно заключить все точки в невыпуклом многоугольнике с вогнутыми вершинами:

k = boundary(x,y,0.9);
plot(x(k),y(k))
title('Nonconvex Polygon')

Выпуклая оболочка имеет многочисленные приложения. Можно вычислить верхнюю границу на области, ограниченной набором дискретной точки в плоскости от выпуклой оболочки набора. Выпуклая оболочка упрощает представление более комплексных многоугольников или многогранников. Например, чтобы определить, пересекаются ли два невыпуклых тела, вы могли бы применяться, ряд быстрого отклонения продвигается, чтобы избежать штрафа полного перекрестного анализа:

Если бы выпуклые оболочки не пересеклись, это избежало бы расхода более всестороннего теста на пересечение.

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

Альфа-формы

Альфа-форма набора точек является обобщением выпуклой оболочки и подграфом Триангуляции Делоне. Таким образом, выпуклая оболочка является всего одним типом альфа-формы, и полное семейство альфа-форм может быть выведено из Триангуляции Делоне данного набора точки.

rng(4)
x = rand(20,1);
y = rand(20,1);
plot(x,y,'r.','MarkerSize',20)
hold on
shp = alphaShape(x,y,100);
plot(shp)
title('Convex Alpha Shape')
hold off

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

plot(x,y,'r.','MarkerSize',20)
hold on
shp = alphaShape(x,y,.5);
plot(shp)
title('Nonconvex Alpha Shape')
hold off

Варьируясь альфа-радиус может иногда приводить к альфа-форме с несколькими областями, которые могут или не могут содержать отверстия. Однако alphaShape функция в MATLAB® всегда возвращает упорядоченные альфа-формы, который предотвращает изолированные или повисшие точки, ребра или поверхности.

plot(x,y,'r.','MarkerSize',20)
hold on
shp = alphaShape(x,y);
plot(shp)
title('Alpha Shape with Multiple Regions')
hold off