что такое метод триангуляции
Алгоритм триангуляции Делоне методом заметающей прямой
Доброго времени суток!
В этой статье я подробно опишу алгоритм, который у меня получился в результате использования идеи «заметающей прямой» для построения триангуляции Делоне на плоскости. В нем есть несколько идей, которые я нигде не встречал, когда читал статьи про триангуляцию.
Возможно, кто-то тоже найдет их необычными. Я постараюсь сделать все в лучших традициях и включить в рассказ следующие вещи: описание используемых структур данных, описание шагов алгоритма, доказательство корректности, временные оценки, а также сравнение с итеративным алгоритмом, использующим kD-дерево.
Определения и постановка задачи
Триангуляция
Говорят, что на множестве точек на плоскости задана триангуляция, если некоторые пары точек соединены ребром, любая конечная грань в получившемся графе образует треугольник, ребра не пересекаются, и граф максимален по количеству ребер.
Триангуляция Делоне
Триангуляцией Делоне называется такая триангуляция, в которой для любого треугольника верно, что внутри описанной около него окружности не находится точек из исходного множества.
Замечание: для заданного множества точек, в котором никакие 4 точки не находятся на одной окружности, существует ровно одна триангуляция Делоне.
Условие Делоне
Пусть на множестве точек задана триангуляция. Будем говорить, что некоторое подмножество точек удовлетворяет условию Делоне, если триангуляция, ограниченная на это подмножество, является триангуляцией Делоне для него.
Критерий для триангуляции Делоне
Выполнение условия Делоне для всех точек, образующих четырехугольник в триангуляции, эквивалентно тому, что данная триангуляция является триангуляцией Делоне.
Замечание: для невыпуклых четырехугольников условие Делоне всегда выполнено, а для выпуклых четырехугольников (вершины которого не лежат на одной окружности) существует ровно 2 возможные триангуляции (одна из которых является триангуляцией Делоне).
Задача заключается в том, чтобы для заданного множества точек построить триангуляцию Делоне.
Описание алгоритма
Видимые точки и видимые ребра
Пусть задана минимальная выпуклая оболочка (далее МВО) конечного множества точек (ребра, соединяющие некоторые из точек так, чтобы они образовывали многоугольник, содержащий все точки множества) и точка A, лежащая вне оболочки. Тогда точка плоскости называется видимой для точки А, если отрезок, соединяющий ее с точкой А, не пересекает МВО.
Ребро МВО называется видимым для точки А, если его концы видимы для А.
На следующей картинке красным помечены ребра, видимые для красной точки:
Замечание: контур триангуляции Делоне является МВО для точек, на которых построена.
Замечание 2: в алгоритме видимые для добавляемой точки А ребра образуют цепочку, то есть несколько подряд идущих ребер МВО
Хранение триангуляции в памяти
Есть некоторые стандартные способы, неплохо описанные в книге Скворцова [1]. Ввиду специфики алгоритма, я предложу свой вариант. Так как хочется проверять 4-угольники на условие Делоне, то рассмотрим их строение. Каждый 4-угольник в триангуляции представляет из себя 2 треугольника, имеющих общее ребро. У каждого ребра есть ровно 2 треугольника, прилегающих к нему. Таким образом, каждый четырехугольник в триангуляции порождается ребром и двумя вершинами, находящимися напротив ребра в прилегающих треугольниках.
Так как по ребру и двум вершинам восстанавливаются два треугольника и их смежность, то по всем таким структурам мы сможем восстановить триангуляцию. Соответственно предлагается хранить ребро с двумя вершинами в множестве и выполнять поиск по ребру (упорядоченной паре вершин).
Алгоритм
Идея заметающей прямой заключается в том, что все точки сортируются по одному направлению, а затем по очереди обрабатываются.
Проверка условия Делоне
Способы проверки четырехугольников на условие Делоне можно найти в той же книжке [1]. Подмечу лишь, что при выборе метода с тригонометрическими функциями оттуда при неаккуратной реализации могут получаться отрицательные значения синусов, есть смысл брать их по модулю.
Поиск видимых ребер
Осталось понять, как эффективно находить видимые ребра. Заметим, что предыдущая добавленная точка S находится в МВО на текущей итерации, так как имеет наибольшую координату 
, а также видима для текущей точки. Тогда, замечая, что концы видимых ребер образуют непрерывную цепочку видимых точек, мы можем идти от точки S в обе стороны по МВО и собирать ребра, пока они видимы (видимость ребра проверяется с помощью векторного произведения). Таким образом удобно хранить МВО как двусвязный список, на каждой итерации удаляя видимые ребра и добавляя 2 новых из рассматриваемой точки.
Визуализация работы алгоритма
Две красные точки — добавляемая и предыдущая. Красные ребра в каждый момент составляют стек рекурсии из шага (4):
Корректность алгоритма
Чтобы доказать корректность алгоритма, достаточно доказать сохранение инварианта в шагах (3) и (4).
Шаг (3)
После шага (3), очевидно, получится некоторая триангуляция текущего множества точек.
Шаг (4)
В процессе выполнения шага (4) все четырехугольники, не удовлетворяющие условию Делоне, находятся в стеке рекурсии (следует из описания), а значит, по окончании шага (4) все четырехугольники удовлетворяют условию Делоне, то есть действительно построена триангуляция Делоне. Тогда осталось доказать, что процесс в шаге (4) когда-нибудь закончится. Это следует из того, что все ребра, добавленные при перестроении, исходят из текущей рассматриваемой вершины (то есть на шаге 
их не больше, чем 
) и из того, что после добавления этих ребер мы не будем рассматривать четырехугольники, порожденные ими (см. предыдущее замечание), а значит, добавим не более одного раза.
Временная сложность
В среднем на равномерном, нормальном распределениях алгоритм работает довольно неплохо (результаты приведены ниже в табличке). Есть предположение, что время его работы составляет 
. В худшем случае имеет место оценка 
.
Давайте разберем время работы по частям и поймем, какая из них оказывает самое большое влияние на итоговое время:
Сортировка по направлению
Для сортировки будем использовать оценку .
Поиск видимых ребер
Для начала покажем, что время, суммарно затраченное на поиск видимых ребер, есть 
. Заметим, что на каждой итерации мы находим все видимые ребра и еще 2 (первые не видимые) за линейное время. В шаге (3) мы добавляем в МВО новые 2 ребра. Таким образом, всего в меняющейся на протяжении алгоритма МВО побывает не более 
ребер, значит, и различных видимых ребер будет не более . Еще мы найдем ребер, не являющихся видимыми. Таким образом, в общей сложности найдется не более 
ребер, что соответствует времени .
Построение новых треугольников
Суммарное время на построение треугольников из шага (3) с уже найденными видимыми ребрами, очевидно, .
Перестроение триангуляции
Осталось разобраться с шагом (4). Сначала заметим, что проверка условия Делоне и перестроение в случае его не выполнения являются довольно дорогими действиями (хоть и работают за 
). Только на проверку условия Делоне может уйти около 28 арифметических операций. Посмотрим на среднее количество перестроений в течение этого шага. Практические результаты на некоторых распределениях приведены ниже. По ним очень хочется сказать, что среднее количество перестроений растет с логарифмической скоростью, однако оставим это как лишь предположение.
Здесь еще хочется подметить, что от направления, вдоль которого производится сортировка, может сильно варьироваться среднее число перестроений на точку. Так на миллионе равномерно распределенных на длинном низком прямоугольнике с отношением сторон 100000:1 это число варьируется от 1.2 до 24 (эти значения достигаются при сортировке данных по горизонтали и вертикали соответственно). Поэтому я вижу смысл выбирать направление сортировки произвольным образом (в данном примере при произвольном выборе в среднем получалось около 2 перестроений) или выбрать его вручную, если данные заранее известны.
Таким образом, основное время работы программы обычно уходит на шаг (4). Если же он выполняется быстро, то есть смысл задуматься над ускорением сортировки.
Худший случай
В худшем случае на -ой итерации происходит рекурсивный вызов в шаге (4), то есть, суммируя по всем i, получаем асимптотику в худшем случае . Следующая картинка иллюстрирует красивый пример, на котором программа может работать долго (1100 перестроений в среднем при добавлении новой точки при входных данных в 10000 точек).
Сравнение с итеративным алгоритмом построения триангуляции Делоне с использованием kD-дерева
Описание итеративного алгоритма
Коротко опишу вышеуказанный алгоритм. При поступлении очередной точки мы с помощью kD-дерева (советую почитать про него где-нибудь, если вы не знаете) находим довольно близкий к ней уже построенный треугольник. Затем обходом в глубину ищем треугольник, в который попадает сама точка. Достраиваем ребра в вершины найденного треугольника и фактически выполняем шаг (4) из нашего алгоритма для новых четырехугольников. Так как точка может быть вне триангуляции, то для упрощения предлагается накрыть все точки большим треугольником (построить его заранее), это решит проблему.
Сходство алгоритмов
Различия алгоритмов
В итеративном алгоритме локализация точки (поиск нужного треугольника) происходит в среднем за 
, на вышеуказанных распределениях в среднем происходит 3 перестроения (как показано в [1]) при условии произвольного порядка подачи точек. Таким образом заметающая прямая выигрывает время у итеративного алгоритма в локализации, но проигрывает его в перестроениях (которые, напомню, довольно тяжелые). Ко всему прочему итеративный алгоритм работает в режиме онлайн, что также является его отличительной особенностью.
Заключение
Здесь я просто покажу некоторые интересные триангуляции, получившиеся в результате работы алгоритма.
Триангуляция (в геодезии)
Т. имеет большое научное и практическое значение. Она служит для: определения фигуры и размеров Земли методом градусных измерений; изучения горизонтальных движений земной коры; обоснования топографических съёмок в различных масштабах и целях; обоснования различных геодезических работ при изыскании, проектировании и строительстве крупных инженерных сооружений, при планировке и строительстве городов и т.д.
При построении Т. исходят из принципа перехода от общего к частному, от крупных треугольников к более мелким. В связи с этим Т. подразделяется на классы, отличающиеся точностью измерений и последовательностью их построения. В малых по территории странах Т. высшего класса строят в виде сплошных сетей треугольников. В государствах с большой территорией (СССР, Канада, КНР, США и др.) Т. строят по некоторой схеме и программе. Наиболее стройная схема и программа построения Т. применяется в СССР.
Вершины треугольников Т. обозначаются на местности деревянными или металлическими вышками высотой от 6 до 55 м в зависимости от условий местности (см. Сигнал геодезический ). Пункты Т. в целях долговременной их сохранности на местности закрепляются закладкой в грунт особых устройств в виде металлических труб или бетонных монолитов с вделанными в них металлическими марками (см. Центр геодезический ), фиксирующими положение точек, для которых даются координаты в соответствующих каталогах.
Лит.: Красовский Ф. Н., Данилов В. В., Руководство по высшей геодезии, 2 изд., ч. 1, в. 1‒2, М., 1938‒39; Инструкция о построении государственной геодезической сети СССР, 2 изд., М., 1966.
Триангуляция Делоне на сфере
Содержание
Определения [ править ]
| Определение: |
| Триангуляция — набор непересекающихся отрезков, соединяющий заданный набор точек так, что добавление новых отрезков невозможно без пересечения уже имеющихся. |
| Определение: |
| Критерий Делоне (частный случай для сферы): при построении плоскости через три точки, которые образуют треугольник, все остальные точки лежат не выше этой плоскости. |
Существование триангуляции Делоне [ править ]
Рассмотрим треугольник △ [math] OCM [/math] :
Построим выпуклую оболочку наших точек.
Все грани выпуклой оболочки окажутся внутри сферы. Поскольку, все точки лежат на сфере, не найдётся точек, которые будут лежать за гранями выпуклой оболочки, иначе выпуклую оболочку можно было бы расширить. Таким образом, все точки, будут принадлежать выпуклой оболочке. Так же ясно,что критерий Делоне будет выполняться, поскольку для каждой грани не будет точек, которые лежат выше нее. Поскольку никакие четыре точки не лежат на одной окружности в исходном наборе точек, а значит, гранями выпуклой оболочки будут треугольнички. Значит, триангуляция существует.
А поскольку выпуклая оболочка единственна, можно сказать, что и триангуляция единственна.
| Лемма (2): |
| [math]\triangleleft[/math] |
| Лемма (3): |
| [math]\triangleleft[/math] |
Статический алгоритм [ править ]
Алгоритм [ править ]
Корректность [ править ]
Корректность следует из теорем выше.
Время работы [ править ]
Локальный критерий Делоне [ править ]
| Определение: |
| Локальный критерий Делоне: при построении плоскости через три точки, образующие треугольник, противолежащие сторонам треугольника вершины соседей лежат ниже этой плоскости. |
| Утверждение: |
Из глобального в локальный очевидно. Из локального в глобальный: Посмотрим, существует ли у треугольника [math]ABD[/math] смежный треугольник, содержащий вершину [math]E[/math] : Значит глобальный критерий Делоне выполняется. |
| [math]\triangleleft[/math] |
Критерии Делоне для ребер [ править ]
| Определение: |
| Глобальный критерий Делоне для ребра: через ребро можно провести плоскость так, что все точки будут лежать не выше этой плоскости. |
| Определение: |
| Локальный критерий Делоне для ребра: через ребро можно провести плоскость так, что вершины, противолежащие этому ребру, будут лежать не выше этой плоскости |
Следовательно, глобальный критерий Делоне для ребра выполняется.
| Утверждение: |
| [math]\triangleleft[/math] |
Будем называть хорошими те рёбра, для которых выполняется локальный критерий Делоне.
Динамический алгоритм [ править ]
| Определение: |
| Рассмотрим пару смежных треугольников. Рёбра этих треугольников образуют четырёхугольник с проведённой в нём диагональю. Операция замены этой диагонали на другую называется flip (флип). |
Из леммы 4 следует, что если ребро плохое, то флип сделает его хорошим.
Рассмотрим два таких смежных треугольника, что ребро между ними является плохим.Четыре точки, принадлежащие смежным треугольникам, образуют тетраэдр.
Проведём через какой-нибудь из двух треугольников плоскость. Вершина, противолежащая основанию тетраэдра, являющегося этим треугольником, лежит выше этой плоскости (так как для плохого ребра не выполняется локальный критерий Делоне), то есть тетраэдр не включается в объем фигуры.
После флипа станет выполняться локальный критерий Делоне, то есть тело станет включать в себя тетраэдр. Поэтому после флипа плохого ребра объём тела увеличится на объём этого тетраэдра.
| Лемма (6): |
| Доказательство: |
| [math]\triangleright[/math] |
| Всего триангуляций заданного множества точек конечное число, и среди них есть триангуляция Делоне. Последовательность флипов плохих рёбер триангуляции образует такую последовательность триангуляций, что разность объёмов сферы и многогранника, постоенного по триангуляции убывает (по лемме 5). Эта последовательность конечна (при этом последней в последовательности является триангуляция Делоне), значит, число флипов, требуемых для достижения триангуляции Делоне, тоже конечно. |
| [math]\triangleleft[/math] |
| Лемма (7): |
Случай, когда точка вставляется на ребро, рассматривается аналогично. |
| [math]\triangleleft[/math] |
| Утверждение: |
| Доказательство: |
| [math]\triangleright[/math] |
| Копирует случай на плоскости. |
| [math]\triangleleft[/math] |
Удаление точки [ править ]
В результате удаления у нас появляетя некоторый звездный многоугольник на сфере, который надо триангулировать. Из-за того, что у нас сфера, и задача триангуляции сведена к задаче построения выпуклой оболочки, то, следовательно, нам перестает быть важным критерий Делоне, нам просто нужно у звездного многоугольника на сфере как-то провести ребра так, чтобы было выпукло.
Представим себе, что вместо того, чтобы удалять точку, мы просто опускаем ее во внутрь до тех пор, пока она не перестает быть видимой в построенном на триангуляции многоугольнике. Предположим, что мы находимся в удаляемой точке, движемся в центр сферы и смотрим только в направлении движения.
Исходный многогранник был выпуклым.
Если бы мы могли видеть грани, находящиеся вне нашего звездного многоугольника, то это бы значило, что от удаляемой вершины до вершины, противолежащей ребру звездного многоугольника и лежащей в этой грани можно было бы провести ребро. Которого изначально не было.И это ребро лежало бы вне нашего многогранника, что противоречило бы его выпуклости.
Понятно, что мы постепенно перестаем видеть какие-то грани.Это происходит когда мы уходим ближе к центру, чем плоскость, соответствующая грани.
Ухом является часть, которая по двум ребрам граничит с невидимыми гранями и по одному ребру может граничить с видимой. Посмотрим в каком порядке исчезают грани. Предположим нас есть кандидат на то, чтобы исчезнуть. Это какой-то выпуклый треугольник. Предположим, что у этого треугольника есть хотя бы два соседа, которые видны, но сам выпуклый многоугольник уже почти исчез (находится на одной плоскости с нашей точкой). Если мы видим две другие грани, то
Теперь у нас возможна ситуация, когда перестает быть видимым не ухо, а грань, являющаяся выпуклым многоугольником(по лемме 2). Все хорошо, по лемме 3 мы можем триангулировать эту грань как угодно.
Таким образом, мы будем перестраивать нашу выпуклую оболочку и, соответственно, триангуляцию.
Алгоритм удаления точки [ править ]
Предикат [ править ]
Распишем и разложим по последней строке: [math]\begin
Тогда условие, по которому мы будем устанавливать порядок в приоритетной очереди будет:
Время работы [ править ]
Локализация в триангуляции [ править ]
Построим алгоритм на сфере по аналогии с плоскостью.
Структура данных [ править ]
Локализационная структура состоит из нескольких уровней, где каждый уровень — триангуляция Делоне. На нижнем уровне содержатся все точки. Далее точка с вероятностью [math] p [/math] попадает на следующий уровень. Если на последнем уровне находится одна точка, то дальше она уже не пойдет.
| Лемма (О количестве уровней): |
| Доказательство: |
| [math]\triangleright[/math] |
| То же самое, что и для плоскости. |
| [math]\triangleleft[/math] |
| Утверждение: |
| [math]\triangleright[/math] |
| Опять же доказательство копируется с плоскости. |
| [math]\triangleleft[/math] |
Алгоритм [ править ]
Чтобы найти треугольник, которому принадлежит точка запроса(точка [math]Q[/math] ), сначала найдем ближайшую к ней точку триангуляции(точка [math]P[/math] ), а зачем вдоль луча [math]PQ[/math] будем обходить треугольники, пока не локализуемся.
Поиск точки [math]P[/math] :
Меняем порядок суммирования, и получаем:
По предыдущей лемме получаем:
| Лемма: |
Движение вдоль луча [ править ] |