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

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

Геометрический критерий основан на разнице вписанной и описанной окружности вокруг расчетного треугольного элемента. Геометрическую оценку получим с помощью формулы (2), где - количество треугольников, - радиус вписанной окружности, - радиус описанной окружности.

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

Для построения триангуляции существует большое количество алгоритмов. Они различаются между собой трудоёмкостью, сложностью реализации на ЭВМ, подходами к построению. Подробнее об алгоритмах можно узнать в книге А.В. Скворцова . Рассмотрим некоторые алгоритмы.

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

Шаг 1. Генерируется список всех возможных отрезков, соединяющих пары исходных точек, и он сортируется по длинам отрезков.

Шаг 2. Начиная с самого короткого, последовательно выполняется вставка отрезков в триангуляцию. Если отрезок не пересекается с другими ранее вставленными отрезками, то он вставляется, иначе он отбрасывается.

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

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

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

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

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

Шаг 4. Если точка попала на ранее вставленный узел триангуляции, то такая точка обычно отбрасывается, иначе точка вставляется в триангуляцию в виде нового узла. При этом если точка попала на некоторое ребро, то оно разбивается на два новых, а оба смежных с ребром треугольника также делятся на два меньших. Если точка попала строго внутрь какого-нибудь треугольника, он разбивается на три новых. Если точка попала вне триангуляции, то строится один или более треугольников.

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

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

Цепной алгоритм один из первых эффективных алгоритмов построения триангуляции основан на процедуре регуляризации планарного графа и триангуляции монотонных многоугольников . Трудоемкость этого алгоритма составляет, где - количество исходных отрезков. Рассмотрим алгоритм по шагам:

Шаг 1. Из множества исходных структурных отрезков формируем связанный планарный граф (Рисунок 4,а).

Шаг 2. Выполняется регуляризация графа, т.е. добавляются новые рёбра, не пересекающие другие, так что каждая вершина графа становится смежной хотя бы с одной вершиной выше неё и одной ниже. Регуляризация выполняется в два прохода с помощью вертикального плоского заметания . В первом проходе снизу вверх последовательно находятся все вершины, из которых не выходят рёбра, ведущие вверх. Например, на (Рисунок 4,б) такой является вершина B. Проводя горизонтальную линию, обнаруживаем ближайшие пересекаемые ею слева и справа рёбра графа AD и EF. Затем в четырехугольнике DEHG находим самую низкую вершину и проводим в неё ребро из B. Аналогично выполняется второй проход сверху вниз (Рисунок 4,в). В результате работы этого шага каждая область планарного графа становится монотонным многоугольником.

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

Рисунок 4. Схема работы цепного алгоритма триангуляции: а) - исходные отрезки; б - проход снизу вверх регуляризации графа; в) - проход сверху вниз; г) - триангуляция монотонных многоугольников

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Триангуляция для конечного набора точек 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; }

Основные определения и свойства

Триангуляцией называется планарный граф, все внутренние области которого являются треугольниками.

Свойства:

· Триангуляция Делоне взаимно однозначно соответствует диаграмме Вороного для того же набора точек.

· Как следствие: если никакие четыре точки не лежат на одной окружности, триангуляция Делоне единственна.

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

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

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

· Триангуляция Делоне минимизирует максимальный радиус минимального объемлющего шара.

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

Рис 1. Триангуляция.

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

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

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

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

Рис 2. Триангуляция Делоне.

Метод пустого шара Делоне. Построение в общем случае

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

Итак, поместим в систему точек {А} пустой шар Делоне. Это всегда возможно, если выбрать шар достаточно малым. Начнем увеличивать его радиус, оставляя центр шара на месте. В какой-то момент поверхность шара встретит некоторую точку i системы {А}. Это обязательно произойдет, ибо в нашей системе нет неограниченно больших пустот. Будем продолжать увеличивать радиус пустого шара так, чтобы точка i оставалась на его поверхности. Для этого придется двигать центр шара от точки i. Рано или поздно шар достигнет своей поверхностью другой точки системы {А}.

Рис.3

Симплексы Делоне заполняют пространство без щелей и наложений.

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

Пусть это будет точка j. Продолжим увеличивать радиус нашего шара, сохраняя уже обе точки на его поверхности. Увеличиваясь, шар достигнет какой-то третьей точки системы, точки k. В двумерном случае наш "пустой круг" в этот момент зафиксируется, т.е. станет невозможным дальнейшее увеличение его радиуса при сохранении круга пустым. При этом мы выявляем элементарную двумерную конфигурацию трех точек (i,j,k), определяющую некий треугольник, особенностью которого является то, что внутри его описанной окружности нет других точек системы {А}. В трехмерном пространстве шар не определяется тремя точками. Продолжим увеличивать его радиус, сохраняя все три найденные точки на его поверхности. Это будет возможно до тех пор, пока поверхность шара не встретится с четвертой точкой l системы. После этого движение и рост пустого шара станут невозможными. Найденные четыре точки (i,j,k,l) определяют вершины тетраэдра, который характерен тем, что внутри его описанной сферы нет других точек системы {А}. Такой тетраэдр называется симплексом Делоне.

Симплексом в математике называют простейшую фигуру в пространстве данной размерности: тетраэдр - в трехмерном пространстве; треугольник - в двумерном. Произвольная тройка (четверка) точек системы, не лежащих в одной плоскости, всегда определяет некий симплекс. Однако он будет симплексом Делоне только с том случае, если его описанная сфера пуста. Другими словами, симплексы Делоне определяются особым выбором троек (четверок) точек в системе {А}.

Мы построили один симплекс Делоне, однако, помещая пустой шар в различные места и повторяя ту же процедуру, можно определить и другие. Утверждается, что совокупность всех симплексов Делоне системы {А} заполняет пространство без наложений и щелей, т.е. реализует разбиение пространства, но на этот раз на тетраэдры. Это разбиение называется разбиением Делоне (рис.3).

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

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

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

Еще одной часто возникающей в геоинформатике задачей является построение экспозиций склонов. Здесь требуется определить доминирующие направления склонов по странам света и разбить поверхность на регионы, в которых доминирует некоторое определенное направление. Так как для горизонтальных участков поверхности определение экспозиции не имеет смысла, то в отдельный регион выделяют области, являющиеся горизонтальными или имеющие незначительный уклон, например б<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.

Рис.4.

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

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

GRID- модели – модели регулярных ячеек.

Пусть введена система координат
ии
. Пользователь задает
и шаги дискретизации
.

,

- физические координаты точки.

Вычисляем
и
,
- разрядная сетка.

- квантованные значения. Реальные:

- параметр алгоритма – количество точек, - вес. Чем ближе точка, тем больше вес.

- степень расстояния (1 или 2).

Нормировочный коэффициент:

Чем ближе к 1, тем больше учитываются точки с большим весом.

Это метод IDW – долгий, для каждой т. необходимо найти соседей. Набор соседей может быть эффективно найден - ближайшим. Каждая из точек продуцирует «колышек» определенной высоты. От нерегулярности постановок точки многое зависит, для этого берут
или
т.е. разделяют на сектора и в окрестности точки строим.

Преимущество – простота

Недостаток:

------Билет 14. Tin-модель. Алгоритмы триангуляции Делоне------

1) Триангуляционные (tin).

Триангуляция – построение функции в виде совокупности кусочно - линейной функции

Триангуляция – интерполяция внутри выпуклой области.

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

Нужен алгоритм для построения оптимальной триангуляции.

Плоскость, проходящая через 3 точки.

1) Найдем треугольник, который
;

2)
- строим уравнение плоскости.

Чтобы проверить находятся ли точки внутри треугольника или нет, необходимо подставить значение в уравнение линий – ребер треугольника. Если все 3 уравнения > 0, то внутри.

Структура представления:

Каждая триангуляция содержит одинаковое количество треугольников.

, где – количество внутренних точек,
– количество точек.

Жадный триангуляция.

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

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

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

Флипом называется переброска ребер. Она позволяет перейти от обычной триангуляции к триангуляции Делоне. Чтобы проверить принадлежность точки к окружности: подставить, если < R, то внутри.

Условие Делоне.

Уравнение окружности, проходящей через три точки:

Если меньше нуля, то внешняя, иначе – внутренняя.

–условие Делоне.

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

1) Подследственного добавления точек – простой итеративный алгоритм:

Есть набор
добавляем в треугольник, осуществляется построение
разбиение треугольника
перестроение. На нулевом этапе добавляем 3-4 фиктивные точки, которые заведомо покрывают наш конверт, все точки внутри. После кидаем точку, смотрим в какой треугольник попала, разбиваем на 3, для каждого треугольника проверяем условие Делоне и осуществляем флип переброску ребер. Среднее количество перестроений равно трем.

Теоретическая сложность

2) Методы ускорения. Основан на статистически зависимых точках. Затравочный треугольник – треугольник в который попала предыдущая точка. Затем соединяем две точки – предыдущую и новую.

Перемещаемся из первой точки в другую.