1. Триангуляционная сетка и автоматизация её построения.
2. Описание предметной области.
3. Алгоритм.
4. Интерфейс.
5. Перспективы.

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

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

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

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

1. Выбор обрабатываемой точки: инкрементность разработанного алгоритма позволяет в любой момент времени работать с одной точкой и структурой, полученной на предыдущих шагах
2. Определение местоположения "рабочей" точки: возможны варианты попадания в один из ранее построенных треугольников (в этом случае производится ликвидация этого треугольника и появление трёх новых (на базе четырёх точек - новой и трёх вершинах ликвидированного треугольника)), попадания в два треугольника (оба треугольника расформировываются, образуются четыре новых), попадания в три треугольника (этот случай соответствует ошибочному или дублирующему вводу данных) и, наконец, случай "промаха" точки мимо конструкции из ранее построенных треугольников (в этом случае все внешние отрезки имеющейся триангуляции проверяются на возможность соединения отрезком с добавляемой точкой без нарушения правила непересекаемости треугольников, проводится это путем анализа подстановки координат обрабатываемой точки в приведенные к нужному виду уравнения внешних сторон триангуляции).
3. Анализ вновь построенных треугольников на возможность флипов: для всех возможных пар вновь созданный треугольник - его сосед строится пара треугольников, полученных переброской смежного ребра, из этих двух пар оставляется та, которая имеет больший минимальный угол. Вновь созданные треугольники добавляются в список проверяемых.

Проблемы:

• Необходимость предупреждения повторного включения одних и тех же ребер (полученных как результат анализа разных внешних отрезков) в список внешних.
• Поиск соседних треугольников.
• Обработка многочисленных вариантов взаимного расположения соседних треугольников.
• Работа с громоздкими структурами данных: более половины всех функций и процедур предназначены для взаимодействия с объектами типов triangle, line, array of triangle…. И это с учетом того, что не использовалась несколько разгружающая основную программу модифицированная версия структуры триангуляционных данных, предложенная J.R.Shewchuk-ом.

Вышеописанный алгоритм реализован в среде программирование Delphi.

V1.2 программного продукта предоставляет пользователям следую-щие возможности:

• Триангулирование набора данных.
• Визуализация построенных треугольников.
• Возможность показывать/скрывать вспомогательные элементы.
• Работа с предопределенными наборами данных.
• Добавление произвольных данных.

В ближайшем будущем планируется:

• Интеграция в алгоритм процедуры оптимизации поиска треугольника. (Вводится вспомогательная прямоугольная сетка, в каждую из ячеек которой попадает некоторое число треугольников. Определив, к какой ячейке принадлежит исследуемая точка, локализуются ' подозрительные ' треугольники).
• Реализация оптимизированной процедуры включения в триангуляционную сеть внешней точки. (V 1.2 программного продукта использует процедуру, имеющую квадратичную зависимость скорости работы от количества внешних отрезков, в то время как уже разработан алгоритм, имеющий линейную зависимость).
• Реализация процедуры удаления точки из триангуляционной сетки.
• Визуализация списка имеющихся в наличии точек
• Документирование программного продукта.
• Проведение анализа имеющейся триангуляционной сетки с генерацией рекомендаций по расположению добавляемых точек, способствующему улучшению свойств конструкции (ликвидация 'узких' треугольников).
• Непосредственное решение, приводившейся в начале задачи построения проходящей через опорные точки гладкой функции.