Управляемая триангуляция
|
<< Оглавление >> Управляемая триангуляция |
  
|
Для построения моделей рельефа (или квазирельефа – произвольных статистических поверхностей) в ГИС применяется триангуляция Делоне, названная так по имени советского математика 30-х гг. 20 века Бориса Николаевича Делоне.
Триангуляция Делоне – это разбиение нерегулярного множества опорных точек на такую сеть треугольников, которая отвечала бы сформулированной еще в 30-е годы теореме Делоне о пустом шаре, которая в приложении к двумерному пространству формулируется следующим образом:
система взаимосвязанных неперекрывающихся треугольников имеет наименьший диаметр, если ни одна из вершин не попадает внутрь ни одной из окружностей, описанных вокруг образованных треугольников.
Это означает, что образовавшиеся треугольники при такой триангуляции максимально приближаются к равносторонним, а каждая из сторон образовавшихся треугольников из противолежащей вершины видна под максимальным углом из всех возможных для точек соответствующей полуплоскости.
Это именно та оптимальная триангуляция, по ребрам которой делается обычно линейная интерполяция для построения изолиний (возможны варианты и нелинейных интерполяций на этой же основе).
Базовый алгоритм
Отсюда следовал классический алгоритм построения триангуляции Делоне, который часто используется при моделировании (иногда этот алгоритм называется декрементным):
•выбор произвольной начальной точки (от выбора начальной точки результирующая триангуляция не зависит, триангуляция на данном множестве является однозначной с точностью до эквивалентных точек);
•поиск второй ближайшей точки, соединяющий точки отрезок является исходной базой для дальнейших построений;
•поиск в левой полуплоскости от базового отрезка точки, из которой базовый отрезок виден под максимальным углом (если в левой полуплоскости нет точек, попытка повторяется для правой полуплоскости);
•в дальнейшем в качестве базовых отрезков принимаются стороны треугольников, которые не имеют сопряженных треугольников, поиск нужных вершин всегда производится в левой полуплоскости относительно базового отрезка;
•процесс продолжается до тех пор, пока вершинами треугольников не будут закреплены все точки исходного множества.
Недостатки алгоритма:
•это алгоритм класса n**2, т.к. требуется аналитическое сравнение каждой точки со всеми остальными;
•алгоритм использует постоянно вычисляемые тригонометрические функции, что резко замедляет процесс;
•при исследовании взаимоотношения точек и базового отрезка сплошь и рядом возникают очень малые (и исчезающе малые) углы, и при использовании тригонометрических функций постоянно возникает опасность исчезновения порядка и деления на 0 в связи с ограниченной точностью представления данных в компьютере, эта ситуация требует постоянной дополнительной обработки;
•поскольку обработка идет до последней точки, т. е. в границах правильной выпуклой оболочки, при очень частых квазилинейных ограничениях множества на границах области образуются треугольники с исчезающе малыми углами, что часто приводит к трудно обрабатываемым тупиковым ситуациям.
Инкрементный алгоритм
Намного более эффективным является совершенно другой алгоритм, скорее комбинаторный, чем аналитический (иногда он называется инкрементным) (первое схематическое описание такого алгоритма было описано в работе М.Э.Агиштейн, А.А.Мигдал "Как увидеть невидимое?" в книге "Эксперимент на дисплее", М., "Наука", 1989).
Схема алгоритма такова:
1. Вначале делается любая произвольная триангуляция на заданном множестве точек.
2. Полученная триангуляция превращается в триангуляцию Делоне.
Для этого:
•последовательно для каждой из точек выбирается гнездо треугольников, имеющих эту точку в качестве общей вершины;
•для каждого из треугольников гнезда (последовательным обходом вокруг центральной вершины, скажем, по часовой стрелке) находится сопряженный треугольник, расположенный против этой центральной вершины;
•каждая полученная пара треугольников исследуется на соответствие требованиям теоремы Делоне и, если нужного соответствия нет, выполняется флип общей стороны треугольников с получением новых двух треугольников взамен старых.
Алгоритм работает несравненно быстрее, чем первоначально описанный, а главное, абсолютно надежно, устойчиво и безотказно.
На основании описанного алгоритма сконструирован очень полезный дополнительный алгоритм достраивания триангуляции, когда уже есть какая-то начальная триангуляция, которую нужно откорректировать в связи с появлением новых точек наблюдения.
Далее следует использование базовой триангуляции для конкретного прикладного моделирования.
(Заметим, что если говорить о GRID-моделях, то их не рекомендуется строить непосредственно на нерегулярной сети исходных точек – интерполяция по ребрам прямоугольной сетки приводит к несовпадению значений картируемого признака в исходных точках. Если и делать гридизацию для определенных приложений, то ее нужно делать после того как выполнена триангуляция).
Триангуляция в заданном контуре
Использование базового алгоритма ведет к формированию триангуляции Делоне в естественном выпуклом контуре.
Техника построения триангуляции Делоне в заданном контуре, по сути, является той же, что и техника проведения структурных линий по базовой триангуляции:
•выполняется триангуляция по схеме стандартной триангуляции Делоне (см. выше) в естественном выпуклом контуре.
•так же, как проводились структурные линии (см. выше), проводятся линии заданной границы; треугольники, оказавшиеся за пределами заданного контура, удаляются.
Следуя предложенной алгоритмической схеме, мы получаем триангуляцию Делоне в заданном контуре без создания каких-либо искусственных дополнительных узловых точек.