Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

КУРСОВОЙ ПРОЕКТ

ПОСТРОЕНИЕ ТРИАНГУЛЯЦИИ ДЕЛОНЕ

по дисциплине "Структуры и алгоритмы обработки данных "

Содержание

• Введение
• 2.1 Жадный алгоритм
• 2.4 Алгоритм с индексированием центров треугольников k - D - деревом
• 3.4 Веерный алгоритм
• 4. Программная часть
• Заключение

Введение

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

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

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

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

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

1) Изучить основные определения и теоремы задачи триангуляции Делоне;

2) Рассмотреть основные виды итеративных алгоритмов построения триангуляции;

3) Реализовать алгоритм "Удаляй и строй" построения триангуляции Делоне.

1. Общее описание триангуляции делоне

Задача построения триангуляции.

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

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

1.1 Анализ литературы по теме

Скворцов А .В. Триангуляция Делоне и ее применение . /Скворцов А .В. - Томск : Изд-во Том . Ун-та, 2002 . - 128с . Данное учебное пособие является основным для данного курсового проекта. В нем подробно описываются теоретические сведения, связанные с триангуляцией Делоне, даются различные определения и теоремы.

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

Что позаимствовано : основной материал, теоретические сведения, определения, рисунки.

Попов С .А. Вычислительные методы и программирование . /Попов С .А. - Москва : Изд-во МГУ, 2008, - 24с . Это методическое пособие является вспомогательным источником литературы. Описываются некоторые алгоритмы с математической точки зрения, вычисляются формулы для построения, а также есть описание триангуляция в евклидовом пространстве

Что позаимствовано : математическое описание триангуляции Делоне, построение на евклидовом пространстве

Медведев Н .Н. Метод Вороного - Делоне в исследовании структуры некристаллических систем / РАН, Новосиби рск : Изд-во СО РАН, 2000, - 214 с . Книга, посвященная описанию методов Вороного и Делоне в некристаллических системах.

Что позаимствовано : свойства триангуляций Делоне, определение триангуляции Делоне.

1.2 Основные определения и свойства

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

Свойства :

· Триангуляция Делоне взаимно однозначно соответствует диаграмме Вороного для того же набора точек.

· Как следствие: если никакие четыре точки не лежат на одной окружности, триангуляция Делоне единственна.

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

· Триангуляция Делоне максимизирует сумму радиусов вписанных шаров.

· Триангуляция Делоне минимизирует дискретный функционал Дирихле.

· Триангуляция Делоне минимизирует максимальный радиус минимального объемлющего шара.

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

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

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

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

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

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

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

1.3 Метод пустого шара Делоне. Построение в общем случае

Воспользуемся пустым шаром, который мы будем перемещать, изменяя его размер так, чтобы он мог касаться точек системы {А}, но всегда оставался пустым.

Итак, поместим в систему точек {А} пустой шар Делоне. Это всегда возможно, если выбрать шар достаточно малым. Начнем увеличивать его радиус, оставляя центр шара на месте. В какой-то момент поверхность шара встретит некоторую точку i системы {А}. Это обязательно произойдет, ибо в нашей системе нет неограниченно больших пустот. Будем продолжать увеличивать радиус пустого шара так, чтобы точка i оставалась на его поверхности. Для этого придется двигать центр шара от точки i. Рано или поздно шар достигнет своей поверхностью другой точки системы {А}.

Рис.3 - Разбиение Делоне двумерной системы точек

Симплексы Делоне заполняют пространство без щелей и наложений.

Описанная сфера любого симплекса не содержит внутри себя других точек системы.

Пусть это будет точка j. Продолжим увеличивать радиус нашего шара, сохраняя уже обе точки на его поверхности. Увеличиваясь, шар достигнет какой-то третьей точки системы, точки k. В двумерном случае наш "пустой круг" в этот момент зафиксируется, т.е. станет невозможным дальнейшее увеличение его радиуса при сохранении круга пустым. При этом мы выявляем элементарную двумерную конфигурацию трех точек (i,j,k), определяющую некий треугольник, особенностью которого является то, что внутри его описанной окружности нет других точек системы {А}. В трехмерном пространстве шар не определяется тремя точками. Продолжим увеличивать его радиус, сохраняя все три найденные точки на его поверхности. Это будет возможно до тех пор, пока поверхность шара не встретится с четвертой точкой l системы. После этого движение и рост пустого шара станут невозможными. Найденные четыре точки (i,j,k,l) определяют вершины тетраэдра, который характерен тем, что внутри его описанной сферы нет других точек системы {А}. Такой тетраэдр называется симплексом Делоне.

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

Мы построили один симплекс Делоне, однако, помещая пустой шар в различные места и повторяя ту же процедуру, можно определить и другие. Утверждается, что совокупность всех симплексов Делоне системы {А} заполняет пространство без наложений и щелей, т.е. реализует разбиение пространства, но на этот раз на тетраэдры. Это разбиение называется разбиением Делоне (рис.3).

1.4 Применение триангуляции Делоне

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

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

Еще одной часто возникающей в геоинформатике задачей является построение экспозиций склонов. Здесь требуется определить доминирующие направления склонов по странам света и разбить поверхность на регионы, в которых доминирует некоторое определенное направление. Так как для горизонтальных участков поверхности определение экспозиции не имеет смысла, то в отдельный регион выделяют области, являющиеся горизонтальными или имеющие незначительный уклон, например б<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.

Рис.4. Пример расчета экспозиций склонов по модели рельефа

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

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

2. Описание алгоритмов построения

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

Дано множество из N точек .

1. На первых трех исходных точках строим один треугольник.

2. В цикле по n для всех остальных точек выполняем шаги 3-5.

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

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

5. Проводятся локальные проверки вновь полученных треугольников на соответствие условию Делоне и выполняются необходимые перестроения.

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

Ниже приводится подробное описание нескольких алгоритмов .

2.1 Жадный алгоритм

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

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

1. Во множество исходных точек помещаются концы всех структурных отрезков.

2. Генерируются отрезки, соединяющие все пары точек, отрезки сортируются по длине.

3. В триангуляцию вставляются все отрезки структурных линий.

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

Шаг 4 повторяется, пока не кончатся отрезки.

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

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

2.2 Алгоритм "Удаляй и строй"

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

Рис. 4. Алгоритм "Удаляй и строй"

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

2.3 Алгоритм "Строй, разбивая"

Алгоритм вставки структурных отрезков "Строй, разбивая" является наиболее простым в реализации и устойчивым в работе.

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

Рис. 5. Алгоритм "Строй, разбивая"

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

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

2.4 Алгоритм с индексированием центров треугольников k-D - деревом

В алгоритме триангуляции с индексированием центров треугольников k -D-деревом в k-D-дерево (при k = 2) помещаются только центры треугольников. При удалении старых треугольников необходимо удалять их центры из k-D-дерева, а при построении новых - заносить.

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

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

3. Оценка эффективности алгоритмов

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

3.1 Простой итеративный алгоритм

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

При этом в худшем случае приходится пересекать все треугольники триангуляции, поэтому трудоемкость такого поиска составляет O (N). Однако в среднем для равномерного распределения в квадрате нужно совершить только O () операций перехода. Таким образом, трудоемкость простейшего итеративного алгоритма составляет в худшем, а в среднем -

3.2 Итеративный алгоритм с индексированием треугольников

Трудоемкость поиска треугольника в R-дереве в худшем случае составляет O (N), а в среднем O (log N). При этом может быть найдено от 1 до N треугольников, которые надо затем все проверить. Кроме того, появляются дополнительные затраты времени на поддержание структуры дерева - O (log N) при каждом построении и удалении треугольников. Отсюда получаем, что трудоемкость алгоритма триангуляции с индексированием треугольников в худшем случае составляет, а в среднем - O (N log N).

3.3 Итеративный алгоритм с индексированием центров треугольников k-D-деревом

Трудоемкость поиска точки в k-D-дереве в худшем случае составляет O (N), а среднем - O (logN). Далее может быть задействована процедура перехода по треугольникам, которая может иметь трудоемкость в худшем случае O N (). Также здесь имеются дополнительные затраты времени на поддержание структуры дерева - O N (log) при каждом построении и удалении треугольников.

Отсюда получаем, что трудоемкость алгоритма триангуляции с индексированием центров треугольников в худшем случае составляет, а в среднем - O (N log N).

3.4 Веерный алгоритм

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

Трудоемкость такого алгоритма составляет в среднем O N (). Алгоритм работает примерно с той же скоростью, что и предыдущий алгоритм.

4. Программная часть

Программа была разработана в среде разработки Microsoft Visual Studio 2012. Приложение представляет собой окно, в котором пользователь может произвольно добавлять точки, которые сразу соединяются в триангуляцию Делоне. Справа выводится список координат всех добавленных точек.

main. cpp - оконные функции, функции для работы с пользовательским интерфейсом

delone. cpp - алгоритм и функции, которые необходимы для работы с ним

Описание функций программы:

void DrawPoint (int x, int y) - функция рисования точки в окне приложения

void Triangulation () - функция для выполнения триангуляции

void TriangulationIn () - функция для выполнения действий с точками, который оказались внутри треугольника

void TriangulationOut () - функция для выполнения действий с точками, который оказались вне треугольника.

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

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

Рис. 6. Интерфейс программы

Заключение

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

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

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

1. Скворцов А.В. Триангуляция Делоне и ее применение. /Скворцов А.В. - Томск: Изд-во Том. Ун-та, 2012. - 128с.

2. Попов С.А. Вычислительные методы и программирование. /Попов С.А. - Москва: Изд-во МГУ, 2008, - 24с.

3. Медведев Н.Н. Метод Вороного - Делоне в исследовании структуры некристаллических систем / РАН, Новосибирск: Изд-во СО РАН, 2009, - 214с.

Размещено на Allbest.ru

Подобные документы

Метод пустого шара Делоне. Симплициальное разбиение (триангуляция). Особенности взаимного расположения симплексов Делоне. Алгоритм построения круга Делоне. Возможности программирования с помощью технологии Microsoft Windows Presentation Foundation.

курсовая работа , добавлен 14.05.2011


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

краткое изложение , добавлен 11.02.2010


Теоретическое исследование вопроса и практическое применение. Общие сведения о графах. Алгоритм Дейкстры. Особенности работы в среде. Программная реализация. Описание алгоритма и структуры программы. Описание программных средств. Текст программы.

курсовая работа , добавлен 27.11.2007


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

презентация , добавлен 19.08.2013


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

курсовая работа , добавлен 17.11.2011


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

курсовая работа , добавлен 11.03.2014


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

курсовая работа , добавлен 11.06.2012


Семантические сети как модели представления знаний. Основные методы определения сходства графовых моделей систем. Метод решения задач определения сходства семантических сетей на основе их сложности. Разработка алгоритмов и их программная реализация.

дипломная работа , добавлен 17.12.2011


Описание процесса сканирования в упрощенном виде. Описание компонентов метамодели и их возможных состояний. Инициаторы и результанты, классы эквивалентности. Операции над процессами: репозиция, редукция, композиция. Построение сети Петри и ее свойства.

курсовая работа , добавлен 13.06.2011


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

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

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

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

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

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

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

Рис. 9.7.1. Выпуклая область с заданными точками внутри

Пусть даны некоторая выпуклая двухмерная область, ограниченная замкнутой ломаной линией, и набор точек внутри этой области (рис. 9.7.1).

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

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

Рис. 9.7.2. Выбор третьей точки алгоритма Делоне

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

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

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

Через вершины А, В и любую, не лежащую с ними на одной прямой, вершину можно провести окружность. В качестве третьей вершины треугольника выберем вершину V, соответствующая которой окружность, не содержит других вершин с той же стороны относительно отрезка АВ, с которой лежит точка V. Для граничного ребра в общем случае можно найти одну такую вершину. Будем называть ее ближайшей. Центр окружности, проходящей через точки А, В и V, лежит на пересечении перпендикуляров к серединам отрезков АВ, BV и VА. Положение центра окружности будем характеризовать параметром t отрезка MN, перпендикулярного ребру АВ, равного с ним по длине и проходящего через середину ребра АВ.

Рис. 9.7.3. Процесс триангуляции Делоне

Для всех вершин, лежащих слева от отрезка АВ, ближайшая вершина имеет наименьший параметр t. Соответствующая ближайшей вершине окружность не содержит других вершин слева от отрезка АВ. Пусть вершины А, В и V описываются двухмерными радиус-векторами соответственно. Радиус-векторы середин отрезков АВ и BV будут равны

Значение параметра t прямой , соответствующее положению на ней центра окружности, проходящей через точки А, В и V, равно

Для ближайшей слева к отрезку АВ вершины параметр t имеет минимальное значение.

Сориентируем все граничные ребра так, чтобы подлежащая триангуляции область лежала слева от каждого из них. Построение треугольников начнем с любого граничного ребра. Найдем для него ближайшую вершину, соответствующая окружность которой не содержит других вершин. Пусть для граничного ребра АВ найдена ближайшая вершина V. Тогда построим треугольник ABV и переведем ребро АВ в разряд неактивных. Неактивными будем называть ребра и вершины, которые не участвуют в алгоритме триангуляции. Если среди граничных ребер отсутствует ребро BV, то на отрезке VB построим новое граничное ребро. Если же среди граничных ребер есть ребро BV, то переведем его и вершину В в разряд неактивных. Если среди граничных ребер отсутствует ребро VA, то на отрезке AV построим новое граничное ребро. Если же среди граничных ребер есть ребро VA, то переведем его и вершину А в разряд неактивных. Процесс триангуляции показан на рис. 9.7.3.

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

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

Триангуляция методом коррекции.

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

Параметрические расстояния между соседними линиями в соответствии с формулой (9.4.8) возьмем равными

Построив диагонали во всех прямоугольных ячейках, мы получим триангуляцию поверхности (получим набор треугольников, удовлетворяющий предъявленным требованиям). На рис. 9.7.5 приведена триангуляция поверхности вращения описанным способом.

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

Рис. 9.7.5. Триангуляция поверхности с прямоугольной областью определения параметров

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

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

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

Рис. 9.7.6. Незаконченная триангуляция поверхности

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

На непересеченных сторонах ячеек второй группы построим граничные ребра и направим их так, чтобы соответствующая ячейка находилась слева от ребра. Вокруг ячеек первой группы построим замкнутую ломаную линию (возможно несколько замкнутых линий) так, чтобы при движении по ней не разбитая на треугольники часть области лежала слева, если смотреть навстречу нормали поверхности. Прямолинейные участки этой ломаной линии также будем использовать в качестве граничных ребер. Мы будем считать все ребра равноправными. Для завершения триангуляции нам необходимо построить треугольники между граничными ребрами. Для каждого ребра будем искать вершину, которая лежит слева от него и может быть использована для построения треугольника. Поиск вершины будем осуществлять только среди тех вершин, которые лежат в одной ячейке с ребром. Для выбора вершины используем метод Делоне, описанный выше, и проиллюстрированный на рис. 9.7.2. Если такая вершина найдена, то следует проверить, не пересекаются ли два новых ребра треугольника с каким-либо граничным ребром. Пусть для граничного ребра АВ найдена ближайшая вершина V и проверено, что отрезки BV и VА не пересекают другие граничные ребра. Тогда построим треугольник ABV и переведем ребро АВ в разряд неактивных. Если среди граничных ребер отсутствует ребро BV, то на отрезке VВ построим новое граничное ребро, если же среди граничных ребер есть ребро BV, то переведем его и вершину В в разряд неактивных. Если среди граничных ребер отсутствует ребро VA, то на отрезке AV построим новое граничное ребро, если же среди граничных ребер есть ребро VA, то переведем его и вершину А в разряд неактивных.

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

Рис. 9.7.7. Триангуляция методом коррекции

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

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

Триангуляция методом поглощения.

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

Для этого вычислим допустимые приращения параметров вдоль координатных линий

где - коэффициенты первой и второй квадратичных форм поверхности в точке . За границу искомой области примем эллипс с центром в точке и полуосями . Этот эллипс имеет уравнение

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

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

Найдем в рабочем полигоне вершину, в которой он поворачивает внутрь области. Такая точка всегда существует и угол поворота в ней меньше . Обозначим эту точку через О, а ее параметры - через Около этой точки построим один или два треугольника в зависимости от угла поворота. Если угол меньше то построим один треугольник на этих трех точках (рис. 9.7.9). В противном случае построим два треугольника на данной, двух соседних и одной новой точках (рис. 9.7.11). Новая точка обозначена через Р. Точку Р будем искать на диагонали параллелограмма В ОС Р. Если вершина параллелограмма лежит внутри эллипса (рис. 9.7.10), то примем ее за точку Р. В противном случае за точку Р примем пересечение эллипса и диагонали параллелограмма. В последнем случае совсем не обязательно искать пересечение эллипса и отрезка.

Координаты точки Р определяются через координаты точек О ВС

Угол отрезка ОР с горизонталью определяется равенством

(9.7.8)

Эти данные позволяют определить положение точки Р относительно эллипса (9.7.5).

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

Рис. 9.7.9. Построение треугольника

Рис. 9.7.10. Результирующий полигон

Рис. 9.7.11. Построение двух треугольников

Рис. 9.7.12. Результирующий полигон

Такие ситуации показаны на рис. 9.7.13. Они могут возникнуть, когда стороны построенных треугольников пересекут несмежные с ними стороны рабочего полигона. Перед построением нового треугольника как в случае, показанном на рис. 9.7.9, так и в случае, показанном на рис. 9.7.11, должна быть выполнена проверка на отсутствие самопересечения результирующего полигона.

Более того, при определении положения точки Р важно, чтобы она находилась на достаточном расстоянии от других точек рабочего полигона и не подходила близко к отрезкам, соединяющим точки полигона. Иначе могут возникнуть трудности в дальнейшем при построении треугольников. Поэтому прежде, чем сузить рабочий полигон, следует проверить на самопересечение результирующий полигон. Если около точки О нельзя построить треугольник (треугольники), то вместо нее следует найти другую точку, в которой полигон более, чем в других, заворачивает внутрь контура, и выполнить в ней описанные действия.

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

Рис. 9.7.13. В данном углу строить треугольники нельзя

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

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

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

Пусть мы проверяем возможность построения двух треугольников в точке О (рис. 9.7.11), и обнаружили, что новая точка Р, будучи построенной, попадет внутрь одного из внутренних полигонов или окажется в недопустимой близости от его отрезков. В этом случае мы не будем строить точку Р, а вместо этого включим в рабочий полигон данный внутренний полигон, построив два треугольника, показанных на рис. 9.7.14.

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

Построим треугольники на точках OCF и CEF и между точками О и С рабочего полигона вставим точки внутреннего полигона, начиная с точки F и кончая точкой Е. Тем самым мы разорвем рабочий полигон на отрезке ОС, разорвем внутренний полигон на отрезке EF и объединим их отрезками OF и ЕС.

Рис. 9.7.14. Построение двух треугольников

Рис. 9.7.15. Слияние внешнего и внутреннего полигонов

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

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

Рис. 9.7.16. В данном углу строить треугольники нельзя

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

Другие способы триангуляции.

Существуют и другие способы триангуляции. Например, после построения полигонов внешнего и внутренних контуров области определения поверхности может быть выбрана иная стратегия построения треугольников. В другом варианте можно перед началом триангуляции объединить внешний и внутренние полигоны в один полигон. Можно внутри области определения параметров по определенному алгоритму «набросать» точки и по ним и точкам полигонов граничных контуров выполнить триангуляцию Делоне. Существуют алгоритмы, строящие сначала крупные треугольники, а затем делящие их до приемлемых размеров.

Триангуляция тела.

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

Рис. 9.7.17. Согласованность граничных полигонов граней тела

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

Применение триангуляции.

Построенные в результате триангуляции треугольники используются для получения тоновых изображений. На рис. 9.7.18 и 9.7.19 приведены триангуляции грани листового тела, тоновое изображение которого показано на рис. 6.5.1.

Рис. 9.7.18. Триангуляция грани тела методом коррекции

Разбиение области определения параметров поверхности на треугольники может быть использовано в интегралах (8.6.2), (8.6.3), (8.6.12), (8.7.17)-(8.7.22) при вычислении геометрических характеристик тел. При численном интегрировании параметрический шаг для кривых следует вычислять по формуле (8.11.5), а для поверхностей параметрические шаги следует вычислять по формулам (8.11.1) и (8.11.2).

Структура лекции Определения Определения Области применения Области применения Свойства триангуляции Делоне Свойства триангуляции Делоне Методы построения триангуляции Делоне Методы построения триангуляции Делоне Методы пошагового ввода Методы пошагового ввода Методы пошаговой выборки Методы пошаговой выборки Методы декомпозиции Методы декомпозиции Методы сканирования Методы сканирования Двухпроходные методы Двухпроходные методы

Триангуляция Триангуляция – планарный граф все внутренние области которого являются треугольниками. Триангуляция – планарный граф все внутренние области которого являются треугольниками. Термин «Триангуляция» - это Термин «Триангуляция» - это граф; граф; процесс построения графа. процесс построения графа. Задача триангуляции набора точек S – задача соединения всех точек набора S непересекающимися отрезками для получения графа триангуляции. Задача триангуляции набора точек S – задача соединения всех точек набора S непересекающимися отрезками для получения графа триангуляции. Определение триангуляции Набор точек S

Оптимальная триангуляция – триангуляция с минимальной суммой длин всех ребер графа. Оптимальная триангуляция – триангуляция с минимальной суммой длин всех ребер графа. ! Востребованная, но очень трудоемкая задача O(2 n) ! На практике используют аппроксимации (приближения к) оптимальной триангуляции: «Жадная» триангуляция O(N 2 *logN) «Жадная» триангуляция O(N 2 *logN) Триангуляция Делоне O(N*logN) Триангуляция Делоне O(N*logN) Определение оптимальной триангуляции

Триангуляция Делоне (DT(S)) – выпуклая триангуляция удовлетворяющая условию Делоне: Триангуляция Делоне (DT(S)) – выпуклая триангуляция удовлетворяющая условию Делоне: внутрь окружности описанной вокруг любого ее треугольника недолжна попадать ни одна из вершин графа. внутрь окружности описанной вокруг любого ее треугольника недолжна попадать ни одна из вершин графа. Определение триангуляции Делоне У словие Делоне выполняется У словие Делоне не выполняется Б.Н. Делоне ()

Применение триангуляции Делоне В других задачах ВГ В других задачах ВГ Минимальный остов набора точек Минимальный остов набора точек Построение буферных зон Построение буферных зон Построение диаграммы Вороного (зон близости) Построение диаграммы Вороного (зон близости) Нахождение максимальной пустой окружности Нахождение максимальной пустой окружности и др. и др. В приложениях в КГ, ГИС, ГМ в САПР В приложениях в КГ, ГИС, ГМ в САПР Полигональные модели поверхностей Полигональные модели поверхностей Рельефы в ГИС, скульптуры, пром.модели, модели в играх, Рельефы в ГИС, скульптуры, пром.модели, модели в играх, Численный анализ моделей Численный анализ моделей Изолинии, Изоклины, МКЭ. Изолинии, Изоклины, МКЭ.

Свойства любой выпуклой триангуляции 1. Для набора n точек из которых m - внутренние Количество треугольников триангуляции = n + m – 2 Количество треугольников триангуляции = n + m – 2 Количество ребер триангуляции 3n – 6 Количество ребер триангуляции 3n – 6Пример: Точек (n) – 13 Точек (n) – 13 Внутренних (m) – 4 Внутренних (m) – 4 Треугольников – 15 = Треугольников – 15 = Ребер – 26 3*13-6 = 33 Ребер – 26 3*13-6 = 33

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

Методы построения триангуляции Делоне Методы пошагового ввода Методы пошагового ввода Итеративные алгоритмы () Итеративные алгоритмы () Методы пошаговой выборки Методы пошаговой выборки Алгоритмы прямого (пошагового) построения (3) Алгоритмы прямого (пошагового) построения (3) Методы декомпозиции Методы декомпозиции Алгоритмы слияния (2) Алгоритмы слияния (2) Методы сканирования Методы сканирования Итеративные алгоритмы с измененным порядком добавления точек (1.4) Итеративные алгоритмы с измененным порядком добавления точек (1.4) Двухпроходные алгоритмы (4) Двухпроходные алгоритмы (4)

Методы пошагового ввода Итеративные алгоритмы () Общая схема итеративных алгоритмов построения триангуляции Делоне 1. На первых трех точках построить один треугольник 2. Цикл по всем оставшимся точкам p i набора S 3. Найти ближайший к точке p i треугольник t j текущей триангуляции 4. Если точка p i снаружи треугольника t j, то построить треугольники к ближайшему ребру. 5. Если точка p i внутри треугольника t j, то разбить треугольник на три. 6. Если точка p i на ребре, то разбить прилегающие треугольники на пары. 7. Если условие Делоне для соседей нарушилось, то перестроить соседние треугольники. Варианты ускорения поиска треугольников: Индексирование треугольников (деревья) – O(log n) Индексирование треугольников (деревья) – O(log n) Кэширование треугольников (сетки) – O(с) Кэширование треугольников (сетки) – O(с)

Методы пошаговой выборки Алгоритмы прямого (пошагового) построения (3) Строить сразу нужные треугольники, не перестраивая что уже построено. Общая схема алгоритмов прямого построения триангуляции Делоне Удобно использовать стек еще необработанных ребер. 1. Найти любое ребро q выпуклой оболочки набора точек S. 2. Занести ребро q в стек необработанных ребер. 3. Цикл пока стек необработанных ребер не пуст. 4. Извлечь ребро v из стека. 5. Для ребра v найти точку p, удовлетворяющую условию Делоне (соседа Делоне) 6. Если сосед Делоне p найден, то 7. Построить треугольник от ребра v к точке p. 8. Занести новые ребра нового треугольника в стек необработанных ребер. Варианты ускорения поиска соседа Делоне: Индексирование точек k-D-деревом – O(log n) Индексирование точек k-D-деревом – O(log n) Клеточное индексирование точек – O(с) Клеточное индексирование точек – O(с)

Процесс работы жадного алгоритма триангуляции Делоне

Методы декомпозиции Алгоритмы слияния (2) Разбиение на подмножества, независимая обработка, слияние результатов. Общая схема алгоритмов слияния 0. Если точек в наборе S не более 3 шт, построить непосредственно иначе 1. Разбить набор точек S на примерно равные подмножества. 1. Разбить набор точек S на примерно равные подмножества. 2. Построение триангуляции для подмножеств. 2. Построение триангуляции для подмножеств. 3. Слияние полученных триангуляций в одну. 3. Слияние полученных триангуляций в одну. Способы разделения на подмножества Ортогональными прямыми Ортогональными прямыми По диаметру выпуклой оболочки По диаметру выпуклой оболочки Полосами Полосами

Алгоритмы слияния (2) Способы слияния триангуляций «Удаляй и строй» (проверка до построения) «Удаляй и строй» (проверка до построения) «Строи и перестраивай» (проверка после построения) «Строи и перестраивай» (проверка после построения) «Строй, перестраивая» (проверка во время построения) «Строй, перестраивая» (проверка во время построения)

Общая схема итеративных методов с измененным порядком добавления точек 1. Упорядочить точки (построить перечень точек событий) 2. Цикл сканирования по всем точкам-событиям 3. Для каждой точки p i построить треугольники к предыдущему треугольнику. 4. Если условие Делоне для соседей нарушилось, то перестроить соседние треугольники. Методы сканирования Итеративные алгоритмы с измененным порядком добавления точек (1.4)

Методы сканирования Способы упорядочивания точек событий Прямолинейное Прямолинейное Полярное (круговое, веерообразное) Полярное (круговое, веерообразное) Полосовое Полосовое Квадратное Квадратное По кривой Гильберта По кривой Гильберта По Z-коду По Z-коду Цели: Сразу строить максимум хороших треугольников Сразу строить максимум хороших треугольников Минимизировать число перестроений Минимизировать число перестроений

Сводные характеристики методов триангуляции Делоне Метод триангуляции Время в среднем Время в худшем Время сек / т Простотареализац. Методы пошагового ввода Методы пошагового ввода Итеративные алгоритмы () Итеративные алгоритмы ()O(n)- O(n 3/2) O(n 2) 1,5-9,2 2-5 Методы пошаговой выборки Методы пошаговой выборки Метод прямого построения (3) Метод прямого построения (3) O(n)- O(n 2) O(n 2) -2 Методы декомпозиции Методы декомпозиции Методы слияния (2) Методы слияния (2) O(n)- O(nlogn) O(nlogn)- O(n 2) 2,5-4,52-3 Методы сканирования Методы сканирования Итеративные с измененным порядком добавления точек (1.4) Итеративные с измененным порядком добавления точек (1.4)O(n) O(n 2) 1,9-5,34-5 Двухпроходные методы (4) Двухпроходные методы (4) O(n)- O(n 2) O(nlogn)- O(n 2) 2,2-15,41-5 Скворцов рекомендует: итеративный алгоритм с динамическим кэшированием

А сегодня о чем? О триангуляции Делоне! Определение Определение Области применения Области применения Свойства триангуляции Делоне Свойства триангуляции Делоне Методы построения триангуляции Делоне Методы построения триангуляции Делоне Методы пошагового ввода Методы пошагового ввода Методы пошаговой выборки Методы пошаговой выборки Методы декомпозиции Методы декомпозиции Методы сканирования Методы сканирования Двухпроходные методы Двухпроходные методы

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

Дано множество из N точек.

1. На первых трех исходных точках строим один треугольник.

2. В цикле по n для всех остальных точек выполняем шаги 3-5.

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

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

5. Проводятся локальные проверки вновь полученных треугольников на соответствие условию Делоне и выполняются необходимые перестроения.

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

Ниже приводится подробное описание нескольких алгоритмов.

Жадный алгоритм

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

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

1. Во множество исходных точек помещаются концы всех структурных отрезков.

2. Генерируются отрезки, соединяющие все пары точек, отрезки сортируются по длине.

3. В триангуляцию вставляются все отрезки структурных линий.

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

Шаг 4 повторяется, пока не кончатся отрезки.

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

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

Алгоритм "Удаляй и строй"

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

Рис. 4. Алгоритм "Удаляй и строй"

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

Алгоритм "Строй, разбивая"

Алгоритм вставки структурных отрезков "Строй, разбивая" является наиболее простым в реализации и устойчивым в работе.

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

Рис. 5. Алгоритм "Строй, разбивая"

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

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

Алгоритм с индексированием центров треугольников k-D - деревом

В алгоритме триангуляции с индексированием центров треугольников k-D-деревом в k-D-дерево (при k = 2) помещаются только центры треугольников. При удалении старых треугольников необходимо удалять их центры из k-D-дерева, а при построении новых - заносить.

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

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

Пространственная триангуляция Делоне

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

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

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

Сеть таких треугольников называется триангуляцией Делоне, если она удовлетворяет некоторым условиям:

Внутрь окружности, описанной вокруг любого треугольника, не попадает ни одна из исходных точек (рис. 5.3);

Триангуляция является выпуклой и удовлетворяет сформулиро­ванному выше условию Делоне;

Сумма минимальных углов всех треугольников максимальна из всех возможных триангуляций;

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

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

(5.2)

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

В приложении к двумерному пространству она формулируется следующим образом: система взаимосвязанных неперекрывающихся треугольников имеет наименьший периметр, если ни одна из вершин не попадает внутрь ни одной из окружностей, описанных вокруг образованных треугольников (рис. 5.4).

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

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

Многие алгоритмы построения триангуляции Делоне используют следующую теорему .

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

Рис. 5.5.. Перестроение треугольников, не удовлетворяющих условию Делоне

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

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

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

– проверка через уравнение описанной окружности;

– проверка с заранее вычисленной описанной окружностью;

– проверка суммы противолежащих углов;

– модифицированная проверка суммы противолежащих углов.

В многих системах выполняется проверка с заранее вычисленной описанной окружностью. Основная идея алгоритма проверки через за­ранее вычисленные окружности заключается в предварительном вычислении для каждого построенного треугольника центра и радиуса описанной вокруг него окружности, после чего проверка условия Делоне будет сводиться к вычислению расстояния до центра этой окружности и сравнению результата с ради­усом. Центр и радиус r окружности, описанной вокруг можно найти как , , , r 2 = (b 2 + с 2 - 4аd)/4а 2 , где значения а, b, с, d определены по формулам (5.3)

(5.3)

Другая запись уравнения этой окружности имеет вид:

(5.5.)

(5.6)

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

(x 0 – x C) 2 + (y 0 – y C) 2 ≥ r 2 . (5.7)

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

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

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

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

– все множество точек делится на треугольники, т.е. создаются комбинации из трех точек;

– для каждой комбинации находится описанная окружность и координаты ее центра;

– если внутри окружности текущей комбинации не находится ни одной точки из оставшихся то эта комбинация есть треугольник – часть триангуляции Делоне.

К достоинствам этого алгоритма можно отнести:

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

– непосредственное построение триангуляции Делоне, без каких – либо предварительных построений;

– простота всех вычислений и преобразований;

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

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

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

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

Множество исходных точек делится вертикальными линиями на две или более частей, после чего каждая из них разделяются горизонтальными и вертикаль­ными линиями на примерно равные части. В результате вся область исходных точек оказывается разделенной на примитивы по три – четыре точки (рис. 2.4), по которым строятся один – два треугольника.

Слияние этих треугольников в единую сеть выполняется путем построения двух базовых линий (P 0 P 1 и P 2 P 3 , рис. 5,7.а), проведении окружностей переменного радиуса с центром на серединном перпендикуляре к базовой линии (рис. 5.7, б), поиску попадающего на окружность узла (точка A , рис. 5.7. в) и построению нового треугольника (P 0 P 1 A). При этом может возникнуть необходимость удаления уже существующего треугольника (например, P 0 AB) .

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

Двухпроходные алгоритмы, предусматривают вначале построение некоторой триангуляции, игнорируя условия Делоне, а затем – ее перестроение в соответствии с этими условиями. Пример при­менения алгоритма приведен на рис. 5.8.

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

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

Фрагмент триангуляции Делоне с включенными в нее дополнительными элементами приведен на рис. 5.9, где справа показаны узлы, ребра, грани и структурные линии, а слева – структурные линии местности (береговые линии, бровки оврага и др.) и точки с известными отметками.

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

Модель TIN легко редактируется путем перемещения узлов, вставки новых, удаления имеющихся, изменения положения одного или нескольких ребер, внедрения новых структурных линий и др. Такие изменения всегда затрагивают небольшую группу смежных треугольников, не требуют перестроения всей сети и осуществляются в режиме on-line, по указанию курсором на соответствующий элемент .

О точности:

Располагая пикеты на характерных элементах рельефа (например, водоразделах и тальвегах), мы игнорируем более мелкие элементы в промежутках. При построении горизонталей1 по таким ребрам треугольников возникает ошибка, которая зависит от величины неровности рельефа и угла наклона местности. Например, средняя погрешность съемки рельефа, не должна превышать 1/3 сечения рельефа при углах наклона поверхности от 2 до 10 градусов. Можно рассчитать, что при сечении рельефа 0,5 м предельная величина пропущенной неровности (то есть отклонения поверхности земли от прямой, проходящей через соседние пикеты) не должна превышать (0,5/3)*cos10°=0,16 м.

Для точности определения объема перемещаемого грунта важна также площадь, занимаемая не учитываемой деталью рельефа. Допустим, в квадрате 20х20 м между двумя парами пикетов имеется цилиндрическая выпуклость с максимальной высотой 0,15 м. Нетрудно подсчитать, что ее неучет при представлении данной поверхности только двумя треугольниками приведет к ошибке приблизительно в 40 м3. Не так уж много, но для участка в 1 га, расположенного на холме или верхней (как правило, выпуклой) части склона, получится уже 40*25=1000 м3 лишнего грунта. Если же брать пикеты в два раза чаще (то есть через 10 м), ошибка уменьшится вчетверо и составит 250 м3 на гектар. Этот фактор можно учесть заранее, поскольку положительные формы равнинного рельефа обычно имеют выпуклую форму, а отрицательные – вогнутую. Если на подлежащий съемке участок имеются приближенные данные о рельефе, то радиус кривизны поверхности и необходимую густоту пикетов легко рассчитать по величинам заложения горизонталей или отдельным высотным отметкам.