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

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

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

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