Главная › Интеллектуальное › Пространственная триангуляция делоне. Оптимизация алгоритма проверки условия Делоне через уравнение описанной окружности и его применение

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

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

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

Размещено на 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20 августа 2012 в 22:41

Оптимизация алгоритма проверки условия Делоне через уравнение описанной окружности и его применение

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

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

На входе

После обнаружения и обхода границ на выходе я получил множество внешних контуров. Каждые соприкасающиеся контура имеют разные цвета. Внутри каждого такого контура содержится также известное кол-во внутренних контуров.
Таким образом, с точки зрения «заметания плоскости», если рассматривать внешние контура отдельно, имеем множество точек, каждая из которых имеет по одному соседу справа и слева. Т.е. все точки замкнуты в цепи, нет ни одной одиночной «висячей» точки, а так же в каждой из цепей содержится не менее 3-ех точек (Рисунок 1).

Рисунок 1

Что надо сделать

Нужно заметать фигуру треугольниками.

Поиски

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

Алгоритм

1) Допустим, для начала, что в рассматриваемой фигуре всего одна последовательность. Тогда все сводится к последовательному забиранию треугольников. Берем любую точку и пытаемся построить треугольник с соседними точками. Если треугольник построить не получилось (линия связывающая эти две точки, пересекается с уже построенными или линия проходит в зоне отчуждения (Рисунок 2), двигаемся к соседней точке, допустим вправо. Когда очередной треугольник найден, заносим его в список (Рисунок 3), а точку из которой он строился удаляем (Рисунок 4).

Рисунок 2

Рисунок 3

Рисунок 4

Еще одно но: при сохранении очередного треугольника необходимо записывать вершины в обходе по часовой стрелке (в правой системе координат). Это пригодится в дальнейшем для уменьшения вычислительных ресурсов.

2) Повторяем шаг 1 пока не заметаем всю плоскость.

3) Если последовательностей несколько, т.е. одна, а внутри её еще одна или более внутренних контуров (Рисунок 1). Тут необходимо рассмотреть каждую последовательность отдельно. Возьмем очередной внутренний контур. Из одного внешнего и одного внутреннего сделаем два одиночных контура. Для этого нужно найти два «порта» из одного контура в другой. Условие для «портов»: они не должны пересекаться между собой(не должны соприкасаться даже концами), не должны пересекаться с линиями контуров (Рисунок 5).

Рисунок 5

Рисунок 6
4) Далее следует ввести поочередно все внутренние последовательности в уже образованные, отделенные друг от друга (пункт 3) последовательности. Сливать нужно с той, которая содержит новую. По определению ни одна внутренняя последовательность не касается и не пересекается с другими(как одной внешней, так и всеми возможными внутренними), так что все пройдет гладко.
Найдя порты (Рисунок 6) легко построить новые последовательности и обойти их пунктами 1 и 2 текущего алгоритма (Рисунок 7).

Рисунок 7

5) После 4-его этапа имеем список треугольников(Рисунок 8). Как бы с задачей уже справились, но осталось сделать картинку красивой: проверить выполнение условия Делоне (Рисунок 9).

Рисунок 8

Рисунок 9

6) Забегая вперед расскажу про шестой пункт. Он заключается в последовательном прогоне по списку полученных треугольников пунктом №5. Сначала метим все треугольники «грязными». В каждом цикле проверяем для каждого треугольника условие Делоне. Если условие не выполняется, то делаем перестроение и помечаем соседей и текущий треугольник «грязными». Если условие выполняется, то метим его чистым. В моей реализации алгоритма, каждый треугольник имеет ссылку на соседей. В этом случае 6-ой пункт работает наиболее быстро.

Подробнее о пятом этапе

Сейчас, на сколько я знаю, существуют два возможных способа определить удовлетворяют треугольники условию Делоне или нет: 1) Проверить сумму противоположных углов. Она должны быть меньше 180. 2) Вычислить центр описанной окружности и посчитать расстояние до 4-ой точки. Всем известно, условие Делоне выполняется, если точка находится за пределами описанной окружности.

Мощность вычислений №1: 10 операций умножения/деления и 13 операций сложения/вычитания.
Мощность вычислений №2: 29 операций умножения/деления и 24 операций сложения/вычитания.

С точки зрения вычислительной мощности, которая высчитывается к примеру в книге , выгоднее вариант №1. Его и реализовал, если бы не… (Рисунок 10). Как оказалось после постановки данного метода на «конвейер», получилась неопределенность. Это вариант, когда сам угол А больше 180 градусов. Он рассматривается в книге как один из отдельных частных методов. А с этим пропадает вся его элегантность, прозрачность и производительность. А так же в последствии оказалось, что метод №2 можно очень существенно оптимизировать.

Рисунок 10

Оптимизация алгоритма проверки условия Делоне через уравнение описанной окружности

Далее чистая математика.

Итак имеем:
Проверка условия для точки M(X, Y) уравнением окружности, проходящей через точки A(x1, y1), B(x2, y2), C(x3, y3), можно записать в виде:

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ sign a ≥ 0

Подробности можно взять в великолепной книге . (Нет, не я ее автор)
Итак, sign a - это знак направления обхода, с самого начала я строил треугольники по часовой стрелке, так что его можно опустить (он равен единице).

A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);

D >= 0

Рисунок 11

Просто не правда ли?

Согласно книге, опять же,

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)*(y1*x2 - x1*y2) <= 0

Имеем: 15 операций умножения/деления и 14 операций сложения/вычитания.

Спасибо за внимание. Жду критики.

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

1. Скворцов А.В. Триангуляция Делоне и её применение. – Томск: Изд-во Том. ун-та, 2002. – 128 с. ISBN 5-7511-1501-5

(Development and Implementation of Algorithms for Constrained Volume Triangulations: Iterative Algorithms
Preprint, Inst. Appl. Math., the Russian Academy of Science)

Галанин М.П., Щеглов И.А.
(M.P.Galanin, I.A.Sheglov)

ИПМ им. М.В.Келдыша РАН

Москва, 2006
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект № 06-01-00421)

Аннотация

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

Abstract

Three main families of iterative algorithms for free and constrained simplicial volume triangulation are described: boundary correction (including "octree" algorithm), Delaunay-based methods and advancing front approach. For each method type an example algorithm is given.

1. Введение 3

2. Методы граничной коррекции4

2.1 Построение первичной сетки4

2.2 Коррекция первичной сетки6

3. Методы на основе критерия Делоне9

3.1 Построение триангуляции Делоне на заданном наборе точек 12

3.2. Триангуляция Делоне с ограничениями17

3.3 Особенности технической реализации алгоритмов на основе
критерия Делоне 22

4. Методы исчерпывания23

4.1 Пример алгоритма исчерпывания26

Список литературы3 0

1. Введение

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

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

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

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

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

Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (проект № 06-01-00421).

Рис. 11. Триангуляция области, представляющей собой объединение додекаэдра и икосаэдра (триангуляция Делоне с ограничениями)

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

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

4) объем тетраэдра не больше максимально допустимого ().

Из всех тетраэдров () выбирается тетраэдр наилучшего качества и производится переход к п. 5; если же тетраэдров, удовлетворяющих указанным условиям, не оказалось, то осуществляется переход к п. 4.

4. Находится такая точка внутри еще неисчерпанной области, что:

1) тетраэдр () удовлетворяет всем условиям п. 3;

2) в шаре нет ни одной удаленной точки F (это предотвращает размещение узла p слишком близко от граней и вершин существующих тетраэдров).

Вариант алгоритма поиска узла p рассмотрен ниже.

5. Удаляются все вершины F , попавшие внутрь (и на границы) сформированного тетраэдра. Затем фронт обновляется по следующей схеме: рассматривается каждая грань сформированного тетраэдра и

1) если грань является гранью фронта, то она удаляется из фронта;

2) если грань НЕ является гранью фронта, она добавляется во фронт.

6. Если еще остались неудаленные точки F или (что эквивалентно) фронт не пуст (то есть область еще не исчерпана полностью), осуществляется переход к п. 1, иначе процесс окончен.

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

Вернемся к вопросу нахождения координат нового узла для построения тетраэдра (п. 4 описанного алгоритма). Пусть заданы три узла - .

1. На первом шаге находятся - центр масс треугольника (как среднее арифметическое координат его узлов) и единичная нормаль к плоскости грани (через нормированное векторное произведение).

2. Далее определяется первое приближение для расстояния от до искомой точки p (H ), исходя из максимального объема тетраэдра: . Заметим, что площадь грани S фактически найдена на предыдущем шаге (результат векторного произведения двух ребер равен удвоенной площади грани), а максимальный объем обусловлен значением контрольной функции.

3. Проверяется точка . Если тетраэдр () удовлетворяет всем требованиям, происходит переход к п. 6, иначе - к п. 4.

4. Проверяется точка . Если тетраэдр () удовлетворяет всем требованиям, происходит переход к п. 6, иначе - к п. 5.

5. Полагают и переходят к п. 3.

6. Искомый узел найден.

Заметим, что в 99% случаев искомая точка находится на 1 или 2 итерации данного алгоритма.

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

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

Список литературы

1. Шайдуров В.В. Многосеточные методы конечных элементов. - М., Наука, 1989. - 288с.

2. Скворцов А.В. Обзор алгоритмов построения триангуляции Делоне // , 2002, №3, c . 14-39.

3. Скворцов А.В. Алгоритмы построения триангуляции с ограничениями // Вычислительные методы и программирование , 2002, №3, c . 82-92.

4. I.Babushka, W.C. Rheinboldt. A-posteriori Error Estimates for Finite Element Method // Int. J. Numer. Meth. Eng. , Vol. 12, p.p. 1597-1615, 1978.

5. T.J. Baker. Automatic Mesh Generation for Complex Three-Dimensional Regions Using a Constrained Delaunay Triangulation // Engineering With Computers , Springer-Verlag, № 5, p.p. 161-175, 1989.

6. M. Bern, D. Eppstein. Mesh Generation and Optimal Triangulation // Computing in Euclidean Geometry , World Scientific Publishing Co., p.p. 23-90, 1995.

7. D.K. Blandford, G. Blelloch, D. Cardoze, C. Kadow. Compact Representations of Simplicial Meshes In Two and Three Dimensions // Proceedings of 12th International Meshing Roundtable , Sandia National Laboratories, p.p.135-146, Sept. 2003.

8. H. Borouchaki, S.H. Lo. Fast Delaunay Triangulation In Three Dimensions // Computer Methods In Applied Mechanics And Engineering , Elsevier, Vol. 128, p.p. 153-167, 1995.

9. E.K. Buratynski. A Three-Dimensional Unstructured Mesh Generator for Arbitrary Internal Boundaries // Numerical Grid Generation in Computational Fluid Mechanics , Pineridge Press, p.p. 621-631, 1988.

10. P.R. Cavalcanti, U.T. Mello. Three-Dimensional Constrained Delaunay Triangulation: A Minimalist Approach // Proceedings of the 8th International Meshing Roundtable , p.p. 119-129, 1999.

11. Dey, K. Tamal, K. Sugihara, C.L. Bajaj. Delaunay Triangulations In Three Dimensions With Finite Precision Arithmetic // Computer Aided Geometric Design , North-Holland, № 9, p.p. 457-470, 1992.

12. H.N. Djidjev. Force-Directed Methods For Smoothing Unstructured Triangular And Tetrahedral Meshes // Proceedings of 9th International Meshing Roundtable , Sandia National Laboratories, p.p. 395-406, October 2000.

13. L. Durbeck. Evaporation: A Technique For Visualizing Mesh Quality // Proceedings of 8th International Meshing Roundtable , South Lake Tahoe, CA, U.S.A., p.p. 259-265, October 1999.

14. D.A. Field. Laplacian Smoothing And Delaunay Triangulations // , vol. 4, p.p. 709-712, 1988.

15. P.J. Frey, H. Borouchaki, P.-L. George. Delaunay Tetrahedralization Using an Advancing-Front Approach // Proceedings of 5th International Meshing Roundtable , Sandia National Laboratories, p.p. 31-46, October 1996.

16. L.A. Freitag, C. Ollivier-Gooch. A Comparison of Tetrahedral Mesh Improvement Techniques // Proceedings of 5th International Meshing Roundtable , Sandia National Laboratories, p.p. 87-106, October 1996.

17. L.A. Freitag, C. Ollivier-Gooch.Tetrahedral Mesh Improvement Using Swapping and Smoothing // , vol. 40, p.p. 3979-4002, 1995.

18. L.A. Freitag, C. Ollivier-Gooch. The Effect Of Mesh Quality On Solution Efficiency // Proceedings of 6th International Meshing Roundtable , Sandia National Laboratories, p.p.249, October 1997.

19. P.L. George. TET MESHING: Construction, Optimization and Adaptation // Proceedings of 8th International Meshing Roundtable , p.p.133-141, 1999.

20. N.A. Golias, T.D. Tsiboukis. An Approach to Refining Three-Dimensional Tetrahedral Meshes Based on Delaunay Transformations // , John Wiley, № 37, p.p.793-812, 1994.

21. C. Hazlewood. Approximating Constrained Tetrahedralizations // Computer Aided Geometric Design , vol. 10, p.p. 67–87, 1993.

22. B. Joe. Delaunay Triangular Meshes in Convex polygons, SIAM J. Sci. Stat. Comput ., Vol. 7, p.p. 514-539, 1986.

23. B. Joe. Construction Of Three-Dimensional Delaunay Triangulations Using Local Transformations // Computer Aided Geometric Design , Vol. 8, p.p. 123-142, 1991.

24. B. Joe. Construction of Three-Dimensional Improved-Quality Triangulations Using Local Transformations // Siam J. Sci. Comput. , vol. 16, p.p. 1292-1307, 1995.

25. R.W. Lewis, Yao Zheng, D.T. Gethin. Three-Dimensional Unstructured Mesh Generation: Part 3. Volume Meshes // Computer Methods In Applied Mechanics And Engineering , Elsevier, Vol 134, p.p.285-310, 1996.

26. A.Liu, B. Joe. On The Shape Of Tetrahedra From Bisection // Mathematics of Computation , vol. 63, №207, 141–154, 1994.

27. S.H. Lo. Volume Discretization into Tetrahedra-I. Verification and Orientation of Boundary Surfaces // Computers and Structures , Pergamon Press, Vol. 39, № 5, p.p. 493-500, 1991.

28. S.H. Lo. Volume Discretization into Tetrahedra - II. 3D Triangulation by Advancing Front Approach // Computers and Structures , Pergamon, Vol. 39, № 5, p.p. 501-511, 1991.

29. R. Lohner. Generation Of Three-Dimensional Unstructured Grids By The Advancing Front Method //Proceedings of the 26th AIAA Aerospace Sciences Meeting , Reno, Nevada, 1988.

30. S.J. Owen. A Survey of Unstructured Mesh Generation Technology // Proceedings of 7th International Meshing Roundtable , p.p. 239-269, Dearborn, MI, 1998.

31. V.N. Parthasarathy, C.M. Graichen, A.F. Hathaway. A Comparison of Tetrahedron Quality Measures // Finite Elements in Analysis and Design , Elsevier, №. 15, p.p. 255-261, 1993.

32. S. Pirzadeh. Unstructured Viscous Grid Generation by Advancing-Layers Method // AIAA-93-3453-CP, AIAA, p.p. 420-434, 1993.

33. V.T. Rajan. Optimality of Delaunay Triangulation in // Proc. 7th ACM Symp. Comp. Geometry , p.p. 357-363, 1991.

34. A.Rassineux. Generation and Optimization of Tetrahedral Meshes by Advancing Front Technique // International Journal for Numerical Methods in Engineering , Wiley, Vol. 41, p.p. 651-674, 1998.

35. S. Rebay. Efficient Unstructured Mesh Generation by Means of Delaunay Triangulation and Bowyer-Watson Algorithm // Journal Of Computational Physics , vol. 106, p.p. 125-138, 1993.

36. M.-C. Rivara. Selective Refinement/Derefinement Algorithms For Sequences Of Nested Triangulations // International Journal for Numerical Methods in Engineering , №28, p.p. 2889-2906, 1998.

37. M.-C. Rivara, C. Levin. A 3D Refinement Algorithm Suitable For Adaptive And Multigrid Techniques // Communications in Applied Numerical Methods , № 8, p.p. 281-290, 1998.

38. J. Ruppert. A Delaunay refinement algorithm for quality 2-dimensional mesh generation // Journal of Algorithms , №18, p.p. 548-585, 1995.

39. M.S. Shephard, M.K. Georges. Three-Dimensional Mesh Generation by Finite Octree Technique // International Journal for Numerical Methods in Engineering , vol. 32, p.p. 709-749, 1991.

40. M.S. Shephard, F. Guerinoni, J.E. Flaherty, R.A. Ludwig, P.L. Baehmann. Finite octree mesh generation for automated adaptive 3D Flow Analysis // Numerical grid generation in computational Fluid mechanics , Miami, 1988

41. K. Shimada, D.C. Gossard. Bubble Mesh: Automated Triangular Meshing of Non-manifold Geometry by Sphere Packing // Proceedings of 3rd Symposium on Solid Modeling and Applications , p.p. 409-419, 1995.

42. K. Shimada, A. Yamada, T. Itoh. Anisotropic Triangular Meshing of Parametric Surfaces via Close Packing of Ellipsoidal Bubbles // Proceedings of 6th International Meshing Roundtable , p.p. 375-390, 1997.

43. D.F. Watson. Computing the Delaunay Tessellation with Application to Voronoi Polytopes // The Computer Journal , Vol. 24(2), p.p. 167-172, 1981.

44. M.A. Yerry, M.S. Shephard. Three-Dimensional Mesh Generation by Modified Octree Technique // International Journal for Numerical Methods in Engineering , Vol. 20, p.p. 1965-1990, 1984.

45. Галанин М.П., Щеглов И.А. Разработка и реализация алгоритмов трехмерной триангуляции сложных пространственных областей: прямые методы. Препринт ИПМ им. М.В. Келдыша РАН, 2006, в печати. points , т.е. узлы Штейнера - дополнительные узлы, не входившие в изначальный набор

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