АЛГОРИТМЫ ПОСТРОЕНИЯ ТРЕХМЕРНОЙ МОДЕЛИ ИЗОБРАЖЕНИЯ

Введение

Триангуляция – планарное разбиение плоскости на множество фигур, из которых одна является внешней бесконечной, а остальные – треугольниками [1, с. 15].

В середине 19 века появление технологии фотографии позволило производить триангуляцию с помощью определения формы, размеров, положения и иных характеристик объектов по их фотоизображениям. Такой способ называется фотограмметрия. Она находит применение в различных видах деятельности и одна из них это автоматизированное построение пространственных моделей объекта по снимкам [2].

В статье рассматривается построение трехмерной модели по изображениям.

Термины

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

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

В триангуляции Делоне выявляются следующие свойства:

• максимизация минимального угла среди всех построенных треугольников, вследствие чего избегаются «тонкие» треугольники;
• максимизация суммы радиусов вписанных окружностей;
• минимизация суммы радиусов окружностей, описанных около треугольников, среди всех возможных триангуляций [3].

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

Оптимальная триангуляция – это такая триангуляция, в которой сумма ребер минимальна.

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

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

1. «Разделяй и властвуй».

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

• если количество точек равно 3, то нужно построить триангуляцию из одного треугольника (см. рис. 1а);
• если количество точек равняется 4, то построить триангуляцию из двух или трех треугольников в зависимости от расположения точек (см. рис. 1б).

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

Рисунок 1. Триангуляция множеств из трех и четырех точек

В среднем и худшем случаях трудоемкость составляет , где  – количество точек.

Слияние триангуляции одна из сложных и основных пунктов данного алгоритма. Для их слияния используются специальные процедуры, одна из которых – процедура «Строй-и-перестраивай».

Для начала необходимо построить треугольники, которые заполняют зону слияния, между  касательными (см. рис.2а). Чтобы построить их нужно сделать следующее: касательная  будет текущей базовой линией  и относительно нее рассматриваются точки  и  вдоль границ сливаемых триангуляций. Далее имеются два треугольника  и  из них нужно выбрать тот, который можно построить и у которого максимум минимального угла больше. Открытая сторона построенного треугольника будет новой базовой линией (см. рис 2б). И так цикл продолжается до тех пор, пока касательная  не будет достигнута [1, с. 30].

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

Рисунок 2. Слияние триангуляций

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

2. Невыпуклое полосовое слияние.

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

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

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

Рисунок 3. Триангуляция полосы точек

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

3. На данном этапе анализируется выпуклость границы. Определяется первая точка , начиная с той, где нарушается выпуклость (точка ), и запоминается следующая за ней точка . Перед анализом проводится проверка, чтобы выяснить какой треугольник строить. Если  выше , то достраивается выпуклая оболочка на границе от  до  или от  до . и ищутся следующие точки  и , если они существуют (см. рис. 4) [1, с. 33].

Рисунок 4. Алгоритм невыпуклого полосового слияния

Проверка условия Делоне

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

1. проверка через уравнение описанной окружности;
2. проверка с заранее вычисленной описанной окружностью;
3. проверка суммы противолежащих углов;
4. модифицированная проверка суммы противолежащих углов.

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

, где

, , , .

Условие Делоне для данного треугольника и другой точки  выполняется, когда выполняется неравенство [1]:

.

Если тройка вершин треугольника является правой, то , иначе, если тройка левая, то  [1, c. 20].

Заключение

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

Список литературы:

1. Скворцов А.В. Триангуляция Делоне и ее применение/А.В. Скворцов. – Томск: Изд-во Том. ун-та, 2002. – 128с.
2. Фотограмметрия. [Электронный ресурс] — URL: https://ru.wikipedia.org/wiki/Фотограмметрия (дата обращения 12.04.2018)
3. Триангуляция Делоне. [Электронный ресурс] — URL: https://ru.wikipedia.org/wiki/Триангуляция_Делоне (дата обращения 12.04.2018)