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

Топологический критерий основан на ближайших соседях точки из множества. В идеальном случае точка имеет для двумерной области 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. Схема работы цепного алгоритма триангуляции: а) - исходные отрезки; б - проход снизу вверх регуляризации графа; в) - проход сверху вниз; г) - триангуляция монотонных многоугольников

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

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

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

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

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

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

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

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

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

Рис. 9.7.1. Выпуклая область с заданными точками внутри

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

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

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

Рис. 9.7.2. Выбор третьей точки алгоритма Делоне

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

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

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

Через вершины А, В и любую, не лежащую с ними на одной прямой, вершину можно провести окружность. В качестве третьей вершины треугольника выберем вершину V, соответствующая которой окружность, не содержит других вершин с той же стороны относительно отрезка АВ, с которой лежит точка V. Для граничного ребра в общем случае можно найти одну такую вершину. Будем называть ее ближайшей. Центр окружности, проходящей через точки А, В и V, лежит на пересечении перпендикуляров к серединам отрезков АВ, BV и VА. Положение центра окружности будем характеризовать параметром t отрезка MN, перпендикулярного ребру АВ, равного с ним по длине и проходящего через середину ребра АВ.

Рис. 9.7.3. Процесс триангуляции Делоне

Для всех вершин, лежащих слева от отрезка АВ, ближайшая вершина имеет наименьший параметр t. Соответствующая ближайшей вершине окружность не содержит других вершин слева от отрезка АВ. Пусть вершины А, В и V описываются двухмерными радиус-векторами соответственно. Радиус-векторы середин отрезков АВ и BV будут равны

Значение параметра t прямой , соответствующее положению на ней центра окружности, проходящей через точки А, В и V, равно

Для ближайшей слева к отрезку АВ вершины параметр t имеет минимальное значение.

Сориентируем все граничные ребра так, чтобы подлежащая триангуляции область лежала слева от каждого из них. Построение треугольников начнем с любого граничного ребра. Найдем для него ближайшую вершину, соответствующая окружность которой не содержит других вершин. Пусть для граничного ребра АВ найдена ближайшая вершина V. Тогда построим треугольник ABV и переведем ребро АВ в разряд неактивных. Неактивными будем называть ребра и вершины, которые не участвуют в алгоритме триангуляции. Если среди граничных ребер отсутствует ребро BV, то на отрезке VB построим новое граничное ребро. Если же среди граничных ребер есть ребро BV, то переведем его и вершину В в разряд неактивных. Если среди граничных ребер отсутствует ребро VA, то на отрезке AV построим новое граничное ребро. Если же среди граничных ребер есть ребро VA, то переведем его и вершину А в разряд неактивных. Процесс триангуляции показан на рис. 9.7.3.

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

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

Триангуляция методом коррекции.

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

Параметрические расстояния между соседними линиями в соответствии с формулой (9.4.8) возьмем равными

Построив диагонали во всех прямоугольных ячейках, мы получим триангуляцию поверхности (получим набор треугольников, удовлетворяющий предъявленным требованиям). На рис. 9.7.5 приведена триангуляция поверхности вращения описанным способом.

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

Рис. 9.7.5. Триангуляция поверхности с прямоугольной областью определения параметров

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

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

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

Рис. 9.7.6. Незаконченная триангуляция поверхности

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

На непересеченных сторонах ячеек второй группы построим граничные ребра и направим их так, чтобы соответствующая ячейка находилась слева от ребра. Вокруг ячеек первой группы построим замкнутую ломаную линию (возможно несколько замкнутых линий) так, чтобы при движении по ней не разбитая на треугольники часть области лежала слева, если смотреть навстречу нормали поверхности. Прямолинейные участки этой ломаной линии также будем использовать в качестве граничных ребер. Мы будем считать все ребра равноправными. Для завершения триангуляции нам необходимо построить треугольники между граничными ребрами. Для каждого ребра будем искать вершину, которая лежит слева от него и может быть использована для построения треугольника. Поиск вершины будем осуществлять только среди тех вершин, которые лежат в одной ячейке с ребром. Для выбора вершины используем метод Делоне, описанный выше, и проиллюстрированный на рис. 9.7.2. Если такая вершина найдена, то следует проверить, не пересекаются ли два новых ребра треугольника с каким-либо граничным ребром. Пусть для граничного ребра АВ найдена ближайшая вершина V и проверено, что отрезки BV и VА не пересекают другие граничные ребра. Тогда построим треугольник ABV и переведем ребро АВ в разряд неактивных. Если среди граничных ребер отсутствует ребро BV, то на отрезке VВ построим новое граничное ребро, если же среди граничных ребер есть ребро BV, то переведем его и вершину В в разряд неактивных. Если среди граничных ребер отсутствует ребро VA, то на отрезке AV построим новое граничное ребро, если же среди граничных ребер есть ребро VA, то переведем его и вершину А в разряд неактивных.

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

Рис. 9.7.7. Триангуляция методом коррекции

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

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

Триангуляция методом поглощения.

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

Для этого вычислим допустимые приращения параметров вдоль координатных линий

где - коэффициенты первой и второй квадратичных форм поверхности в точке . За границу искомой области примем эллипс с центром в точке и полуосями . Этот эллипс имеет уравнение

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

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

Найдем в рабочем полигоне вершину, в которой он поворачивает внутрь области. Такая точка всегда существует и угол поворота в ней меньше . Обозначим эту точку через О, а ее параметры - через Около этой точки построим один или два треугольника в зависимости от угла поворота. Если угол меньше то построим один треугольник на этих трех точках (рис. 9.7.9). В противном случае построим два треугольника на данной, двух соседних и одной новой точках (рис. 9.7.11). Новая точка обозначена через Р. Точку Р будем искать на диагонали параллелограмма В ОС Р. Если вершина параллелограмма лежит внутри эллипса (рис. 9.7.10), то примем ее за точку Р. В противном случае за точку Р примем пересечение эллипса и диагонали параллелограмма. В последнем случае совсем не обязательно искать пересечение эллипса и отрезка.

Координаты точки Р определяются через координаты точек О ВС

Угол отрезка ОР с горизонталью определяется равенством

(9.7.8)

Эти данные позволяют определить положение точки Р относительно эллипса (9.7.5).

В случае, показанном на рис. 9.7.9, построим треугольник (запомним номера его вершин) и в рабочем полигоне удалим точку О. В случае, показанном на рис. 9.7.11, построим два треугольника и в рабочем полигоне точку О заменим точкой Р и поместим последнюю в результирующий массив точек. На рис. 9.7.12 приведен полигон, полученный после построения двух треугольников и ликвидации точки О. В обоих случаях точка О будет удалена из рабочего полигона и рабочий полигон сузится. Заметим, что треугольники можно строить только тогда, когда рабочий полигон после сужения не будет сам себя пересекать.

Рис. 9.7.9. Построение треугольника

Рис. 9.7.10. Результирующий полигон

Рис. 9.7.11. Построение двух треугольников

Рис. 9.7.12. Результирующий полигон

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

Более того, при определении положения точки Р важно, чтобы она находилась на достаточном расстоянии от других точек рабочего полигона и не подходила близко к отрезкам, соединяющим точки полигона. Иначе могут возникнуть трудности в дальнейшем при построении треугольников. Поэтому прежде, чем сузить рабочий полигон, следует проверить на самопересечение результирующий полигон. Если около точки О нельзя построить треугольник (треугольники), то вместо нее следует найти другую точку, в которой полигон более, чем в других, заворачивает внутрь контура, и выполнить в ней описанные действия.

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

Рис. 9.7.13. В данном углу строить треугольники нельзя

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

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

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

Пусть мы проверяем возможность построения двух треугольников в точке О (рис. 9.7.11), и обнаружили, что новая точка Р, будучи построенной, попадет внутрь одного из внутренних полигонов или окажется в недопустимой близости от его отрезков. В этом случае мы не будем строить точку Р, а вместо этого включим в рабочий полигон данный внутренний полигон, построив два треугольника, показанных на рис. 9.7.14.

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

Построим треугольники на точках OCF и CEF и между точками О и С рабочего полигона вставим точки внутреннего полигона, начиная с точки F и кончая точкой Е. Тем самым мы разорвем рабочий полигон на отрезке ОС, разорвем внутренний полигон на отрезке EF и объединим их отрезками OF и ЕС.

Рис. 9.7.14. Построение двух треугольников

Рис. 9.7.15. Слияние внешнего и внутреннего полигонов

Результат слияния приведен на рис. 9.7.15. Конечно, перед объединением внешнего и внутреннего полигонов должны быть выполнены проверки на корректность этой операции.

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

Рис. 9.7.16. В данном углу строить треугольники нельзя

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

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

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

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

Триангуляция тела представляет собой совокупность треугольников, полученных путем триангуляции поверхностей его граней. Триангуляция отдельных поверхностей отличается от триангуляции граней тела тем, что в последнем случае должны быть согласованы граничные полигоны для смежных граней (рис. 9.7.17).

Рис. 9.7.17. Согласованность граничных полигонов граней тела

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

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

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

Рис. 9.7.18. Триангуляция грани тела методом коррекции

Разбиение области определения параметров поверхности на треугольники может быть использовано в интегралах (8.6.2), (8.6.3), (8.6.12), (8.7.17)-(8.7.22) при вычислении геометрических характеристик тел. При численном интегрировании параметрический шаг для кривых следует вычислять по формуле (8.11.5), а для поверхностей параметрические шаги следует вычислять по формулам (8.11.1) и (8.11.2).

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

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

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

На входе

Рисунок 1

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

Поиски

Алгоритм

Рисунок 2

Рисунок 3

Рисунок 4

Еще одно но: при сохранении очередного треугольника необходимо записывать вершины в обходе по часовой стрелке (в правой системе координат). Это пригодится в дальнейшем для уменьшения вычислительных ресурсов.

2) Повторяем шаг 1 пока не заметаем всю плоскость.

3) Если последовательностей несколько, т.е. одна, а внутри её еще одна или более внутренних контуров (Рисунок 1). Тут необходимо рассмотреть каждую последовательность отдельно. Возьмем очередной внутренний контур. Из одного внешнего и одного внутреннего сделаем два одиночных контура. Для этого нужно найти два «порта» из одного контура в другой. Условие для «портов»: они не должны пересекаться между собой(не должны соприкасаться даже концами), не должны пересекаться с линиями контуров (Рисунок 5).

Рисунок 5

Рисунок 6
4) Далее следует ввести поочередно все внутренние последовательности в уже образованные, отделенные друг от друга (пункт 3) последовательности. Сливать нужно с той, которая содержит новую. По определению ни одна внутренняя последовательность не касается и не пересекается с другими(как одной внешней, так и всеми возможными внутренними), так что все пройдет гладко.
Найдя порты (Рисунок 6) легко построить новые последовательности и обойти их пунктами 1 и 2 текущего алгоритма (Рисунок 7).

Рисунок 7

5) После 4-его этапа имеем список треугольников(Рисунок 8). Как бы с задачей уже справились, но осталось сделать картинку красивой: проверить выполнение условия Делоне (Рисунок 9).

Рисунок 8

Рисунок 9

6) Забегая вперед расскажу про шестой пункт. Он заключается в последовательном прогоне по списку полученных треугольников пунктом №5. Сначала метим все треугольники «грязными». В каждом цикле проверяем для каждого треугольника условие Делоне. Если условие не выполняется, то делаем перестроение и помечаем соседей и текущий треугольник «грязными». Если условие выполняется, то метим его чистым. В моей реализации алгоритма, каждый треугольник имеет ссылку на соседей. В этом случае 6-ой пункт работает наиболее быстро.

Подробнее о пятом этапе

Мощность вычислений №1: 10 операций умножения/деления и 13 операций сложения/вычитания.
Мощность вычислений №2: 29 операций умножения/деления и 24 операций сложения/вычитания.

С точки зрения вычислительной мощности, которая высчитывается к примеру в книге , выгоднее вариант №1. Его и реализовал, если бы не… (Рисунок 10). Как оказалось после постановки данного метода на «конвейер», получилась неопределенность. Это вариант, когда сам угол А больше 180 градусов. Он рассматривается в книге как один из отдельных частных методов. А с этим пропадает вся его элегантность, прозрачность и производительность. А так же в последствии оказалось, что метод №2 можно очень существенно оптимизировать.

Рисунок 10

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

Итак имеем:
Проверка условия для точки M(X, Y) уравнением окружности, проходящей через точки A(x1, y1), B(x2, y2), C(x3, y3), можно записать в виде:

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ sign a ≥ 0

Подробности можно взять в великолепной книге . (Нет, не я ее автор)
Итак, sign a - это знак направления обхода, с самого начала я строил треугольники по часовой стрелке, так что его можно опустить (он равен единице).

A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);

D >= 0

Рисунок 11

Просто не правда ли?

Согласно книге, опять же,

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)*(y1*x2 - x1*y2) <= 0

Имеем: 15 операций умножения/деления и 14 операций сложения/вычитания.

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

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

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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Xmin ← M

for i ← 1 to lenght(M) – 1

If Xmin › M[i]

Xmin ← M[i]

Xmax ← M

for i ← 1 to lenght(M) – 1

If Xmax < M[i]

Xmax ← M[i]

Ymin ← M

for i ← 1 to lenght(M) – 1

If Ymin › M[i]

Ymin ← M[i]

Ymax ← M

for i ← 1 to lenght(M) – 1

If Ymax < M[i]

Ymax ← M[i]

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

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

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

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

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

for points to points

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

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

Point.angle ← 0

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

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

Foundation ← |point.x – Xc|

Point.angle ← arctg(perpendicular/foundation)

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

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

Point.angle ← p/2

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

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

Foundation ← |point.y – Yc|

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

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

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

Point.angle ← p

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

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

Foundation ← |point.x – Xc|

Perpendicular ← |point.y – Yc|

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

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

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

Point.angle ← 3p/2

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

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

Foundation ← |point.y – Yc|

Perpendicular ← |point.x – Xc|

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

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

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

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

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

for i ← 0 to length(Points) – 1

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

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

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

Graham(Q)

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

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

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

Push(p 0 ,S)

Push(p 1 ,S)

for i=2 to N do

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

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

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

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

Do Pop(S)

Push(pi,S)

return S

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

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

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

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

T(n) = O(NlnN)

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

Выводы

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

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

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

The modified Delaunay’s triangulation algorithm

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

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

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

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

Вконтакте