Выпуклая оболочка набора точек на пробеле N-D является самой маленькой выпуклой областью, заключающей все точки в набор. Если бы вы думаете о 2D наборе точек как о штепселях в плате штепселя, выпуклая оболочка того набора была бы сформирована путем взятия резинки и использования его, чтобы заключить все штепсели.
x = gallery('uniformdata',20,1,20); y = gallery('uniformdata',20,1,30); 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 = gallery('uniformdata',20,1,30); y = gallery('uniformdata',20,1,40); 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')
Выпуклая оболочка имеет многочисленные приложения. Можно вычислить верхнюю границу на области, ограниченной набором дискретной точки в плоскости от выпуклой оболочки набора. Выпуклая оболочка упрощает представление более комплексных многоугольников или многогранников. Например, чтобы определить, пересекаются ли два невыпуклых тела, вы могли бы применяться, ряд быстрого отклонения продвигается, чтобы избежать штрафа полного перекрестного анализа:
Проверяйте, пересекаются ли выровненные осью ограничительные рамки вокруг каждого тела.
Если ограничительные рамки пересекаются, можно вычислить выпуклую оболочку каждого тела и проверять пересечение оболочек.
Если бы выпуклые оболочки не пересеклись, это избежало бы расхода более всестороннего теста на пересечение.
В то время как выпуклые оболочки и невыпуклые многоугольники являются удобными способами представлять относительно простые контуры, они - на самом деле определенные экземпляры более общего геометрического построения, названного альфа-формой.
Альфа-форма набора точек является обобщением выпуклой оболочки и подграфом Триангуляции Делоне. Таким образом, выпуклая оболочка является всего одним типом альфа-формы, и полное семейство альфа-форм может быть выведено из Триангуляции Делоне данного набора точки.
x = gallery('uniformdata',20,1,10); y = gallery('uniformdata',20,1,20); 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