Типы контуров области

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

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

Figure contains an axes. The axes with title The Convex Hull of a Set of Points contains 2 objects of type line.

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

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

Figure contains an axes. The axes with title Convex Polygon contains an object of type line.

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

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

Figure contains an axes. The axes with title Nonconvex Polygon contains an object of type line.

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

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

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

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

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

Альфа-формы

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

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

Figure contains an axes. The axes with title Convex Alpha Shape contains 2 objects of type line, patch.

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

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

Figure contains an axes. The axes with title Nonconvex Alpha Shape contains 2 objects of type line, patch.

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

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

Figure contains an axes. The axes with title Alpha Shape with Multiple Regions contains 2 objects of type line, patch.

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

|

Похожие темы

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