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

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

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

На входе

Рисунок 1

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

Поиски

Алгоритм

Рисунок 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: 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 операций сложения/вычитания.

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

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

ТЕПЛОВ А.А. , бакалавр, МГТУ имени Н.Э. Баумана, кафедра «Программное обеспечение ЭВМ и информационные технологии», Москва, [email protected]

МАЙКОВ К.А. , д.т.н., профессор, МГТУ имени Н.Э. Баумана, кафедра «Программное обеспечение ЭВМ и информационные технологии», Москва, [email protected]

Модифицированный алгоритм
триангуляции Делоне

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

Введение

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

Постановка решаемых задач

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

Проблема «степени правильности» треугольников решается триангуляцией, удовлетворяющей условию Делоне .

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

Итеративные алгоритмы построения триангуляции Делоне

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

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

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

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

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

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

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

Выбор прототипа для модификации триангуляции Делоне

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

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

Однако алгоритмы данного типа нуждаются в модификации в целях повышения быстродействия применимо к задачам реального времени. Двухпроходной веерный алгоритм избыточен в определении центра масс точек. Определяя координату точки центр масс по OX или OY, при большом количестве точек нецелесообразно вычислять значение среднего арифметического, и при больших значениях координат точек может произойти переполнение данных, что повлечет за собой ошибку или сбой программы. Поэтому целесообразно все значения точек триангуляции разделить на интервалы по оси X на Δх 1 , Δх 2 , Δх 3 ... Δх n и по оси Y на Δy 1 , Δy 2 , Δy 3 ... Δy n . Также необходимо определить количество точек, принадлежащих соответствующим интервалам по осям X и Y. Результирующие формулы получения центра координат масс точек имеют следующий вид:

• х c – x-координата точки центра масс;
• Δх i – i-й интервал на оси X;
• X max – максимальное значение по оси X среди всех точек триангуляции;
• X min – минимальное значение по оси X среди всех точек триангуляции;

• y c – y-координата точки центра масс;
• n i – количество точек на i-м интервале;
• Δy i – i-й интервал на оси Y;
• Y max – максимальное значение по оси Y среди всех точек триангуляции;
• Y min – минимальное значение по оси Y среди всех точек триангуляции.

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

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

Анализ модифицированного веерного алгоритма триангуляции Делоне

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

• T 1 ,T 2 – значения времени вычислений оптимального числа интервалов по осям X и Y соответственно;
• T 3 ,T 4 – значения времени вычислений X min и X max соответственно;
• T 5 ,T 6 – значения времени вычислений Y min и Y max соответственно;
• T 7 ,T 8 – значения времени вычислений величин интервалов по осям X и Y соответственно;
• T 9 – значение времени вычисления величин полярного угла каждой точки массива относительно точки A(X c ,Y c);
• T 10 – значение времени сортировки слиянием всех точек по полярному углу относительно точки A(X c ,Y c);
• T 11 – значение времени построения ребра от каждой точки массива к точке A(X c ,Y c);
• T 12 – значение времени достроения триангуляции до выпуклой;
• T 13 – значение времени перестроения триангуляции, удовлетворяющей условию Делоне;
• n – массив значений координат точек.

Рассмотрим каждую временную зависимость отдельно.

При определении оптимального числа интервалов по оси X и Y, воспользуемся правилом Стерджеса , согласно которому количество интервалов n определяется как:

• N – общее число наблюдений величины;
• [x] – целая часть числа x.

Очевидно, что временные зависимости T 1 и T 2 имеют константные представления c 1 и c 2 .

На этапах определения значений X min , X max , Y min , Y max псевдокод будет выглядеть следующим образом:

Xmin ← M

for i ← 1 to lenght(M) – 1

If Xmin › M[i]

Xmin ← M[i]

Xmax ← M

for i ← 1 to lenght(M) – 1

If Xmax < M[i]

Xmax ← M[i]

Ymin ← M

for i ← 1 to lenght(M) – 1

If Ymin › M[i]

Ymin ← M[i]

Ymax ← M

for i ← 1 to lenght(M) – 1

If Ymax < M[i]

Ymax ← M[i]

Из вышеуказанного псевдокода отчетливо видно, что время нахождения максимального или минимального значения величин x или y имеет линейную зависимость O(N), следовательно, T 3 (n), T 4 (n),T 5 (n),T 6 (n), имеют временную характеристику O(N) соответственно.

Схема определения значений интервалов по оси X представлена на рис. 2.

Из выше представленной схемы также видна линейная временная зависимость O(N), т.к. в определении величин участвует весь набор координат значений массива точек. Схема определения величин интервалов по оси Y имеет аналогичную структуру и временные характеристики, следовательно, временная зависимость для T 7 (n) и T 8 (n) имеет вид O(N).

Схема определения значений полярного угла для исходного массива точек представлена на рис. 3.

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

for points to points

# Если точка лежит на оси координат между I и IV четвертями

If point.x ≥ Xc and point.y = Yc

Point.angle ← 0

# Если точка лежит строго в I четверти

Else if point.x > Xc and point.y > Yc

Foundation ← |point.x – Xc|

Point.angle ← arctg(perpendicular/foundation)

# Если точка лежит на оси координат между I и II четвертями

Else if point.x = Xc and point.y > Yc

Point.angle ← p/2

# Если точка лежит строго в II четверти

Else if point.x < Xc and point.y > Yc

Foundation ← |point.y – Yc|

Point.angle ← p/2 + arctg(perpendicular/foundation)

# Если точка лежит на оси координат между II и III четвертями

If point.x < Xc and point.y = Yc

Point.angle ← p

# Если точка лежит строго в III четверти

If point.x < Xc and point.y > Yc

Foundation ← |point.x – Xc|

Perpendicular ← |point.y – Yc|

Point.angle ← p + arctg(perpendicular/foundation)

# Если точка лежит на оси координат между III и IV четвертями

If point.x = Xc and point.y < Yc

Point.angle ← 3p/2

# Если точка лежит строго в IV четверти

If point.x > Xc and point.y < Yc

Foundation ← |point.y – Yc|

Perpendicular ← |point.x – Xc|

Point.angle ← 3p/2 + arctg(perpendicular/foundation)

Очевидно, что временная характеристика определения значений полярного угла для исходного массива координат точек имеет вид O(N), следовательно, T 9 (n) = O(N).

Как показано в , сортировка слиянием имеет временную зависимость вида O(N), следовательно, T 10 (n) = O(NlnN).

Схема построения ребра, соединяющего точки исходного массива, представлена на рис. 4.

Псевдокод вышеуказанной схемы будет иметь вид:

for i ← 0 to length(Points) – 1

Draw(Xc,Yc,Points[i].x, Points[i].y)

Временная характеристика также линейна, следовательно, T 11 (n) = O(N).

Достроение получившейся триангуляции до выпуклой осуществляется согласно алгоритму Грэхема . В качестве входных данных процедуры выступает множество точек Q, где |Q|≥3. В ней вызывается функция Top(S), которая возвращает точку, находящуюся на вершине стека S, не изменяя при этом его содержимое. Кроме того, используется также функция NextToTop(S), которая возвращает точку, расположенную в стеке S, на одну позицию ниже от верхней точки; стек S при этом не изменяется.

Graham(Q)

Пусть p 0 – точка из множества Q с минимальной координатой.

Пусть ‹p 1 , p 2 ,...,p N › – точки множества Q, отсортированные

В порядке возрастания полярного угла.

Push(p 0 ,S)

Push(p 1 ,S)

for i=2 to N do

While угол, образованный точками NextToTop(S), Top(S) и pi,

Образуют не левый поворот

# при движении по ломаной, образованной этими

# точками, движение осуществляется прямо или вправо

Do Pop(S)

Push(pi,S)

return S

Время работы процедуры Graham равно O(NlnN), где N=length(Q). Как несложно показать, что циклу while потребуется время O(N), а сортировка полярных углов займет O(NlnN) времени, откуда и следует общая асимптотика процедуры Graham, следовательно, T 12 (n) = O(NlnN).

Временная характеристика перестроения триангуляции, удовлетворяющей условию Делоне, как показано в , имеет линейную зависимость O(N), таким образом, T 13 (n) = O(N).

Если подставить все найденные временные характеристики в выражение (3), то результирующая временная зависимость будет иметь вид:

T(n) = c 1 +c 2 +O(N)+O(N)+O(N)+O(N)+O(N)+O(N)+O(N)+ +O(NlnN)+O(N)+O(NlnN)+O(N)

T(n) = O(NlnN)

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

Выводы

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

1. Кнут Д.Э. Искусство программирования. Том 1. Основные алгоритмы. – М.: Вильямс, 2008. – 680 с.
2. Кнут Д.Э. Искусство программирования. Том 3. Сортировка и поиск. – М.: Вильямс, 2008. – 800 с.
3. Мандельброт Б. Фрактальная геометрия природы. – М.: Институт компьютерных исследований, 2002. – 656 с.
4. Скворцов А. В. Триангуляция Делоне и ее применение. – Томск: Изд-во Томского университета, 2002. – 128 с.
5. Скворцов А.В. Построение триангуляции Делоне за линейное время. – Томск: Изд-во Томского университета, 1999. – С.120-126.
6. Скворцов А.В., Мирза Н.С. Алгоритмы построения и анализа триангуляции. – Томск: Изд-во Томского университета, 2006. – 168 с.
7. Томас Х. Кормен, Чарльз И. Лейзерон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, 3-е изд.: Пер. с англ. – М.: Вильямс, 2013. – 1328 с.
8. Шайдуров В.В. Многосеточные методы конечных элементов. – М.: Наука, 1989. – 288 с.
9. Sturges H. (1926). The choice of a class-interval. J. Amer. Statist. Assoc., 21, 65-66.

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

The modified Delaunay’s triangulation algorithm

Teplov A.A. , Bachelor, MSTU Bauman, Department of "Software and Information Technologies", Moscow, [email protected]

Maikov K.A. , Doctor of Technical Sciences, Professor, MSTU Bauman, Department of "Software and Information Technologies", Moscow, [email protected]

Abstract: The results of the comparative analysis of the virtually popular methods of the Delaunay’s triangulation with high performance and low resource consumption are described in this article. The choice of the method for further modernization with the aim of building of dynamic 3-D objects in real time with a certain degree of detail is justified. One of the main stages of a fibered the two-pass algorithm of the Delaunay’s triangulation is modified. There is the proposal of the algorithm for the interval partitioning of the cell array of the triangulation in accordance with the density of distribution, allowing to avoid the errors in the hardware implementation.

Keywords: virtual reality, triangulation on a given cell array, Delaunay’s triangulation, building of dynamic 3-D objects.

Вконтакте

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

Рис. 1

Для данного набора точек S мы можем видеть, что все точки из набора S могут быть подразделены на граничные точки - те точки, которые лежат на границе выпуклой оболочки CH(S), и внутренние точки - лежащие внутри выпуклой оболочки CH(S). Также можно классифицировать и ребра, полученные в результате триангуляции S, как ребра оболочки и внутренние ребра . К ребрам оболочки относятся ребра, расположенные вдоль границы выпуклой оболочки CH(S), а к внутренним ребрам - все остальные ребра, образующие сеть треугольников внутри выпуклой оболочки. Отметим, что каждое ребро оболочки соединяет две соседние граничные точки, тогда как внутренние ребра могут соединять две точки любого типа. В частности, если внутреннее ребро соединяет две граничные точки, то оно является хордой выпуклой оболочки CH(S). Заметим также, что каждое ребро триангуляции является границей двух областей: каждое внутреннее ребро находится между двумя треугольниками, а каждое ребро оболочки - между треугольником и бесконечной плоскостью.

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

Теорема о триангуляции набора точек. Предположим, что набор точек S содержит n>3 точек и не все из них коллинеарны. Кроме того, i точек из них являются внутренними (т. е. лежащими внутри выпуклой оболочки CH(S). Тогда при любом способе триангуляции набора S будет получено точно n + i - 2 треугольников.

Для доказательства теоремы рассмотрим сначала триангуляцию n-i граничных точек. Поскольку все они являются вершинами выпуклого полигона, то при такой триангуляции будет получено (n - i) - 2 треугольников. (В этом нетрудно удостовериться и, более того, можно показать, что любая триангуляция произвольного m-стороннего полигона - выпуклого или невыпуклого - содержит m - 2 треугольника). Теперь проверим, что будет происходить с триангуляцией при добавлении оставшихся i внутренних точек, каждый раз по одной. Мы утверждаем, что добавление каждой такой точки приводит к увеличению числа треугольников на два. При добавлении внутренней точки могут возникнуть две ситуации, показанные на рис. 2. Во-первых, точка может оказаться внутри некоторого треугольника и тогда такой треугольник заменяется тремя новыми треугольниками. Во-вторых, если точка совпадает с одним из ребер триангуляции, то каждый из двух треугольников, примыкающих к этому ребру, заменяется двумя новыми треугольниками. Из этого следует, что после добавления всех г точек, общее число треугольников составит (n - i - 2) + (2i), или просто n + i - 2.

Рис. 2

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

Рис. 3

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

Триангуляция набора точек S будет триангуляцией Делоне, если описанная окружность для каждого треугольника будет свободна от точек. На схеме триангуляции рис. 1а показаны две окружности, которые явно не содержат внутри себя других точек (можно провести окружности и для других треугольников, чтобы убедиться, что они также свободны от точек набора). Это правило не соблюдается на схеме рис. 16 - внутрь проведеной окружности попала одна точка другого треугольника, следовательно, эта гриангуляция не относится к типу Делоне.

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

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

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

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

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

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

На рис. 4 показана работа алгоритма, где действие происходит сверху вниз и слава направо. Граница на каждом этапе выделена толстой линией.

Алгоритм реализован в программе delaunayTriangulate. Программе задается массив s из n точек и она возвращает список треугольников, представляющих триангуляцию Делоне. Реализация использует класс кольцевого списка и классы из раздела структуры геометрических данных . В качестве класса Dictionary можно использовать любой словарь, поддерживающий требуемые операции. Например, можно переопределить #define Dictionary RandomizedSearchTree .

List * (Point s, int n) { Point p; List *triangles = new List; Dictionary frontier(edgeCmp); Edge *e = hullEdge(s, n); frontier.insert(e); while (!frontier.isEmpty()) { e = frontier.removeMin(); if (mate(*e, s, n, p)) { updateFrontier(frontier, p, e->org); updateFrontier(frontier, e->dest, p); triangles->insert(triangle(e->org, e->dest, p)); } delete e; } return triangles; }

Рис. 4

Треугольники, образующие триангуляцию, записываются в список triangles. Граница представлена словарем frontier живых ребер. Каждое ребро направлено, так что неизвестная область для него (подлежащая определению) лежит справа от ребра. Функция сравнения edgeCmp используется для просмотра словаря. В ней сравниваются начальные точки двух ребер, если они оказываются равными, то потом сравниваются их концевые точки:

Int edgeCmp (Edge *a, Edge *b) { if (a->org < b->org) return 1; if (a->org > b->org) return 1; if (a->dest < b->dest) return -1; if (a->dest > b->dest) return 1; return 0; }

Как же изменяется граница от одного шага к другому и как функция updateFrontier изменяет словарь ребер границы для отражения этих изменений? При подсоединении к границе нового треугольника t изменяются состояния трех ребер треугольника. Ребро треугольника t, примыкающее к границе, из живого становится мертвым. Функция updateFrontier может игнорировать это ребро, поскольку оно уже должно быть удалено из словаря при обращении к функции removeMin. Каждое из двух оставшихся ребер треугольника t изменяют свое состояние из спящего на живое, если они уже ранее не были записаны в словарь, или из живого в мертвое, если ребро уже находится в словаре. На рис. 5 показаны оба случая. В соответствии с рисунком мы обрабатываем живое ребро af и, после обнаружения, что точка b является сопряженной ему, добавляем треугольник afb к текущей триангуляции. Затем ищем ребро fb в словаре и, поскольку его там еще нет и оно обнаружено впервые, его состояние изменяется от спящего к живому. Для редактирования словаря мы повернем ребро fb так, чтобы примыкающая к нему неизвестная область лежала справа от него и запишем это ребро в словарь. Затем отыщем в словаре ребро ba - поскольку оно есть в нем, то оно уже живое (известная примыкающая к нему область - треугольник abc). Так как неизвестная для него область, треугольник afb, только что была обнаружена, это ребро удаляется из словаря.

Функция updateFrontier редактирует словарь frontier, в котором изменяется состояние ребра из точки а в точку b:

Рис. 5

Void updateFrontier (Dictionary &frontier, Point &a, Point &b) { Edge *e = new Edge (a, b); if (frontier.find (e)) frontier.remove(e); else { e->flip(); frontier.insert(e); } }

Функция hullEdge обнаруживает ребро оболочки среди п точек массива s. В этой функции фактически применяется этап инициализации и первой итерации метода заворачивания подарка:

Edge *hullEdge (Point s, int n) { int m = 0; for (int i = 1; i < n; i++) if (s[i] < s[m]) m = i; swap(s, s[m]); for (m = 1, i = 2; i < n; i++) { int с = s[i].classify (s, s[m]); if ((c == LEFT) || (C == BETWEEN)) m = i; } return new Edge(s, s[m]); }

Функция triangle просто формирует и возвращает полигон для трех точек, передаваемых ей в качестве параметров:

Polygon *triangle (Point &а, Point &b, Point &c) { Polygon *t = new Polygon; t->insert (a); t->insert (b); t->insert (c); return t; }

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

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

Впервые задача построения сети неперекрывающихся треуголь­ников была поставлена в 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.

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

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

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

Модель 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 на гектар. Этот фактор можно учесть заранее, поскольку положительные формы равнинного рельефа обычно имеют выпуклую форму, а отрицательные – вогнутую. Если на подлежащий съемке участок имеются приближенные данные о рельефе, то радиус кривизны поверхности и необходимую густоту пикетов легко рассчитать по величинам заложения горизонталей или отдельным высотным отметкам.

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

Триангуляция Триангуляция – планарный граф все внутренние области которого являются треугольниками. Триангуляция – планарный граф все внутренние области которого являются треугольниками. Термин «Триангуляция» - это Термин «Триангуляция» - это граф; граф; процесс построения графа. процесс построения графа. Задача триангуляции набора точек 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 Скворцов рекомендует: итеративный алгоритм с динамическим кэшированием

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