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

Выпуклые корпуса против невыпуклых многоугольников

Выпуклый корпус набора точек в 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