УДК 004.021

Построение невыпуклой оболочки множества точек

Пугачев Анатолий Иванович – кандидат технических наук, доцент Самарского государственного технического университета.

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

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

Вычисления выпуклых и невыпуклых (вогнутых) оболочек множества точек на плоскости по-прежнему остается сложной задачей вычислительной геометрии, решение которой востребовано различных областях: в компьютерной графике, в распознавании образов и системах искусственного интеллекта, в геоинформационных системах (ГИС) [1].

В разработке алгоритмов построения невыпуклой оболочки (НВО) преобладают два подхода. Первый основан на том, что на множестве исходных точек предварительно строится триангуляция Делоне [2]. Далее в ней последовательно исключаются самая длинная внешняя сторона. При этом во внешний контур вместо удаленной в качестве внешних добавляются две оставшиеся стороны удаляемого треугольника.

В алгоритмах второго типа в качестве начальной НВО строится минимальная выпуклая оболочка (МВО) исходного множества точек [4]. Далее для сторон этой НВО среди оставшихся точек исходного множества подбираются точки, на основании которых вместо имеющихся сторон строятся впадины. К этому типу относятся алгоритмы, опубликованные в работах [3, 5].

В алгоритме, предложенном в [3], доминирующим критерием выбора точки для построения впадины служит максимальное удаление ее от стороны НВО. Дополнительно проверяется отсутствие в треугольнике, образуемом стороной и выбираемой точкой, других точек исходного множества, а также отсутствие пересечения сторон треугольника с другими сторонами НВО. Алгоритм хорошо ориентирован на построение НВО с возможностью высокой ее детализации.

В алгоритме, представленном в [5], при выборе каждой точки для построения впадины вместо стороны НВО используется ряд жестких условий, ограничивающих диапазоны возможных углов треугольника, образуемого стороной и выбираемой точкой. Так же дополнительно проверяется отсутствие в этом треугольнике других точек исходного множества, а также отсутствие пересечения сторон треугольника с другими сторонами НВО. Этот алгоритм в первую очередь ориентирован на построение невыпуклых оболочек, гладкость которых можно регулировать.

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

Входными данными алгоритма служат множество P точек на плоскости. Результат работы алгоритма – упорядоченное множество H вершин невыпуклой оболочки.

На первом этапе алгоритма находятся вершины H минимальной выпуклой оболочки множества P (рисунок 1а). Не принципиально, но в данном алгоритме функция ConvexHull на основании P возвращает вершины H упорядоченными в соответствии с обходом по часовой стрелке [3].

а)	б)

Рисунок 1. Этапы построения НВО: а) МВО; б) формирование впадин.

На втором этапе в списке H находится индекс i_m точки H[i_m] – начала стороны H[i_m] H[i_m+1] наибольшей длины. Обозначим начальную точку как
p_b = H[im] , а конечную – как p_e = H[im+1] .

Далее для стороны p_bp_e в множестве G = P\H выполняется поиск дополнительной вершины p_t, образующей впадину (рисунок 1б). Выбор ее ограничивается несколькими условиями. Во-первых, зона поиска ограничивается условием:

d₁² > |d₁² – d₂²|, (1)

где d₀ – длина p_bp_e; d₁ – длина p_bp_t; d₂ – длина p_ep_t.

Условие (1) ограничивает зону поиска в виде полосы шириной d₀, начинающейся от стороны p_bp_e и перпендикулярной ей (рисунок 2).

Рисунок 2. Ограничение зоны поиска.

Из всех точек, удовлетворяющих условию (1), точка p_t должна быть максимально удалена от стороны p_bp_e. Если при этом в треугольнике p_bp_ep_t нет ни одной точки из G, кроме p_t, и стороны p_bp_t и p_ep_t не пересекаются ни с одной из сторон НВО, построенных к этому моменту, то тогда p_t добавляется в список H между H[i_m] и H[i_m+1]. При этом вместо стороны p_bp_e в НВО образуются две новые стороны.

Далее процесс построения впадин повторяется. После этого в расширенном списке H вновь находится индекс i_m начальной точки стороны наибольшей длины, и для нее по тем же условиям выполняется поиск точки p_t, образующей впадину на ней.

Процесс повторяется wn_h раз. n_h – количество точек МВО, 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 наибольший.

Далее в полосе, начинающейся от найденной наибольшей стороны p_bp_e, в G = P\H отбирается точка pt, наиболее удаленная от p_bp_e. Мерой расстояния pt от p_bp_e служит площадь Sqt треугольника p_bp_ep_t. Точка pt отбрасывается, если функция NotEmptyTreangle обнаруживает в треугольнике p_bp_ep_t хотя бы одну точку из 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 приводит к повышению детальности НВО, позволяя выявить в ней глубокие впадины.

Список литературы

1. Asaeedi, Didehvar F., Mohades A. NLP Formulation for Polygon Optimization Problems // Mathematics 2019, 7(1), 24. [Электронный ресурс]. – URL: https://doi.org/10.3390/math7010024
2. 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.
3. Tereshchenko V., Muravitskiy V. Constructing a Simple Polygonalizations // Computer and Information Engineering. – Vol. 5, No 5, – p. 493–496.
4. Пугачев А.И. Рекурсивный алгоритм построения минимальной выпуклой оболочки // Наукосфера. 2021, апрель № 4 (2). URL: http: // Nauko-sfera.ru – с. 165–168.
5. Соловьева А.Н. Построение многоугольников, моделирующих границы текстурных областей на аэрокосмическом снимке // Интеллектуальные системы в производстве, 2014, № 2 (24) – с. 167–168.