Триангуляция методом измельчения плоской области, заданной системой неравенств

ВВЕДЕНИЕ

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

МАТЕРИАЛЫ И МЕТОДЫ

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

Выпуклая триангуляция представляет собой триангуляцию, в которой минимальный многоугольник, охватывающий все треугольники, является выпуклым.

Такая невыпуклая триангуляция называется невыпуклой [3].

Задачи построения триангуляции заключаются в следующем: пусть задан такой набор точек, что, расположив его на плоскости, каждая точка будет иметь две координаты: (x, y). Нужно, чтобы эти точки были соединены таким образом, чтобы в результате получилась триангуляция [4].

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

(x₁, y₁) = (x₀, y₀) + α * gradF(x₀, y₀),(1)

где α – сдвиг с определенным шагом;

(x₀, y₀) – начальные координаты точек;

gradF – градиентная функция;

F(x; y) – функция, зависящая от двух переменных.

Точки (x₁, y₁) представляют собой новые координаты исходных точек (x₀, y₀) после их сдвига по заданной формуле.

Сдвиг выполняется для того, чтобы точки приблизились к границам области, не выходя за их пределы [5].

Рассмотрим алгоритм измельчения триангуляционной области более подробно.

Дано конечное множество точек {Pi} в плоскости R² и триангуляция T = {Tj}, где каждый треугольник содержит три точки из {Pi}, а каждая точка является вершиной хотя бы одного треугольника. Обозначим минимальный угол триангуляции как α(T). Объединение всех треугольников образует многоугольник. Пусть Ω – ограниченная область в R²; триангуляцией области Ω называется триангуляция конечного набора точек в замыкании Ω. Треугольники с двумя или тремя вершинами на границе ∂Ω называются граничными, остальные – внутренними [6].

Для построения треугольной сетки предлагаем подход с одним проходом по вершинам: выбираем небольшое количество точек из Ω и строим начальную триангуляцию, затем применяем процесс измельчения для повышения точности. Качество триангуляции определяется минимальным синусом углов треугольников, что влияет на погрешность при вычислении функций и их производных. Алгоритм измельчения состоит из следующих последовательных шагов [7]:

1. Зафиксируем натуральное число q.
2. Для каждого внутреннего треугольника Tk:

– выбираем одну из его вершин;

– делим стороны, выходящие из этой вершины, на q равных отрезков;

– проводим через полученные точки прямые, параллельные другим сторонам треугольника;

– в результате треугольник Tk разбивается на q² подобных треугольников.

При таком разбиении минимальный угол новой триангуляции остается равным (рис. 2) α(T), обеспечивая высокое качество сетки и более точное приближение границы области.

РЕЗУЛЬТАТЫ И ИХ ОБСУЖДЕНИЕ

Отдельно рассмотрим программную реализацию алгоритма измельчения.

Данная программа выполняет триангуляцию области, ограниченной функциями F1(x) и G1(x), измельчение треугольников и применение градиентного спуска к крайним точкам триангуляции.

В качестве примеров, рассмотрим области, ограниченные неравенствами.

Пример 1 (2):

y ≥ x ²; y ≤ 1. (2)

Из данного неравенства следует, что нижняя функция ограничена параболой, а верхняя функция ограничена прямой.

Далее программа осуществляет вывод следующих графиков.

На изображении (рис. 3) также видны следующие элементы:

1. Синие точки – начальные точки для триангуляции.
2. Фиолетовые линии – границы треугольников начальной триангуляции.
3. Красная линия – граница области y= x².
4. Синяя горизонтальная линия – граница области y= 1.

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

На изображении (рис. 4) демонстрируется триангуляция после применения алгоритма измельчения до сдвига точек, находящихся на границе триангуляции внутри области.

Процесс измельчения заключается в следующем:

1. Для каждой стороны начального треугольника вычисляется средняя точка.
2. Эти средние точки добавляются как новые вершины.
3. Затем начальный треугольник делится на несколько более мелких треугольников, используя новые средние точки [9].

В результате после применения алгоритма измельчения количество треугольников увеличивается, что приводит к более детализированной и точной триангуляции. Визуальный результат:

1. Вершины новых треугольников отмечены синими точками.
2. Границы новых треугольников отмечены фиолетовыми линиями.

На графике (рис. 5) показана триангуляция Делоне для точек, перемещенных по градиенту функции F(x; y). Точки снова отмечены синим цветом, а треугольники образованы ребрами пурпурного цвета. Границы области остаются теми же (красная и синяя линии). Точки были перемещены по градиенту, не выходя за границы области.

Этот график (рис. 6) показывает сдвиг точек с помощью стрелок, указывающих направление и величину перемещения. Исходные точки отмечены синим цветом. Стрелки, нарисованные зеленым цветом, показывают сдвиг каждой точки.

Описание:

1. Синие точки представляют исходные координаты.
2. Зеленые стрелки указывают направление и величину сдвига точек. В некоторых случаях стрелки могут быть очень короткими или отсутствовать, если точки остались на месте (например, точки на границах).

Пример 2 (3):

y – x ² > 0; y – x < 0. (3)

Из данного неравенства следует, что нижняя функция ограничена параболой, а верхняя функция ограничена прямой.

На этом изображении (рис. 7) показана начальная триангуляция области, ограниченной параболой и прямой. Синие точки показывают начальные узлы, и треугольники построены на основе этих точек.

На этом изображении (рис. 8) показана триангуляция после измельчения начальных треугольников. Дополнительно введенные точки (на серединах ребер начальных треугольников) добавлены, что привело к увеличению количества треугольников. Этот процесс увеличивает число разбиений в области и обеспечивает более точное представление геометрии области.

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

Пример 3 (криволинейная трапеция).

Пусть Ω – плоская область, которая будет задана при помощи системы неравенств (4):

0 ≤ x ≤ 3,

{x ² – 3 × x – 2 ≤ y ≤ 3 × x – x ²}. (4)

Получится следующая триангуляция криволинейной трапеции, построенная при помощи алгоритма измельчения (рис. 11–12).

Разработанный в рамках исследования алгоритм триангуляции основывается на методе измельчения плоской области, ограниченной системой неравенств. Этот подход был реализован с помощью программной реализации, обеспечил высокую точность построения триангуляции благодаря градиентному сдвигу точек к границам области [10].

Графики, представленные на рис. 3–12, демонстрируют эффективность предложенного метода. Использование измельчения позволило значительно увеличить количество треугольников в пределах области, тем самым обеспечив более детализированную и точную аппроксимацию ее границ.

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

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

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

ЗАКЛЮЧЕНИЕ

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

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