12

Лекция №21

Оглавление

9.8. Алгоритмы Делоне 1

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

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

9.9. Алгоритм Рапперта и его модификации. 10

9.9.1.Терминология и алгоритм. 10

9.9.2. Модификация алгоритма Рапперта 13

9.9.3. Алгоритм построения первичного разбиения. 21

9.8. Алгоритмы Делоне

Общие замечания

Триангуляция для конечного набора точек S является задачей триангуляции выпуклой оболочки CH(S), охватывающей все точки набора S.

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

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

Для данного набора точек 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: Две ситуации, возникающие при триангуляции после добавления новой внутренней точки

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

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

Она применяется во многих ГИС системах для построения моделей рельефа.

Делоне Борис Николаевич (1890-1980) - российский математик, член-корреспондент АН СССР (1929). Труды по геометрии, теории чисел, математической кристаллографии.

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

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

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

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

На рис. 4-Д показан пример триангуляции Делоне для набора большого числа точек.

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

К триангуляции Делоне (к сетке, удовлетворяющей критерию Делоне) можно отнести несколько свойств, в частности:

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

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

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

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

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

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

Базовый алгоритм

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

Алгоритм содержит следующие операции:

выбор произвольной начальной точки;

поиск второй ближайшей точки, соединяющий точки отрезок является

исходной базой для дальнейших построений;

поиск в левой полуплоскости от базового отрезка точки, из которой

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

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

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

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

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

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

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

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

спящие ребра: ребро триангуляции Делоне является спящим, если она еще не было обнаружено алгоритмом;

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

мертвые ребра: ребро считается мертвым, если оно обнаружено и известны обе примыкающие к нему области.

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

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

Этот алгоритм для вычисления триангуляции Делоне по набору из n точек выполняется за время О(n²), поскольку при каждой итерации из границы исключается одно ребро. Поскольку каждое ребро исключается из границы только однажды — каждое ребро относится к границе однажды и затем исключается из нее, никогда не возвращаясь — число итераций равно числу ребер в триангуляции Делоне. Согласно теореме о триангуляции набор точек любая триангуляция содержит не более, чем О(n) ребер, поэтому алгоритм выполняет О(n) итераций. Поскольку на каждую итерацию тратится время О(n), то полностью алгоритм выполняется за время О(n²).

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

Недостатки алгоритма:

алгоритм использует постоянно вычисляемые тригонометрические

функции, что резко замедляет процесс;