Алгоритмы триангуляции делоне реферат
Обновлено: 02.07.2024
Окружность, спроецированная на параболоид, находится в одной плоскости. Все точки, лежащие внутри окружности, будут лежать под этой плоскостью. Точки, лежащие вне окружности, будут лежать над плоскостью.
Рассмотрим окружность с центром в точке [math](a, b)[/math] радиуса [math]r[/math] , она описывается уравнением: [math](x - a)^2 + (y - b)^2 = r^2[/math] .
Раскрывая скобки в уравнении окружности, получим [math]x^2 - 2ax + a^2 + y^2 - 2by + b^2 = r^2[/math]
Рассмотрим параболоид, пускай его уравнение имеет вид [math]x^2 + y^2 = Cz[/math] .
При проецировании, для проекции окружности на параболоид верны оба уравнения: и окружности, и параболоида, поэтому в уравнение окружности вместо [math]x^2 + y^2[/math] можно подставить [math]Cz[/math] , получится [math](-2a)x + (-2b)y + Cz + (a^2 + b^2 - r^2) = 0[/math]
Заметим, что получившееся уравнение является уравнением плоскости: [math]Ax + By + Cz + D = 0[/math] , то есть, все точки проекции окружности будут лежать в одной плоскости.
Рассмотрим любую точку внутри данной окружности. Через нее можно провести окружность с центром в точке [math](a, b)[/math] и радиусом [math]r' \lt r[/math] , тогда плоскость, проходящая через проекцию этой окружности на параболоид будет иметь уравнение [math]Ax + By + Cz + D' = 0[/math] , то есть, обе плоскости будут параллельны и вторая плоскость будет лежать под плоскостью окружности (поскольку [math]r' \lt r[/math] , то [math]D' = (a^2 + b^2 - r'^2) \gt (a^2 + b^2 - r^2) = D[/math] ).
Спроецируем все точки на параболоид и построим выпуклую оболочку.
Все грани выпуклой оболочки окажутся внутри параболоида из-за его выпуклости. При этом точки лежат на параболоиде. Поэтому не найдётся точек, которые будут лежать за гранями выпуклой оболочки. То есть все точки, спроецированные на параболоид, будут принадлежать выпуклой оболочке.
По лемме 1 очевидно, что внутри окружностей, описанных вокруг проекций граней выпуклой оболочки, не будет лежать никаких точек. Значит, проекции граней — фигуры подразбиения Делоне. Значит, такое подразбиение существует.
Триангуляции Делоне принадлежат те и только те рёбра (с поправкой на точки, лежащие на одной окружности), которые удовлетворяют критерию Делоне.
То, что для рёбер, принадлежащих триангуляции Делоне, выполняется критерий Делоне для рёбер, очевидно (вокруг каждого ребра можно описать окружность, проходящую через противолежащую ему точку в смежном треугольнике, причём в окружности не будет никаких точек по критерию Делоне).
Докажем, что если для ребра выполняется критерий Делоне, то оно принадлежит триангуляции Делоне.
Будем называть хорошими те рёбра, для которых выполняется локальный критерий Делоне.
Если для всех рёбер выполняется локальный критерий Делоне, то выполняется и глобальный критерий Делоне.
Предположим, что это не так, то есть все рёбра хорошие, но существуют треугольники, описанная окружность которых содержат какие-либо точки триангуляции. Возьмём какую-либо конфликтную точку [math]E[/math] . Рассмотрим такой треугольник [math]ABC[/math] из тех, в описанную окружность которых попадает [math]E[/math] , что угол [math]BEC[/math] максимален, если [math]BC[/math] — ближайшая к точке [math]E[/math] сторона. Пусть треугольник [math]BDC[/math] — смежный с [math]ABC[/math] .
Докажем, что точка [math]E[/math] лежит в окружности, описанной вокруг [math]BDC[/math] . Предположим, что это не так. Посмотрим на окружность, описанную вокруг треугольника [math]ABC[/math] : [math]\angle BAC + \angle BEC \gt 180^\circ[/math] и [math]\angle BAC + \angle BDC \lt 180^\circ[/math] . Если точка [math]E[/math] не лежит в окружности, описанной вокруг треугольника [math]BDC[/math] , то [math]\angle BEC \lt \angle BDC[/math] , что противоречит предыдущим двум неравенствам.
Из леммы 3 следует, что если ребро плохое, то флип сделает его хорошим.
Рассмотрим два таких смежных треугольника, что ребро между ними является плохим. Спроецируем их на параболоид. Четыре точки, принадлежащие смежным треугольникам, при проекции на параболоид образуют тетраэдр.
Проведём через какой-нибудь из двух треугольников плоскость. Вершина, противолежащая основанию тетраэдра, являющегося этим треугольником, лежит ниже этой плоскости (так как не выполняется локальный критерий Делоне), то есть тетраэдр лежит ниже тела, образующегося при проекции всей триангуляции на параболоид.
Если в триангуляцию Делоне вставить точку в некоторый треугольник и соединить его вершины с этой точкой, то получившиеся рёбра будут хорошими.
Предположим, точка была вставлена не на ребро. Рассмотрим любое из рёбер — пусть это будет ребро [math]VC[/math] . Проведём окружность, описывающую треугольник [math]ABC[/math] . По критерию Делоне в ней не будет никаких точек триангуляции. На ребре [math]VC[/math] можно построить окружность, изнутри касающуюся окружности, описанной вокруг треугольника. В ней тоже нет никаких точек. Значит, для [math]VC[/math] выполняется критерий Делоне для рёбер, то есть, оно хорошее.
Для начала локализуемся: поймём, в каком фейсе лежит точка (или на каком ребре).
Если точка лежит внутри фейса, добавляем три ребра, сам фейс превращаем в один из новых смежных с вставляемой точкой и добавялем ещё два фейса.
Если же точка лежит на ребре, два смежных с ребром фейса превращаем в два новых, добавляем ещё два, а так же превращаем ребро, на которое вставляется точка, в ребро, которое заканчивается в этой точке, и вставляем три новых.
Итого у нас появилось несколько новых рёбер. Они все хорошие (по лемме 7), плохими могут оказаться только рёбра, противолежащие вставленной точке. Флипаем рёбра, пока триангуляция не станет хорошей.
Представим, что вне триангуляции — бесконечные треугольники, основания которых — рёбра выпуклой оболочки триангуляции, а противолежащая ребру вершина — это бесконечно удалённая точка. Тогда понятно, что вставка точки, не лежащей в триангуляции, сведётся к вставке точки внутрь триангуляции, если мы научимся обрабатывать бесконечные фейсы.
Бесконечно удалённая точка имеет координаты [math](0,0,1,0)[/math] (последняя координата — однородная).
Тогда проверка на то, является ли хорошим ребро, инцидентное бесконечно удалённой точке, упрощается: [math] \begin a_x & a_y & a_x^2 + a_y^2 & 1 \\ b_x & b_y & b_y^2 + b_y^2 & 1 \\ c_x & c_y & c_x^2 + c_y^2 & 1 \\ 0 & 0 & 1 & 0 \end = \begin a_x & a_y & 1 \\ b_x & b_y & 1 \\ c_x & c_y & 1 \end [/math] , то есть достаточно проверить поворот трёх остальных точек образованного двумя бесконечными треугольниками четырёхугольника.
Проверка, принадлежит ли точка бесконечному треугольнику, тоже проста: нужно, чтобы из точки было видно ребро, противолежащее бесконечно удалённой точке, в бесконечном треугольнике. Это проверяется предикатом поворота.
Доказательство по индукции.
База. По лемме 7 изначально не будут флипаться новые рёбра, инцидентные точке, то есть плохими могут оказаться только рёбра, противолежащие точке.
Предположим, что мы вставляем [math]i+1[/math] -ую точку из последовательности из [math]n[/math] точек. Рассмотрим все перестановки из этих [math]i+1[/math] точек, означающие порядок вставки этих точек. Всего таких перестановок [math](i+1)![/math] . Тогда средняя степень последней вершины среди перестановок равна:
Каждая из [math]i+1[/math] вершин побывает последней ровно [math]i![/math] раз, поэтому:
Так как среднее число флипов — [math]O(1)[/math] , то время вставки целиком зависит от времени локализации.
При удалении точки получится звёздный многоугольник, который можно затриангулировать за линию . При этом все рёбра, полученные в результате триангуляции звёздного многоугольника, могут оказаться плохими, поэтому необходимо пройтись по ним и пофлипать, если нужно.
Средняя степень вершины в триангуляции — [math]O(1)[/math] , поэтому триангуляция звёздного многоугольника будет тоже за [math]O(1)[/math] . Новых рёбер получится [math]O(1)[/math] , проверить их на локальный критерий Делоне и пофлипать тоже можно за [math]O(1)[/math] . Итого удаление точки работает за [math]O(1)[/math] .
Локализационная структура состоит из нескольких уровней, где каждый уровень — это триангуляция Делоне. На нижнем уровне содержатся все точки. Каждая точка с вероятностью [math]p[/math] проходит на следующий уровень (причём если точка — единственная на последнем уровне, то дальше она не пройдёт).
Уровни связаны между собой следующим образом: на уровне [math]i[/math] каждая точка содержит указатель на себя же на уровне [math]i-1[/math] .
Как происходит локализация: нам дают точку [math]v_[/math] , которая на предыдущем уровне была ближайшей к точке [math]q[/math] , которую мы локализуем. Нужно получить следующую точку [math]v_i[/math] , которая будет ближайшей уже на этом уровне. Делается это следующим образом:
- Находим, в каком из треугольников, смежных с [math]v_[/math] , лежит отрезок [math]v_ q[/math]
- Находим, какие рёбра треугольников пересекает [math]v_ q[/math] , в итоге находим треугольник, в котором лежит [math]q[/math]
- Находим ближайшую к [math]q[/math] точку. Первым кандидатом на то, чтобы быть ближайшей точкой, становится ближайшая к [math]q[/math] вершина найденного в предыдущем пункте треугольника. Для каждого кандидата нужно просмотреть смежные вершины в поиске точки, которая находится ближе к [math]q[/math] — эта точка становится следующим кандидатом. Если же среди соседей точки не нашлось более близких, значит, эта точка и есть ближайшая.
Для оценки матожидания посчитаем вероятность того, что количество уровней [math]h[/math] равно [math]k[/math] при вероятности пройти на следующий уровень равной [math]p[/math] .
[math]p(h \leq k) = (1 - p^)^n[/math] , потому что вероятность того, что точка дойдёт до уровня [math]k + 1[/math] , равна [math]p^[/math] .
[math]p(h \geq k) = (1 - (1 - p^k)^n)[/math] , потому что вероятность того, что точка не дойдёт до уровня [math]k[/math] , равна [math]1 - p^k[/math] .
[math]p(h = k) = 1 - p(h \gt k) - p(h \lt k) = 1 - (1 - (1 - p^)^n) - (1 - p^)^n = (1 - p^)^n - (1 - p^k)^n \leq 1 - (1 - p^k)^n \leq np^k[/math]
[math]E(h) = \sum\limits_^ <\infty>k \cdot p(h = k) = p(1) \cdot 1 + \dots + p(\log_ n) \cdot \log_ n + \sum\limits_
Оценим первую сумму:
[math]p(1) \cdot 1 + \dots + p(\log_ n) \cdot \log_ n \leq p(1) \cdot \log_ n + \dots + p(\log_ n) \cdot \log_ n = O(\log(n))[/math] , поскольку сумма этих вероятностей не превосходит единицу.
Оценим вторую сумму:
[math]\sum\limits_ n + 1>^ <\infty>k \cdot p(k) \leq \sum\limits_ n>^ <\infty>k \cdot n p^k = n \cdot \sum\limits_ n>^ <\infty>k \cdot p^k[/math]
Рассмотрим эту сумму:
[math]\sum\limits_ n>^ <\infty>k \cdot p^k = p^ <\log_n> \cdot \sum\limits_^ <\infty>(k + \log_ n) \cdot p^k = p^ <\log_n> \cdot (\sum\limits_^ <\infty>(k p^k) + \log_ n \cdot \sum\limits_^ <\infty>(p^k)) = p^ <\log_n> \cdot (O(1) + \log_ n \cdot O(1)) = 1/n \cdot O(\log(n))[/math]
Предположим, что это не так.
Пусть некоторая точка [math]u[/math] является ближайшей для семи точек. Соединим эти семь точек с точкой [math]u[/math] отрезками и рассмотрим минимальный из углов, который образуют проведённые отрезки [math]vu[/math] и [math]wu[/math] . Этот угол [math]\alpha[/math] меньше 60° (иначе все семь углов больше либо равны 60° и их сумма больше 360°).
Для заданной точки [math]q[/math] на [math]k[/math] -ом уровне средняя степень ближайшей на [math]k+1[/math] -ом уровне вершины равна [math]O(1)[/math] .
Функция [math]nn[/math] принимает точку и множество и возвращает ближайшего соседа заданной точки из заданного множества.
Рассмотрим некоторый уровень [math]S_k[/math] . Определим множество [math]R_k=S_k\cup\[/math] . Рассмотрим все возможные подмножества [math]R_k[/math] , равномощные [math]R_[/math] , тем самым рассмотрев все возможные уровни [math]k+1[/math] . Для каждой точки из каждого подмножества [math]R'_[/math] рассмотрим степень ближайшей вершины и усредним всё, получив нужную нам оценку.
Назовём графом [math]NN(\)[/math] двудольный граф, в левой и правой долях содержащий точки [math]\[/math] , рёбра [math]uv[/math] которого означают, что точка [math]v[/math] является ближайшей для точки [math]u[/math] (точка [math]u[/math] лежит в левой доли, точка [math]v[/math] лежит в правой доли).
По лемме 11 степень вершины из правой доли графа [math]NN[/math] не может быть больше шести.
Среднее число точек, лежащих в окружности с центром в точке [math]q[/math] и проходящей через [math]v_[/math] , равно [math]O(1)[/math] .
Рассмотрим точки триангуляции [math]\[/math] . Для каждой точки [math]a_i[/math] построим окружность с центром в точке [math]a_i[/math] , проходящую через ближайшую к ней точку. Докажем, что заданная точка [math]w[/math] попадёт в [math]O(1)[/math] таких окружностей на предыдущем уровне. Разделим плоскость на шесть частей прямыми, проходящими через точку [math]w[/math] . Рассмотрим одну из частей. Отсортируем все точки, попавшие в неё, по увеличению расстояния до [math]w[/math] . Получим такую последовательность точек [math]\[/math] , что [math]|wa_i|\le|wa_|[/math] . Заметим, что если какая-нибудь точка [math]a_i[/math] содержится на предыдущем уровне, то все точки, начиная с [math]a_[/math] уже не содержат в своей окружности точку [math]w[/math] . Таким образом, среднее число точек [math]k[/math] , в окружности которых содержится точка [math]w[/math] :
[math]E(k)\le6\cdot\sum_i i(1-p)^i p = O(1)[/math]
Среднее число рёбер, пересечённое отрезком [math]qv_[/math] во втором этапе алгоритма локализации, равно [math]O(1)[/math] .
Рассмотрим рёбра, пересекающие [math]qv_[/math] , для которых хотя бы одна из граничных точек окажется в окружности с центром в точке [math]q[/math] , проходящей через [math]v_[/math] . Число таких рёбер не превосходит суммы степеней вершин, лежащих внутри окружности. А по лемме 13 число таких точек равно [math]O(1)[/math] . При этом средняя степень вершины равна [math]O(1)[/math] . Таким образом, число таких рёбер равно [math]O(1)[/math] .
Докажем, что число рёбер, пересекающих [math]qv_[/math] , для которых обе граничные точки лежат вне окружности, тоже равно [math]O(1)[/math] . При вставке точки [math]q[/math] в триангуляцию для этих рёбер перестанет выполняться критерий Делоне: в любой окружности, построенной на ребре как на хорде, будет содержаться либо точка [math]q[/math] , либо точка [math]v_[/math] . Поэтому эти рёбра придётся флипнуть. Число флипов при вставке точки равно [math]O(1)[/math] , поэтому число таких рёбер равно [math]O(1)[/math] .
Среднее число треугольников, посещённых на третьем этапе алгоритма локализации, равно [math]O(1)[/math] .
Докажем, что каждый этап локализации происходит за [math]O(1)[/math] .
1 этап: по лемме 12 средняя степень вершины [math]v_[/math] равна [math]O(1)[/math] , поэтому треугольников, в которых может лежать отрезок [math]qv_[/math] тоже [math]O(1)[/math] . Просмотрев их все, за [math]O(1)[/math] можно понять, в каком из них лежит отрезок [math]qv_[/math] .
2 этап: число рёбер, пересечённых отрезком [math]qv_[/math] , равно [math]O(1)[/math] (по лемме 14). Поэтому этот этап локализации тоже происходит за [math]O(1)[/math] .
Смотрим на список рёбер, пересечённых ещё не вставленным констрейнтом, и флипаем их. Последнее флипнутое ребро и будет констрейнтом (по понятным причинам) , после флипа пометим его как констрейнт. Затем флипаем всё, что могло стать плохим (кроме констрейнта), пока триангуляция вновь не станет хорошей.
Аналогично: помечаем ребро как не-констрейнт и флипаем, пока не дойдём до хорошей триангуляции.
Задача построения триангуляции Делоне является одной из базовых в вычислительной геометрии. К ней сводятся многие другие задачи, она широко используется в машинной графике и геоинформационных системах для моделирования поверхностей и решения пространственных задач. Впервые задача построения триангуляции Делоне была поставлена в 1934 г. в работе советского математика Бориса Николаевича Делоне.
Содержание
Вложенные файлы: 1 файл
Реферат ГИС.docx
Федеральное государственное автономное
высшего профессионального образования
Институт космических и информационных технологий
Триангуляция Делоне. Полигоны Вороного.
Список использованной литературы 17
Задача построения триангуляции Делоне является одной из базовых в вычислительной геометрии. К ней сводятся многие другие задачи, она широко используется в машинной графике и геоинформационных системах для моделирования поверхностей и решения пространственных задач. Впервые задача построения триангуляции Делоне была поставлена в 1934 г. в работе советского математика Бориса Николаевича Делоне.
- Триангуляция Делоне
- Основные определения и задачи построения триангуляции Делоне
Определение 1. Триангуляцией называется планарный граф, все внутренние области которого являются треугольниками.
Рис 1 - Триангуляция.
Определение 2. Выпуклой триангуляцией называется такая триангуляция, для которой минимальный многоугольник, охватывающий все треугольники, будет выпуклым. Триангуляция, не являющаяся выпуклой, называется невыпуклой.
Определение 3. Задачей построения триангуляции по заданному набору двумерных точек называется задача соединения заданных точек непересекающимися отрезками так, чтобы образовалась триангуляция.
Определение 4. Триангуляция называется оптимальной, если сумма длин всех рёбер минимальна среди всех возможных триангуляций, построенных на тех же исходных точках.
Одним из первых был предложен следующий алгоритм построения триангуляции.
Жадный алгоритм построения триангуляции.
Шаг 1. Генерируется список всех возможных отрезков, соединяющих пары исходных точек, и он сортируется по длинам отрезков.
Шаг 2. Начиная с самого короткого, последовательно выполняется вставка отрезков в триангуляцию. Если отрезок не пересекается с другими ранее вставленными отрезками, то он вставляется, иначе он отбрасывается.
Заметим, что если все возможные отрезки имеют разную длину, то результат работы этого алгоритма однозначен, иначе он зависит от порядка вставки отрезков одинаковой длины.
Определение 5. Триангуляция называется жадной, если она построена жадным алгоритмом.
Определение 6. Говорят, что триангуляция удовлетворяет условию Делоне, если внутрь окружности, описанной вокруг любого построенного треугольника, не попадает ни одна из заданных точек триангуляции.
Определение 7. Триангуляция называется триангуляцией Делоне, если она является выпуклой и удовлетворяет условию Делоне.
Рис 2 - Триангуляция Делоне.
Определение 8. Говорят, что пара соседних треугольников триангуляции удовлетворяет условию Делоне, если этому условию удовлетворяет триангуляция, составленная только из этих двух треугольников.
Определение 9. Говорят, что треугольник триангуляции удовлетворяет условию Делоне, если этому условию удовлетворяет триангуляция, составленная только из этого треугольника и трёх его соседей (если они существуют).
- Теоремы для алгоритмов построения триангуляции Делоне
Теорема 1. Триангуляцию Делоне можно получить из любой другой триангуляции по той же системе точек, последовательно перестраивая пары соседних треугольников ∆ABC и ∆BCD, не удовлетворяющих условию Делоне, в пары треугольников ∆ABD и ∆ACD. Такая операция перестроения также часто называется флипом.
Данная теорема позволяет строить триангуляцию Делоне последовательно, построив вначале некоторую триангуляцию, а потом последовательно улучшая её до выполнения условия Делоне.
Теорема 2. Триангуляция Делоне обладает максимальной суммой минимальных углов всех своих треугольников среди всех возможных триангуляций.
Теорема 3. Триангуляция Делоне обладает минимальной суммой радиусов окружностей, описанных около треугольников, среди всех возможных триангуляций.
В данных теоремах фигурирует некая суммарная характеристика всей триангуляции (сумма минимальных углов или сумма радиусов), оптимизируя которую в парах смежных треугольников, можно получить триангуляцию Делоне.
1.3 Структуры для представления триангуляции
Выбор структуры для представления триангуляции оказывает существенное влияние на теоретическую трудоёмкость алгоритмов, а также на скорость конкретной реализации. Кроме того, выбор структуры может зависеть от цели дальнейшего использования триангуляции.
1.3.1 Структура узлы с соседями
Для каждого узла триангуляции хранятся его координаты на плоскости и список указателей на соседние узлы (список номеров узлов), с которыми есть общие рёбра. По сути, список соседей определяет в неявном виде рёбра триангуляции. Треугольники же при этом не представляются вообще, что является обычно существенным препятствием для дальнейшего применения триангуляции. Кроме того, недостатком является переменный размер структуры узла, зачастую приводящий к неэкономному расходу оперативной памяти при построении триангуляции.
Основой триангуляции является список ориентированных рёбер. При этом каждое ребро входит в структуру триангуляцию дважды, но направленными в противоположные стороны.
Для каждого ребра хранятся следующие указатели:
4) на треугольник, находящийся справа от ребра.
Последний указатель не нужен для построения триангуляции, и поэтому его наличие должно определяться в зависимости от цели дальнейшего применения триангуляции.
Для каждого треугольника хранятся три указателя на образующие его узлы и три указателя на смежные треугольники.
Нумерация точек и соседних треугольников производится в порядке обхода по часовой стрелке, при этом напротив точки с номером i располагается ребро, соответствующее соседнему треугольнику с таким же номером.
Рёбра в данной триангуляции в явном виде не хранятся. При необходимости же они обычно представляются как указатель на треугольник и номер ребра внутри него.
Данная структура часто применяется на практике, особенно в задачах, где требуется в явном виде представлять рёбра триангуляции.
Данная структура часто применяется на практике, особенно в задачах, где требуется в явном виде представлять рёбра триангуляции.
2 Алгоритмы триангуляции Делоне
2.1 Классификация алгоритмов триангуляции Делоне
В настоящее время известно значительное количество различных алгоритмов построения триангуляции Делоне. На рисунке 9 приведена классификация только основных из них (жирным шрифтом выделены конкретные алгоритмы). Кроме этих алгоритмов, существуют и другие, менее известные, но они обладают заведомо худшими характеристиками.
Рисунок 9 – Классификация алгоритмов построения триангуляции Делоне.
2.2 Итеративные алгоритмы с кэшированием поиска треугольников
Рассмотрим подробнее итеративные алгоритмы с кэшированием поиска треугольников.
Основная идея кэширования заключается в построении некоторого более простого, чем триангуляция, планарного разбиения плоскости, в котором можно быстро выполнять локализацию точек. Для каждого элемента простого разбиения делается ссылка на треугольник триангуляции. Процедура поиска сводится к локализации элемента простого разбиения, перехода по ссылке к треугольнику и последующей локализации искомого треугольника алгоритмом из простого итеративного алгоритма триангуляции Делоне. В качестве такого разбиения проще всего использовать регулярную сеть квадратов.
Алгоритм триангуляции Делоне методом заметающей прямой
Доброго времени суток!
В этой статье я подробно опишу алгоритм, который у меня получился в результате использования идеи "заметающей прямой" для построения триангуляции Делоне на плоскости. В нем есть несколько идей, которые я нигде не встречал, когда читал статьи про триангуляцию. Возможно, кто-то тоже найдет их необычными. Я постараюсь сделать все в лучших традициях и включить в рассказ следующие вещи: описание используемых структур данных, описание шагов алгоритма, доказательство корректности, временные оценки, а также сравнение с итеративным алгоритмом, использующим kD-дерево.
Определения и постановка задачи
Говорят, что на множестве точек на плоскости задана триангуляция, если некоторые пары точек соединены ребром, любая конечная грань в получившемся графе образует треугольник, ребра не пересекаются, и граф максимален по количеству ребер.
![]()
Триангуляцией Делоне называется такая триангуляция, в которой для любого треугольника верно, что внутри описанной около него окружности не находится точек из исходного множества.
![]()
Замечание: для заданного множества точек, в котором никакие 4 точки не находятся на одной окружности, существует ровно одна триангуляция Делоне.
Пусть на множестве точек задана триангуляция. Будем говорить, что некоторое подмножество точек удовлетворяет условию Делоне, если триангуляция, ограниченная на это подмножество, является триангуляцией Делоне для него.
Критерий для триангуляции Делоне
Выполнение условия Делоне для всех точек, образующих четырехугольник в триангуляции, эквивалентно тому, что данная триангуляция является триангуляцией Делоне.
Замечание: для невыпуклых четырехугольников условие Делоне всегда выполнено, а для выпуклых четырехугольников (вершины которого не лежат на одной окружности) существует ровно 2 возможные триангуляции (одна из которых является триангуляцией Делоне).
![]()
Задача заключается в том, чтобы для заданного множества точек построить триангуляцию Делоне.
Видимые точки и видимые ребра
Пусть задана минимальная выпуклая оболочка (далее МВО) конечного множества точек (ребра, соединяющие некоторые из точек так, чтобы они образовывали многоугольник, содержащий все точки множества) и точка A, лежащая вне оболочки. Тогда точка плоскости называется видимой для точки А, если отрезок, соединяющий ее с точкой А, не пересекает МВО.
Ребро МВО называется видимым для точки А, если его концы видимы для А.
На следующей картинке красным помечены ребра, видимые для красной точки:
![]()
Замечание: контур триангуляции Делоне является МВО для точек, на которых построена.
Замечание 2: в алгоритме видимые для добавляемой точки А ребра образуют цепочку, то есть несколько подряд идущих ребер МВО
Хранение триангуляции в памяти
Есть некоторые стандартные способы, неплохо описанные в книге Скворцова [1]. Ввиду специфики алгоритма, я предложу свой вариант. Так как хочется проверять 4-угольники на условие Делоне, то рассмотрим их строение. Каждый 4-угольник в триангуляции представляет из себя 2 треугольника, имеющих общее ребро. У каждого ребра есть ровно 2 треугольника, прилегающих к нему. Таким образом, каждый четырехугольник в триангуляции порождается ребром и двумя вершинами, находящимися напротив ребра в прилегающих треугольниках. Так как по ребру и двум вершинам восстанавливаются два треугольника и их смежность, то по всем таким структурам мы сможем восстановить триангуляцию. Соответственно предлагается хранить ребро с двумя вершинами в множестве и выполнять поиск по ребру (упорядоченной паре вершин).
![]()
Идея заметающей прямой заключается в том, что все точки сортируются по одному направлению, а затем по очереди обрабатываются.
Отсортируем все точки вдоль некоторой прямой (для простоты по координате х).
Построим треугольник на первых 3 точках.
Далее для каждой следующей точки будем выполнять шаги, сохраняющие инвариант, что имеется триангуляция Делоне для уже добавленных точек и, соответственно, МВО для них.
Добавим треугольники, образованные видимыми ребрами и самой точкой (то есть добавим ребра из рассматриваемой точки во все концы видимых ребер).
Проверим на условие Делоне все четырехугольники, порожденные видимыми ребрами. Если где-то условие не выполнилось, то перестроим триангуляцию в четырехугольнике (напоминаю, что их всего две) и рекурсивно запустим проверку для четырехугольников, порожденных ребрами текущего четырехугольника (ибо только в них после изменения условие Делоне могло нарушиться).
Замечание: в шаге (4) при рекурсивном запуске можно не проверять четырехугольники, порожденные ребрами, исходящими из рассматриваемой на данной итерации точки (их всегда два из четырех). Чаще всего они будут невыпуклыми, для выпуклых доказательство чисто геометрическое, оставлю его на читателя. Далее будем считать, что выполняется только 2 рекурсивных запуска на каждое перестроение.
Проверка условия Делоне
Способы проверки четырехугольников на условие Делоне можно найти в той же книжке [1]. Подмечу лишь, что при выборе метода с тригонометрическими функциями оттуда при неаккуратной реализации могут получаться отрицательные значения синусов, есть смысл брать их по модулю.
Поиск видимых ребер
Осталось понять, как эффективно находить видимые ребра. Заметим, что предыдущая добавленная точка S находится в МВО на текущей итерации, так как имеет наибольшую координату х, а также видима для текущей точки. Тогда, замечая, что концы видимых ребер образуют непрерывную цепочку видимых точек, мы можем идти от точки S в обе стороны по МВО и собирать ребра, пока они видимы (видимость ребра проверяется с помощью векторного произведения). Таким образом удобно хранить МВО как двусвязный список, на каждой итерации удаляя видимые ребра и добавляя 2 новых из рассматриваемой точки.
![]()
Визуализация работы алгоритма
Две красные точки - добавляемая и предыдущая. Красные ребра в каждый момент составляют стек рекурсии из шага (4):
Чтобы доказать корректность алгоритма, достаточно доказать сохранение инварианта в шагах (3) и (4).
После шага (3), очевидно, получится некоторая триангуляция текущего множества точек.
В процессе выполнения шага (4) все четырехугольники, не удовлетворяющие условию Делоне, находятся в стеке рекурсии (следует из описания), а значит, по окончании шага (4) все четырехугольники удовлетворяют условию Делоне, то есть действительно построена триангуляция Делоне. Тогда осталось доказать, что процесс в шаге (4) когда-нибудь закончится. Это следует из того, что все ребра, добавленные при перестроении, исходят из текущей рассматриваемой вершины (то есть на шаге i их не больше, чем i - 1) и из того, что после добавления этих ребер мы не будем рассматривать четырехугольники, порожденные ими (см. предыдущее замечание), а значит, добавим не более одного раза.
В среднем на равномерном, нормальном распределениях алгоритм работает довольно неплохо (результаты приведены ниже в табличке). Есть предположение, что время его работы составляет O( NlogN ). В худшем случае имеет место оценка O( N^2 ).
![]()
Давайте разберем время работы по частям и поймем, какая из них оказывает самое большое влияние на итоговое время:
Сортировка по направлению
Для сортировки будем использовать оценку O( NlogN ).
Поиск видимых ребер
Для начала покажем, что время, суммарно затраченное на поиск видимых ребер, есть O( N ). Заметим, что на каждой итерации мы находим все видимые ребра и еще 2 (первые не видимые) за линейное время. В шаге (3) мы добавляем в МВО новые 2 ребра. Таким образом, всего в меняющейся на протяжении алгоритма МВО побывает не более 2 * N ребер, значит, и различных видимых ребер будет не более 2 * N. Еще мы найдем 2 * N ребер, не являющихся видимыми. Таким образом, в общей сложности найдется не более 4 * N ребер, что соответствует времени O( N ).
Построение новых треугольников
Суммарное время на построение треугольников из шага (3) с уже найденными видимыми ребрами, очевидно, O( N ).
Осталось разобраться с шагом (4). Сначала заметим, что проверка условия Делоне и перестроение в случае его не выполнения являются довольно дорогими действиями (хоть и работают за O(1)). Только на проверку условия Делоне может уйти около 28 арифметических операций. Посмотрим на среднее количество перестроений в течение этого шага. Практические результаты на некоторых распределениях приведены ниже. По ним очень хочется сказать, что среднее количество перестроений растет с логарифмической скоростью, однако оставим это как лишь предположение.
![]()
Здесь еще хочется подметить, что от направления, вдоль которого производится сортировка, может сильно варьироваться среднее число перестроений на точку. Так на миллионе равномерно распределенных на длинном низком прямоугольнике с отношением сторон 100000:1 это число варьируется от 1.2 до 24 (эти значения достигаются при сортировке данных по горизонтали и вертикали соответственно). Поэтому я вижу смысл выбирать направление сортировки произвольным образом (в данном примере при произвольном выборе в среднем получалось около 2 перестроений) или выбрать его вручную, если данные заранее известны.
Таким образом, основное время работы программы обычно уходит на шаг (4). Если же он выполняется быстро, то есть смысл задуматься над ускорением сортировки.
В худшем случае на i-ой итерации происходит i - 1 рекурсивный вызов в шаге (4), то есть, суммируя по всем i, получаем асимптотику в худшем случае O( n^2 ). Следующая картинка иллюстрирует красивый пример, на котором программа может работать долго (1100 перестроений в среднем при добавлении новой точки при входных данных в 10000 точек).
![]()
Сравнение с итеративным алгоритмом построения триангуляции Делоне с использованием kD-дерева
Описание итеративного алгоритма
Коротко опишу вышеуказанный алгоритм. При поступлении очередной точки мы с помощью kD-дерева (советую почитать про него где-нибудь, если вы не знаете) находим довольно близкий к ней уже построенный треугольник. Затем обходом в глубину ищем треугольник, в который попадает сама точка. Достраиваем ребра в вершины найденного треугольника и фактически выполняем шаг (4) из нашего алгоритма для новых четырехугольников. Так как точка может быть вне триангуляции, то для упрощения предлагается накрыть все точки большим треугольником (построить его заранее), это решит проблему.
На самом деле, если точки добавляются в отсортированном по направлению порядке, то наш алгоритм фактически работает также, как итеративный, разве что количество перестроений меньше. Следующая анимация это отлично демонстрирует. На ней точки добавлялись справа налево, и все они накрыты большим треугольником, который впоследствии удаляется.
В итеративном алгоритме локализация точки (поиск нужного треугольника) происходит в среднем за O( logN ), на вышеуказанных распределениях в среднем происходит 3 перестроения (как показано в [1]) при условии произвольного порядка подачи точек. Таким образом заметающая прямая выигрывает время у итеративного алгоритма в локализации, но проигрывает его в перестроениях (которые, напомню, довольно тяжелые). Ко всему прочему итеративный алгоритм работает в режиме онлайн, что также является его отличительной особенностью.
Здесь я просто покажу некоторые интересные триангуляции, получившиеся в результате работы алгоритма.
![]()
Нормальное распределение, 1000 точек
![]()
Равномерное распределение, 1000 точек
![]()
Триангуляция, построенная на местоположениях всех городов России
![]()
![]()
Спасибо за внимание!
[1] Скворцов А.В. Триангуляция Делоне и её применение. – Томск: Изд-во Том. ун-та, 2002. – 128 с. ISBN 5-7511-1501-5
![]()
практик е это т алгорит м работае т значительн о медленне е исходного .
![]()
триангуляции , применяемы х дл я работ ы с большим и наборам и исходны х
Линейный алгоритм <алгоритм линейного заметания плоскости)
можн о представит ь ка к частны й случа й двухпроходног о алгоритм а выпук -
лог о слияни я с одно й полосой . В данно м алгоритм е вначал е вс е исходны е
тельн о перебира я точк и сверх у вниз , он и соединяютс я в одн у невыпуклу ю
46,в) . И в заключени е производитс я полно е перестроени е триангуля -
Трудоемкост ь таког о алгоритм а составляе т в средне м O(N). Те м н е
мене е н а практик е это т алгорит м работае т существенн о медленне е полно -
В веерном алгоритме триангуляци и (алгоритме радиального заме-
тания плоскости) вначал е и з исходны х точе к выбираетс я та , котора я на -
ходитс я ка к можн о ближ е к центр у мас с все х точек . Дале е дл я остальны х
точе к вычисляетс я полярны й уго л относительн о выбранно й центрально й
точк и и вс е точк и сортируютс я п о этом у угл у (рис . 41,6). Зате м вс е точк и
соединяютс я рёбрам и с центрально й точко й и соседним и в отсортирован -
47,г) . И в заключени е производитс я полно е перестроени е триангуля -
Трудоемкост ь таког о алгоритм а составляе т в средне м O(N). Алго -
рит м работае т примерн о с то й ж е скоростью , чт о и предыдущи й - линей -
![]()
47 . Веерны й алгоритм : а - исходны е точки , б - кругова я
сортировка ; в - невыпукла я триангуляция ; г - достраивани е
Алгоритм рекурсивного расщепления работае т в дв а проход а [36] .
Второ й прохо д аналогиче н все м двухпроходны м алгоритма м триангуля -
ции , а первы й похо ж н а рекурсивны й алгорит м с разрезание м п о диаметру ,
н о разрезани е производитс я н е отрезком , а некоторо й ломаной .
Пере д начало м работ ы алгоритм а вычисляетс я выпукла я оболочк а
все х исходны х точек . Н а каждо м шаг е рекурси и дл я заданног о множеств а
точе к и и х оболочк и (н е обязательн о выпуклой ) выполняетс я делени е все х
точе к н а дв е части . Дл я этог о н а оболочк е находятс я противоположны е
, делящи е многоугольни к оболочк и примерн о попола м (рис .
стояни и Я , т.е . попадающи е в некоторы й коридо р расщеплени я (рис . 48,а) .
разбивае т исходно е множеств о точе к н а дв е части . Разделяюща я ломана я
лочк а невыпуклая , т о необходим о исключит ь случа и возможног о пересе -
чени я построенно й ломано й с оболочкой . Есл и полученны е множеств а н е
являютс я треугольниками , т о к ни м опят ь рекурсивн о применяетс я данны й
алгорит м (рис . 48, в) . Посл е построени я триангуляци и отдельны х часте й
выполняетс я и х соединени е вдол ь разделяюще й ломано й (рис . 48,г,д) .
48 . Алгорит м рекурсивног о расщепления : а - выбо р направлени я и
коридора ; б-г - шаг и расщепления ; д - перестроени е триангуляци и
![]()
Теоретическ и алгорит м рекурсивног о расщеплени я имее т трудоем -
цело м алгорит м работае т существенн о медленне е любы х двух -
49,в) . Посл е этог о полученна я триангуляци я достраиваетс я
В данно м алгоритм е используетс я процедур а слияния , соединяюща я
рёбр а будуще й триангуляции . Поэтом у наиболе е удобн о это т
Главны м параметро м данног о алгоритм а являетс я количеств о полос ,
![]()
Дл я дальнейшег о рассмотрени я введё м поняти я полилиния
Определение 12. Полилинией называетс я фигура , состояща я и з нену -
Определение 13. Регионом называетс я фигура , состояща я и з ненуле -
вог о числ а многоугольников , причё м допустим ы самопересечени я и пере -
сечени я различны х многоугольников . Пр и это м точк и плоскости , принад -
лежащи е к многоугольника м фигуры , считаютс я принадлежащим и регион у
тогд а и тольк о тогда , когд а к =l(mo d 2 ) (н а рис . 50, 6 регио н состои т и з
одног о самопересекающегос я пятиугольник а и внутреннег о треугольника) .
Таки е фигур ы н а практик е част о используютс я дл я представления ,
например , лини й с разрывам и и многоугольнико в с дыркам и внутри .
Определение 14. Задача построения триангуляции с ограничениями.
ни й и верши н регионо в построит ь триангуляци ю таки м образом , чтоб ы вс е
отрезк и полилини й и регионо в проходил и п о рёбра м триангуляции . Кром е
есл и множеств о регионо в н е пусто , т о дл я все х построенны х тре -
угольнико в необходим о установлени е факт а попадани я в заданны е регио -
н ы (пр и это м кажды й треугольни к може т попаст ь одновременн о в не -
![]()
Определение 15. В задач е построени я триангуляци и с ограничениям и
составляющи е ломаны е исходны х полилини й и границ ы исходны х регио -
Определение 16. Рёбр а триангуляци и с ограничениями , п о которы м
проходя т исходны е структурны е линии , называютс я структурными рёб-
В тако й постановк е задач а построени я триангуляци и наиболе е част о
используетс я пр и моделировани и рельеф а в геоинформационны х системах .
Задаваемы е точк и пр и это м определяю т точк и плоскости , в которы х изме -
рен ы высот ы н а поверхности , полилини и - проекци и н а плоскост ь струк -
турны х лини й рельефа , а регион ы - област и интересо в (рис . 51) .
В случае , когд а множеств а точе к и полилини й пусты , а задан ы толь -
к о регионы , получаетс я классическа я задач а построени я триангуляци и за -
Задач а построени я триангуляци и с ограничениями , та к ж е ка к и за -
дач а бе з ограничений , являетс я неоднозначной . Сред и различны х видо в
триангуляци и с ограничениям и выделяю т такж е тр и основны х вид а триан -
гуляции : оптимальную , жадну ю и триангуляци ю Делон е с ограничениями .
Определение 17. Триангуляци я с ограничениям и называетс я оптима-
льной, есл и сумм а дли н все х рёбе р минимальн а сред и все х возможны х три -
ангуляци и с ограничениями , построенны х н а те х ж е исходны х данных .
Задач а построени я оптимально й триангуляци и являетс я NP-полно й
[37,39] . Поэтом у н а практик е он а почт и н е применяется .
![]()
Обобща я рассмотренны й в гл . 1 жадны й алгоритм , получае м сле -
Жадный алгоритм построения триангуляции с ограничениями.
Шаг 1. В о множеств о исходны х точе к помещаютс я вс е вершин ы за -
данны х полилини й и регионов , а такж е генерируетс я списо к все х возмож -
ны х отрезков , соединяющи х пар ы исходны х точек , и о н сортируетс я п о
Шаг 2 . Выполняетс я вставк а отрезко в в триангуляци ю о т боле е ко -
ротки х д о длинных . Вначал е вставляютс я вс е отрезки , являющиес я частя -
м и исходны х полилини й и регионов , а зате м - остальны е отрезки . Есл и от -
резо к н е пересекаетс я с другими , ране е вставленным и отрезками , т о о н
вставляется , инач е о н отбрасывается . Конец алгоритма.
Заметим , чт о есл и вс е возможны е отрезк и имею т разну ю длину , т о
результа т работ ы этог о алгоритм а однозначен , инач е о н зависи т о т порядк а
Условие м правильно й работ ы жадног о алгоритм а являетс я отсутст -
ви е сред и исходны х полилини й и регионо в взаимны х пересечени й отрез -
Есл и таковы е имеются , т о о т ни х над о избавитьс я д о начал а работ ы
жадног о алгоритм а разбиение м эти х отрезко в н а части .
Определение 18. Триангуляци я с ограничениям и называетс я жадной,
Трудоемкост ь работ ы жадног о алгоритм а пр и некоторы х ег о улуч -
удалени я пересекающихс я отрезков . Пр и учет е предварительног о этап а
трудоемкость ю н а практик е тако й алгорит м применяетс я редко .
Определение 19. Триангуляци я заданног о набор а точе к буде т назы -
ватьс я триангуляцией Делоне с ограничениями, есл и услови е Делон е вы -
полняетс я дл я любо й пар ы смежны х треугольников , которы е н е разделя -
Дл я построени я триангуляци и Делон е с ограничениям и могу т быт ь
обобщен ы некоторы е и з приведенны х выш е алгоритмов . Наиболе е хорош о
дл я таког о обобщени я подходя т итеративны е алгоритм ы триангуляции .
Алгоритм ы триангуляци и слияние м н е подходят , та к ка к н е всегд а
возможн о делени е множеств а исходны х объекто в н а непересекающиес я
част и (например , когд а ест ь большо й регион , охватывающи й вс е осталь -
![]()
Алгоритм ы прямог о построени я триангуляци и подходя т больше , н о
в ни х необходим о добавит ь в процедур у поиск а очередног о сосед а Делон е
Большинств о эффективны х двухпроходны х алгоритмо в построени я
триангуляци и в данно м случа е использоват ь нельзя , та к ка к он и либ о яв -
ляютс я неприменимым и алгоритмам и слияния , либ о строя т огромно е ко -
личеств о узки х вытянуты х треугольников , которы е почт и всегд а пере -
страиваются , а поэтом у и х применени е неэффективно .
Дл я триангуляци и с ограничениям и наиболе е удобн о использоват ь
структур ы данных , представляющи х в явно м вид е рёбра , та к ка к дл я рёбе р
необходим о хранит ь дополнительну ю информаци ю о том , являютс я л и он и
межд у расходо м памят и и удобство м применения . Дополнительны м е ё
достоинство м являетс я возможност ь простог о эволюционног о переход а к
не й о т итеративног о алгоритм а триангуляци и Делон е бе з ограничений , ис -
Оди н и з первы х эффективны х алгоритмо в построени я триангуляци и
с ограничениям и основа н н а процедур е регуляризаци и планарног о граф а и
триангуляци и монотонны х многоугольнико в [12] . Трудоемкост ь этог о ал -
Исходным и данным и дл я цепног о алгоритм а являетс я множеств о не -
пересекающихс я отрезко в н а плоскости , п о сут и образующи х планарны й
Есл и в триангуляци ю необходим о поместит ь такж е отдельны е точки ,
т о и х следуе т добавит ь уж е посл е работ ы данног о алгоритма , наприме р
Цепной алгоритм построения триангуляции с ограничениями.
Шаг 1. И з множеств а исходны х структурны х отрезко в формируе м
Шаг 2. Выполняетс я регуляризация графа, т.е . добавляютс я новы е
рёбра , н е пересекающи е другие , та к чт о кажда я вершин а граф а становитс я
смежно й хот я б ы с одно й вершино й выш е не ё и одно й ниже . Регуляриза -
ци я выполняетс я в дв а проход а с помощь ю вертикальног о плоског о заме -
тани я [12] . В перво м проход е сниз у ввер х последовательн о находятс я вс е
вершины , и з которы х н е выходя т рёбра , ведущи е вверх . Например , н а рис .
52,6 тако й являетс я вершин а В. Провод я горизонтальну ю линию , обнару -
живае м ближайши е пересекаемы е е ю слев а и справ а рёбр а граф а AD и EF.
![]()
води м в не ё ребр о и з В. Аналогичн о выполняетс я второ й прохо д сверх у
вни з (рис . 52,в) . В результат е работ ы этог о шаг а кажда я област ь планарно -
г о граф а становитс я монотонны м многоугольником .
Шаг 3. Кажду ю област ь граф а необходим о разбит ь н а треугольники .
Дл я этог о можн о воспользоватьс я алгоритмо м невыпуклог о слияни я дву х
52 . Схем а работ ы цепног о алгоритм а триангуляции :
а - исходны е отрезки ; б - прохо д сниз у ввер х регуляризаци и графа ;
в - прохо д сверх у вниз ; г - триангуляци я монотонны х многоугольнико в
Дл я реализаци и цепног о алгоритм а триангуляци и с ограничениям и
лучш е всег о использоват ь структур ы данных , в которы х рёбр а представ -
Недостатко м цепног о алгоритм а являетс я то , чт о о форм е получае -
мо й триангуляци и ничег о заране е сказат ь нельзя . Эт о н е оптимальна я три -
ангуляция , н е жадна я и н е триангуляци я Делон е с ограничениями . В цеп -
но м алгоритм е могу т получатьс я очен ь длинны е вытянуты е треугольники .
Дл я улучшени я качеств а полученно й триангуляци и можн о проверит ь
вс е пар ы смежны х треугольников , н е разделенны х структурны м ребром ,
н а выполнени е услови я Делон е и пр и необходимост и произвест и пере -
строения . В результат е буде т получен а триангуляци я Делон е с ограниче -
З а основ у итеративног о алгоритм а построени я триангуляци и Делон е
с ограничения м може т быт ь взя т любо й итеративны й алгорит м построени я
обычно й триангуляци и Делоне , н о наиболе е удобн о здес ь использоват ь ал -
Читайте также:
