Описание препроцессора (стр. 4 )

Пример 2. Триангуляция с использованием функции плотности.

Распределение плотности

Результат триангуляции с использованием функции плотности

Модуль триангуляции по Делоне

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

Форма модуля триангуляции по Делоне

Триангуляция Делоне является одним из самых популярных в последнее время способов построения триангуляционной сетки. Она применяется во многих ГИС системах для построения моделей рельефа.

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

Триангуляция Делоне

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

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

Для формирования триангуляции Делоне потребуется несколько новых определений. Набор точек считается круговым, если существует некоторая окружность, на которой лежат все точки набора. Такая окружность будет описанной для данного набора точек. Описанная окружность для треугольника проходит через все три ее (не коллинеарные) вершины. Говорят, что окружность будет свободной от точек в отношении к заданному набору гочек S, если внутри окружности нет ни одной точки из набора S. Но, однако, точки из набора S могут располагаться на самой свободной от точек окружности.

Триангуляция набора точек S будет триангуляцией Делоне, если описанная окружность для каждого треугольника будет свободна от точек.

Для упрощения алгоритма триангуляции можно сделать два предположения относительно точек в наборе S. Во-первых, чтобы вообще существовала триангуляция, мы должны полагать, что набор S содержит по крайней мере три точки и они не коллинеарны. Во-вторых, для уникальности триангуляции Делоне необходимо, чтобы никакие четыре точки из набора S не лежали на одной описанной окружности. Легко видеть, что без такого предположения гриангуляция Делоне не будет уникальной, ибо 4 точки на одной описанной окружности позволяют реализовать две различные триангуляции Делоне.

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

Генерация набора опорных точек;

Реализация алгоритма триангуляции.

Решение первой задачи система предлагает одним из следующих методов:

Хаотическая генерация точек;

Хаотическая генерация точек с распределение плотности;

Прямоугольная регулярная;

Равноугольная регулярная;

Использование узлов уже имеющейся сетки.

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

Объемлющий прямоугольник области .

При генерации точек в прямоугольнике ) нужно проверять попала ли точка в область , и только в случае положительного ответа помещать во множество . К тому же, надо убедиться что .

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

Методы генерации точек

Хаотическая генерация точек.

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

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

Пользователь препроцессора имеет возможность задать следующие параметры алгоритма генерации:

Количество точек на зону;

Минимальное расстояние между точками ;

Предельное количество попыток генерации координат новой точки.

Хаотическая генерация точек с распределением плотности.

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