УДК 004.021
Построение невыпуклой оболочки множества точек
Пугачев Анатолий Иванович – кандидат технических наук, доцент Самарского государственного технического университета.
Аннотация: В статье рассматривается алгоритм построения невыпуклой оболочки для множества точек на плоскости, в котором сначала строится минимальная выпуклая оболочка, а затем список ее точек последовательно расширяется путем добавления новых точек, образующих впадины. В отличие от известных алгоритмов такого типа в предлагаемом алгоритме отбор новых точек исходного множества для добавления впадин осуществляется на основе комплекса оригинальных условий, обеспечивающих построение невыпуклой оболочки, гладкость которой и степень глубины впадин можно менять. Рассмотрена программная реализация алгоритма. Приведены результаты, полученные при его программной реализации.
Ключевые слова: множество точек, минимальная выпуклая оболочка, невыпуклая оболочка, вершина, площадь ориентированного треугольника.
Вычисления выпуклых и невыпуклых (вогнутых) оболочек множества точек на плоскости по-прежнему остается сложной задачей вычислительной геометрии, решение которой востребовано различных областях: в компьютерной графике, в распознавании образов и системах искусственного интеллекта, в геоинформационных системах (ГИС) [1].
В разработке алгоритмов построения невыпуклой оболочки (НВО) преобладают два подхода. Первый основан на том, что на множестве исходных точек предварительно строится триангуляция Делоне [2]. Далее в ней последовательно исключаются самая длинная внешняя сторона. При этом во внешний контур вместо удаленной в качестве внешних добавляются две оставшиеся стороны удаляемого треугольника.
В алгоритмах второго типа в качестве начальной НВО строится минимальная выпуклая оболочка (МВО) исходного множества точек [4]. Далее для сторон этой НВО среди оставшихся точек исходного множества подбираются точки, на основании которых вместо имеющихся сторон строятся впадины. К этому типу относятся алгоритмы, опубликованные в работах [3, 5].
В алгоритме, предложенном в [3], доминирующим критерием выбора точки для построения впадины служит максимальное удаление ее от стороны НВО. Дополнительно проверяется отсутствие в треугольнике, образуемом стороной и выбираемой точкой, других точек исходного множества, а также отсутствие пересечения сторон треугольника с другими сторонами НВО. Алгоритм хорошо ориентирован на построение НВО с возможностью высокой ее детализации.
В алгоритме, представленном в [5], при выборе каждой точки для построения впадины вместо стороны НВО используется ряд жестких условий, ограничивающих диапазоны возможных углов треугольника, образуемого стороной и выбираемой точкой. Так же дополнительно проверяется отсутствие в этом треугольнике других точек исходного множества, а также отсутствие пересечения сторон треугольника с другими сторонами НВО. Этот алгоритм в первую очередь ориентирован на построение невыпуклых оболочек, гладкость которых можно регулировать.
В этой статье предлагается новый алгоритм построения невыпуклой оболочки, также основанный первоначальном построении МВО, отличающийся тем, что в отборе точек при построении впадин используется оригинальный критерий, позволяющий сочетать достижение высокой детальности НВО с достаточной гладкостью.
Входными данными алгоритма служат множество P точек на плоскости. Результат работы алгоритма – упорядоченное множество H вершин невыпуклой оболочки.
На первом этапе алгоритма находятся вершины H минимальной выпуклой оболочки множества P (рисунок 1а). Не принципиально, но в данном алгоритме функция ConvexHull на основании P возвращает вершины H упорядоченными в соответствии с обходом по часовой стрелке [3].
![]() |
|
а) |
б) |
Рисунок 1. Этапы построения НВО: а) МВО; б) формирование впадин.
На втором этапе в списке H находится индекс im точки H[im] – начала стороны H[im] H[im+1] наибольшей длины. Обозначим начальную точку как
pb = H[im] , а конечную – как pe = H[im+1] .
Далее для стороны pbpe в множестве G = P\H выполняется поиск дополнительной вершины pt, образующей впадину (рисунок 1б). Выбор ее ограничивается несколькими условиями. Во-первых, зона поиска ограничивается условием:
d12 > |d12 – d22|, (1)
где d0 – длина pbpe; d1 – длина pbpt; d2 – длина pept.
Условие (1) ограничивает зону поиска в виде полосы шириной d0, начинающейся от стороны pbpe и перпендикулярной ей (рисунок 2).
Рисунок 2. Ограничение зоны поиска.
Из всех точек, удовлетворяющих условию (1), точка pt должна быть максимально удалена от стороны pbpe. Если при этом в треугольнике pbpept нет ни одной точки из G, кроме pt, и стороны pbpt и pept не пересекаются ни с одной из сторон НВО, построенных к этому моменту, то тогда pt добавляется в список H между H[im] и H[im+1]. При этом вместо стороны pbpe в НВО образуются две новые стороны.
Далее процесс построения впадин повторяется. После этого в расширенном списке H вновь находится индекс im начальной точки стороны наибольшей длины, и для нее по тем же условиям выполняется поиск точки pt, образующей впадину на ней.
Процесс повторяется wnh раз. nh – количество точек МВО, w – параметр, задающий число повторений построения впадин. При каждом повторении в список H добавляется одна вершина, образующая новую впадину.
Ниже приведена программная реализация рассмотренного алгоритма построения невыпуклой оболочки для множества точек на плоскости.
H = ConvexHull(P); // МВО списка P точек
nh = H.Count();
G = P\H;
for (i = 0; i < w * nh; i++)
{
im = IndexMaxSide(H); // индекс в H начальной точки наибольшей стороны
pb = H[im]; pe = H[(im + 1) % H.Count()];
jpt = -1;
qd0 = qDist(pb, pe); // квадрат расстояния pb, pe
Sqmax = 0;
foreach (pt in G)
{
qd1 = qDist(pb, pt); qd2 = qDist(pe, pt);
if (qd0 > Abs(qd1 - qd2))
{
Sqt = Sq(pb, pt, pe);
if (Sqt < Sqmax) continue;
if (NotEmptyTreangle(pb, pe, pt, G)) continue;
if (IsCrossHull(pb, pe, pt, H)) continue;
jpt = G.IndexOf(pt);
Sqmax = Sqt;
}
}
if (jpt >= 0)
{
H.Insert(im + 1, G[jpt]);
G.RemoveAt(jpt);
}
else break;
}
Функция ConvexHull выделяет из множества P МВО H в качестве начального значения НВО. В циклической части функцией IndexMaxSide в H находится сторона, для которой квадрат длины qd0 наибольший.
Далее в полосе, начинающейся от найденной наибольшей стороны pbpe, в G = P\H отбирается точка pt, наиболее удаленная от pbpe. Мерой расстояния pt от pbpe служит площадь Sqt треугольника pbpept. Точка pt отбрасывается, если функция NotEmptyTreangle обнаруживает в треугольнике pbpept хотя бы одну точку из G, не считая pt. Функция IsCrossHull дополнительно исключает из отбора точку pt, если сторона pbpt или pept пересекается с какой-либо стороной текущего списка Н.
Если в G находится точка, удовлетворяющая всем условиям отбора, то она добавляется в список Н и вычитается из G. В следующей итерации рассматривается расширенный список Н.
Каждая итерация добавляет в Н одну вершину. Число итераций задается значением w * nh, где nh – число вершин МВО.
Параметр w определяет степень детализации НВО и степень ее гладкости. При w = 0 НВО будет минимальной выпуклой оболочкой и ее гладкость будет максимальной. С возрастанием w детализация повышается: увеличивается число впадин и их глубина, гладкость НВО при этом снижается.
Для проверки работоспособности алгоритма и оценки его свойств он был реализован программно с визуализацией исходного множества точек и формируемой невыпуклой оболочки.
На рисунке 3 приведены результаты программного построения НВО для множества из 388 точек при нескольких значениях w.
![]() |
||
а) |
б) |
в) |
Рисунок 3. НВО множества из 388 точек: а) w = 2; б) w = 5; в) w = 8.
Результаты подтверждают, что увеличение параметра w приводит к повышению детальности НВО, позволяя выявить в ней глубокие впадины.
Список литературы
- Asaeedi, Didehvar F., Mohades A. NLP Formulation for Polygon Optimization Problems // Mathematics 2019, 7(1), 24. [Электронный ресурс]. – URL: https://doi.org/10.3390/math7010024
- Duckham M., Kulik L., Worboys M., Galton A. Efficient Generation of Simple Polygons for Characterizing the Shape of a Set of Points in the Plane // Pattern Recognition. – 2008. – Vol. 41. – p. 3224–3236.
- Tereshchenko V., Muravitskiy V. Constructing a Simple Polygonalizations // Computer and Information Engineering. – Vol. 5, No 5, – p. 493–496.
- Пугачев А.И. Рекурсивный алгоритм построения минимальной выпуклой оболочки // Наукосфера. 2021, апрель № 4 (2). URL: http: // Nauko-sfera.ru – с. 165–168.
- Соловьева А.Н. Построение многоугольников, моделирующих границы текстурных областей на аэрокосмическом снимке // Интеллектуальные системы в производстве, 2014, № 2 (24) – с. 167–168.