Триангуляция Делоне. Полигоны Вороного

Федеральное государственное  автономное

образовательное учреждение

высшего профессионального  образования

«СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ  УНИВЕРСИТЕТ»

Институт космических  и информационных технологий

Кафедра «Геоинформационные системы»

 

 

 

РЕФЕРАТ

По дисциплине «геоинформационные системы и технологии»

Триангуляция Делоне. Полигоны Вороного.

 

 

 

Студент	КИ10-14-3	19.10.13	Будник У.А.
	номер группы	подпись, дата	инициалы, фамилия
Преподаватель			Гостева А.А.
		подпись, дата	инициалы, фамилия

 

 

Содержание

Введение 3

1. Триангуляция Делоне 
1. Основные определения и задачи триангуляции Делоне 4
2. Теоремы для алгоритмов построения триангуляции Делоне 6
3. Структуры для представления триангуляции 7

1. Структура «Узлы с соседями» 7
2. Структура «Двойные ребра» 8
3. Структура «Узлы и треугольники» 9
4. Структура «Узлы, ребра и треугольники» 10
5. Структура «Узлы, простые ребра и треугольники» 10

2. Алгоритмы триангуляции Делоне 
1. Классификация алгоритмов триангуляции Делоне 12
2. Итеративные алгоритмы с кэшированием поиска треугольников 13
1. Алгоритм со статистическим кэшированием поиска 13
2. Алгоритм с динамическим кэшированием поиска 14
3. Полигоны Вороного 15

Заключение  16

Список использованной литературы 17 

Введение

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

 

1. Триангуляция Делоне
1. Основные определения и задачи построения триангуляции Делоне

 

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

Рис 1 - Триангуляция.

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

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

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

Одним из первых был предложен следующий алгоритм построения триангуляции.

Жадный алгоритм построения триангуляции.

Шаг 1. Генерируется список всех возможных отрезков, соединяющих пары исходных точек, и он сортируется по длинам отрезков.

Шаг 2. Начиная с самого короткого, последовательно выполняется вставка отрезков в триангуляцию. Если отрезок не пересекается с другими ранее вставленными отрезками, то он вставляется, иначе он отбрасывается.

Конец алгоритма.

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

Определение 5. Триангуляция называется жадной, если она построена жадным алгоритмом.

Определение 6. Говорят, что триангуляция удовлетворяет условию Делоне, если внутрь окружности, описанной вокруг любого построенного треугольника, не попадает ни одна из заданных точек триангуляции.

Определение 7. Триангуляция называется триангуляцией Делоне, если она является выпуклой и удовлетворяет условию Делоне.

Рис 2 - Триангуляция Делоне.

Определение 8. Говорят, что пара соседних треугольников триангуляции удовлетворяет условию Делоне, если этому условию удовлетворяет триангуляция, составленная только из этих двух треугольников.

Определение 9. Говорят, что треугольник триангуляции удовлетворяет условию Делоне, если этому условию удовлетворяет триангуляция, составленная только из этого треугольника и трёх его соседей (если они существуют).

 

2. Теоремы для алгоритмов построения триангуляции Делоне

 

Теорема 1. Триангуляцию Делоне можно получить из любой другой триангуляции по той же системе точек, последовательно перестраивая пары соседних треугольников ∆ABC и ∆BCD, не удовлетворяющих условию Делоне, в пары треугольников ∆ABD и ∆ACD. Такая операция перестроения также часто называется флипом.

Рис 3 - Флип.

Данная  теорема позволяет строить триангуляцию Делоне последовательно, построив вначале некоторую триангуляцию, а потом последовательно улучшая её до выполнения условия Делоне.

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

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

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

1.3 Структуры  для представления триангуляции

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

1.3.1 Структура узлы с  соседями

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

Рис 4 - Структура данных триангуляции и связи узлов структуры «Узлы с соседями»

1.3.2 Структура «Двойные рёбра»

Основой триангуляции является список ориентированных рёбер. При этом каждое ребро входит в структуру триангуляцию дважды, но направленными в противоположные стороны.

Для каждого ребра хранятся следующие  указатели:

1. на концевой узел ребра;
2. на следующее по часовой стрелке ребро в треугольнике, находящемся справа от данного ребра;
3. на «ребро-близнец», соединяющее те же самые узлы триангуляции, что и данное, но направленное в противоположную сторону;

4) на треугольник, находящийся  справа от ребра.

Рис 5 - Структура данных триангуляции, связи рёбер (слева) и неявное задание треугольников (справа) в структуре «Двойные рёбра».

 

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

Недостатками  данной структуры является представление  треугольников в неявном виде, а также большой расход памяти, составляющий при 8-байтовом представлении координат и 4-байтовых указателях не менее 64 • N байт (не учитывая расход памяти на представление дополнительных данных в треугольниках).

1.3.3Структура «Узлы и треугольники»

Для каждого треугольника хранятся три указателя на образующие его узлы и три указателя на смежные треугольники.

 

 

 

 

 

Рис 6 - Структура данных триангуляции и связи треугольников структуры «Узлы и треугольники»

 

Нумерация точек  и соседних треугольников производится в порядке обхода по часовой стрелке, при этом напротив точки с номером i {1, 2, 3} располагается ребро, соответствующее соседнему треугольнику с таким же номером.

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

При 8-байтовом представлении  координат и 4-байтовых указателях данная структура триангуляции требует  примерно 64 • N байт.

Данная структура  уступает «Узлам с соседями», но она наиболее часто применяется на практике в силу своей относительной простоты и удобства программирования алгоритмов на её основе.

1.3.4 Структура «Узлы, рёбра и треугольники»

В структуре «Узлы, рёбра и треугольники» в явном виде задаются все объекты триангуляции: узлы, рёбра и треугольники. Для каждого ребра хранятся указатели на два концевых узла и два соседних треугольника. Для треугольников хранятся указатели на три образующих треугольник ребра.

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

Недостатком данной структуры  является большой расход памяти, составляющий при 8-байтовом представлении координат и 4-байтовых указателях примерно 88⦁N байт.

 

Рис 7 - Структура данных триангуляции «Узлы, рёбра и треугольники» , связи треугольников (слева) и рёбер (справа) структуры «Узлы, рёбра и треугольники»

1.3.5Структура данных «Узлы, простые рёбра и треугольники»

В структуре «Узлы, простые рёбра и треугольники» в явном виде задаются все объекты триангуляции: узлы, рёбра и треугольники. Для каждого ребра хранятся указатели на два концевых узла и два соседних треугольника. Для рёбер никакой специальной информации нет. Для треугольников хранятся указатели на образующих треугольник три узла и три ребра, а также указатели на три смежных треугольника.

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

Недостатком данной структуры является относительно большой расход памяти, составляющий при 8-байтовом представлении координат и 4- байтовых указателях примерно 80 • N байт.

Рис 8 - Структура данных «Узлы, простые рёбра и треугольники»

В целом можно  отметить, что структура «Узлы  с соседями» менее удобна, чем  остальные, так как не представляет в явном виде рёбра и треугольники. Среди остальных достаточно удобной в программировании является структура «Узлы и треугольники». Однако некоторые алгоритмы триангуляции Делоне требуют представления рёбер в явном виде, поэтому там можно порекомендовать структуру «Узлы, рёбра и треугольники».

 

2 Алгоритмы триангуляции Делоне

2.1 Классификация алгоритмов  триангуляции Делоне

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

Рисунок 9 – Классификация алгоритмов построения триангуляции Делоне.

2.2 Итеративные алгоритмы с кэшированием поиска треугольников

Рассмотрим подробнее  итеративные алгоритмы с кэшированием поиска треугольников.

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