Бесплатный автореферат и диссертация по наукам о земле на тему

Исследование и разработка высокопроизводительного алгоритма построения цифровых моделей рельефа

ВАК РФ 25.00.35, Геоинформатика

Автореферат диссертации по теме "Исследование и разработка высокопроизводительного алгоритма построения цифровых моделей рельефа"

Б

005001863

НГУЕН ТХЕ КОНГ

ИССЛЕДОВАНИЕ И РАЗРАБОТКА ВЫСОКОПРОИЗВОДИТЕЛЬНОГО АЛГОРИТМА ПОСТРОЕНИЯ ЦИФРОВЫХ МОДЕЛЕЙ РЕЛЬЕФА

Специальность: 25.00.35 - "Геоинформатика"

Автореферат

диссертации на соискание учёной степени кандидата технических наук

2 4 НОЯ 2011

Москва-2011

005001863

Диссертация выполнена на кафедре Информационно-измерительных систем Московского государственного университета геодезии и картографии

(МИИГАиК)

Научный руководитель:

доктор технических наук, профессор Майоров Андрей Александрович

Официальные оппоненты:

доктор технических наук, профессор Цветков Виктор Яковлевич, кандидат технических наук Матвеев Александр Станиславович

Ведущая организация:

ФГУП "Госцентр "Природа"

Защита состоится « 15 » декабря 2011 г. в Ш часов на заседании диссертационного совета Д.212.143.03 в Московском государственном университете геодезии и картографии (МИИГАиК) по адресу: 105064 Москва, Гороховский пер., 4, зал заседания Ученого совета.

С диссертацией можно ознакомиться в библиотеке Московского государственного университета геодезии и картографии (МИИГАиК).

Автореферат разослан « М » ноября 2011 г. Ученый секретарь

диссертационного совета УоИлцллА-----Климков Ю.М.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

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

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

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

1. Обзор и анализ методов представления и применения ЦМР.

2. Исследование алгоритмов инкремента и заметающей линии для построения триангуляции Делоне.

3. Предложение методов повышения скорости вычисления для алгоритмов инкремента и заметающей линии.

4. Разработка эффективного алгоритма построения триангуляции Делоне на основе комбинации алгоритмов инкремента и заметающей линии.

5. Исследование алгоритмов анализа поверхностей.

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

Научная новизна работы.

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

Предложены методы повышения скорости вычисления для алгоритмов инкремента и заметающей линии.

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

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

1. Методы повышения скорости вычисления алгоритмов инкремента и заметающей линии.

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

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

Вклад автора в проведенное исследование.

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

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

Изложенные в диссертации материалы научных исследований докладывались и обсуждались на 65-ой научно-технической конференции студентов, аспирантов и молодых ученых МИИГАиК (апрель 2010 г.). Структура и объем диссертации.

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

По материалам диссертации опубликовано 4 работы, две из которых в журнале, включенном в перечень ВАК.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе "Обобщение цифровых моделей рельефа" представлены понятия о цифровой модели рельефа, методы представлений и применений цифровых моделей рельефа.

Во второй главе "Анализ алгоритмов построения цифровых моделей рельефа" представлены и проанализированы известные алгоритмы построения триангуляции Делоне.

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

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

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

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

Шаг 1. Построение выпуклой оболочки.

Шаг 2. Триангуляция выпуклой оболочки.

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

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

Шаг 5. Находится треугольник, содержащий новую точку.

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

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

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

внутренней точки.

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

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

Методы повышения быстродействия вычисления алгоритма инкремента.

1. Построение первоначального треугольника р°/р02р°з, покрывающего всё множество исходных точек Рь ¡=1,2,3, (рис. 3).

Треугольник р"¡р'^р'з гарантирует, что Р содержится в треугольнике рП1р02р"з-Чтобы не вводить большие координаты, определяем р°1,р02,р°з по формуле (1): Р°1 = (Хср,¥ср+ЗМ),

Р°2 = (Хср + ЗМ,Уср), (1)

Р°з = (Хср-ЗМ,Уср-ЗМ), где Хср, Уср - среднее арифметическое значение координат X, У; М -

наибольшее значение величин (Хтах - Хт,„)/2 и (Утах - Утт)/2, как показано на рис. 3. 6

А

р.

У

о

Рис. 3. Первоначальный треугольникр ¡р 2р з

2. Использование дерева для хранения триангуляции £>.

Чтобы найти треугольник, содержащий рг (рис. 4), мы используем структуру дерева триангуляции Д которая направлена на ациклический график. Листья О соответствуют треугольнику текущей триангуляции, и можно указывать кросс между листьями и триангуляцией. Внутренние узлы £> соответствуют треугольникам, которые находились в триангуляции на некоторых более ранних стадиях, но уже были уничтожены.

Структура дерева О строится следующим образом. Сначала мы инициализируем структуру дерева Б с одним узлом, который соответствует треугольнику р ¡р>2р з (рис. 3). Затем добавлением точки мы разделим текущий треугольник, содержащий точку, на три (или два) новых треугольника. К соответствующим изменениям в й добавим три (или два) новых листа до О и создадим лист для треугольника рр#к в один внутренний узел с исходящим указателем на эти три (или два) листа. Аналогичным образом, когда мы поменяли два треугольника Pl¡PiPj и /?,£>/>/ на треугольники ркрр/ и /адр, переброской ребра /?,/),, мы создаем листья для двух новых треугольников р^рр/ и ркррр и узлы треугольников p|ípipj и р,рр! получают указатели на два новых листа. На рисунке (рис. 4) показан пример изменения в Д вызванного добавлением точки. Заметим, что когда мы делаем лист на внутреннем узле, он получает не более трёх исходящих указателей.

Используя дерево Д мы можем локализовать следующую точку рп которая добавлена в текущей триангуляции. Это делается следующим образом. Мы начинаем в корне Д что соответствует первоначальному треугольнику р"¡р"2Р з-

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

Л

/ Л,

ЛГЛ

\Р1

«с......

Л» I

//Ч. * \

Разделение м

(Z)

!

Л

©

л

KJ

о ь

Переброска ребер pip,

д

IV

:> о Q.

ч

\

jtNJu

Переброска ребер Pif:T

(Д;)

(i)

\\

/1\ г1 Л Ь , , , ,

~ nUs\ \

' и 1

t

Рис. 4. Эффект добавления точки рг в треугольник Д / Поскольку любые узлы представляют собой не больше чем три листа, берётся линейное время для поиска в числе узлов, или, другими словами, в числе треугольников, сохраняемых в D, что содержитрг.

Алгоритм использует простую структуру данных. Если используется ацикличное дерево для хранения и поиска треугольника, тогда трудоёмкость алгоритма оценивается в среднем О (N log N). В худшем О (Л'2). Блок-схема алгоритма инкремента (рис. 5).

Рис. 5. Блок-схема алгоритма инкремента

Алгоритм "заметающей линии". Идея алгоритма заметающей линии является весьма простой: во-первых, геометрические элементы сортируются. Тогда вообразим, что заметающая линия / скользит сверху вниз над плоскостью и останавливается на так называемых точках события. Часть проблемы решена, и структура данных обновляется. А другая часть проблемы остаётся не решенной до конца. Граница между решенной и нерешенной частью делится на так называемую береговую линию, которая состоит из связанных цепей параболических дуг (рис. 6).

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

9

попадает на новую точку из Р. В этом случае вертикальная проекция сделана по цепочке параболических дуг, и новая параболическая дуга создана (рис. 7).

Л..

7Г

Рис. б. Береговая линия вверх заметающей линии Каждая парабола определяется по формуле (2)

Р'=у = ~%р1-1) ~2Р/,Х+р+ ~1у1

(2)

где 1У - значение ^-координат заметающей линии, р,„ р,у - значение координат любой точки р/ на параболе.

1 Г

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

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

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

Блок-схема алгоритма заметающей линии (рис. 9).

Рис. 9. Блок-схема алгоритма заметающей линии.

Алгоритм заметающей линии является одним из самых популярных методов ускорения для построения триангуляции. Алгоритм заметающей линии выполняется очень быстро с трудоёмкостью О (N log N). Вычислительный алгоритм заметающей линии очень сложен.

Комбинация алгоритмов инкремента и заметающей линии. Идея комбинации алгоритмов инкремента и заметающей линии является весьма простой:

11

рассмотрим рис. 10 и предположим, что заметающая линия л движется снизу вверх и уже проходит 15 первоначальных точек. Окружение алгоритма является двумя полилиниями:

- нижняя полилиния (представлена линией точка-тире на рис. 10) состоит из частей выпуклой оболочки. Назовем её нижняя выпуклая оболочка.

- верхняя полилиния (представлена пунктирной линией) рассматривается как продвижение фронта. Продвижение фронта отделяет вершины заметающей и вершины незаметающей. Форма продвижения фронта зависит от расположения точек, которые уже заметены.

Нижняя выпуклая оболочка и продвижение фронта имеют точно две совместных вершины с минимальной и максимальной х-координатой (вершины 4 и 7 на рис. 10а). Все точки между нижней выпуклой оболочкой и продвижением фронта являются триангуляциями, соответствующими свойству пустого круга (условие Делоне).

Когда заметающая линия встречает очередную точку (вершина 15 на рис. 106), алгоритм выполняется следующим образом: вначале делается вертикальная проекция вершины 15 на продвижении фронта. Она попадает на ребро 14,11. В этом случае легко построить новый треугольник А 15,11,14 и заменить продвижение фронта, что соответствует новой ситуации (рис. 106). К сожалению, нет гарантии, что новый треугольник Ацл,^ допустим, и необходимо проверить его с соседом Ayj4.ii, соответствуют ли они свойству пустого круга. Как видно на рис. 10в,

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

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

1. Инициирование

Сортировка исходных точек относительно ^-координат. Инициируют продвижение фронта и нижней выпуклой оболочки из двух первоначальных точек. Вершины в продвижении фронта и нижней выпуклой оболочке расположены относительно х координаты.

2. Триангуляция

Очередная точка V проектируется вертикально на продвижении фронта. Возможем один из четырёх случаев:

- проекция попадает на продвижение фронта,

- проекция не попадает на продвижение фронта,

- точка V локализуется на продвижении фронта,

- точка V совпадает с одной из вершин на продвижении фронта. а. Проекция попадает на продвижение фронта.

Одно ребро продвижения фронта, на которое попадает вертикальная проекция точки V, определяет две вершины выражения £ и Я, как на рис. 11а. Легко построить новый треугольник v,R,L От вершины Ь соседнего треугольника к, I, Я исходит прямое влияние, и надо проверить рекурсивно условие Делоне. Продвижение фронта обновляется вставкой вершины V между вершиной Ь и Я (рис. 116).

Рассмотрим угол между векторами, который определяется вершинами V, Я, Я1 на рис. 116. Если значение угла меньше, чем Зп/4, то строим еще треугольник V,!11,Я (рис. 11в). Проверим условие Делоне для нового треугольника с двумя соседними треугольниками V,Я,I и Я1,1,Я. Удалим вершину Я из продвижения

Рис. 11. Продвижение фронта попадает на точку

фронта (рис. 11в) и повторим процесс для V, Я1, Я2, пока угол между ними не будет больше, чем Зтг/4 (рис. 11 г). Треугольники, полученные таким способом, резко нарушают условие Делоне.

б. Проекция не попадает на продвижение фронта.

Очередная точка V проектируется вертикально на продвижении фронта и, возможно, не попадает на левостороннее и правостороннее продвижения фронта. На рис. 12 показан случай непопадания V на левостороннее продвижение фронта. В этом случае новый треугольник у,Ы,1 построен и проверен условием Делоне. Новый треугольник на правостороннем продвижении фронта порождён как случай, когда проекция попадает на продвижение фронта.

V

Этот случай появляется, когда вершины V, Ь и Я имеют одинаковую координату у. В этом случае разделим треугольник Ь,Я,к на два треугольника 1,\\к и V,Я, к (рис. 13). Оба треугольника согласованы с соседними треугольниками и вершина V вставлена между Ь и Я.

г. Точка V совпадает с одной из вершин на продвижении фронта.

В этом случае точка V пропущена, и следующая точка взята непосредственно.

3. Окончание

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

9

Я-

Рис. 14. Переход продвижения фронта до верхней выпуклой оболочки Структуры данных. Продвижение фронта определяется простой хэш-таблицей (hash-table) с двусвязным списком структуры (рис. 15).

s>>- Hey Ktv key Key »1 Rev —a A'ey

vr Vt vj V) v vi VI vi W

П Л е— 7? л с----- 71 77 n 71

m'; г it

3tD

Рис. 15. Сохранение продвижения фронта Вершины в продвижении фронта расположены относительно х-координаты. Каждая запись продвижения фронта сохраняет ключ (Кеу), индекс вершины (у/) и индекс треугольника (Г/), который использует совместные ребро с продвижением фронта.

Данные точки и треугольники представляются обычной структурой "Узлы и треугольники". В структуре "Узлы и треугольники" для каждого треугольника хранятся три указателя на образующие его узлы и три указателя на смежные треугольники. При 5-байтовом представлении координат (х, у, И) и 4-байтовых представлении указателей данная структура "узлы и треугольники" требует [24-N + 24-М) байт (где ТУ- число исходных точек, М- число треугольников, М <2-И - 5).

Блок-схема комбинации алгоритмов "инкремента и заметающей линии" на рис. 16.

Рис. 16. Блок-схема комбинации алгоритмов инкремента и заметающей линии. Анализ алгоритма. Во-первых, сортировка всех исходных точек, соответствующих у координате. Используя Quicksort, сортировка выполняется в Ti времени, определяемом по формуле (3)

Т, = 0(N log N), (3)

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

времени. Предполагаем, что элемент на хэш-таблице HashSize, HashSize > 0, и т вершин на продвижении фронта. Для локализации ребра на продвижении фронта в среднем является т / HashSize. Новый треугольник порождён и проверен по условию Делоне, эти операции сделаны за одинаковое время. Легализация новых треугольников выполняется в логарифмическом времени. Сумма времени во второй части вычисляется по формуле:

Т2 = N {ml HashSize + log N). (4)

Обычно m « N и HashSize » 1. В случае (m / HashSize) « N и можно опускать (m / HashSize), тогда

Т2= О (N log N). (5)

Общее время для процесса алгоритма таково:

Таб. = т, + Т2 = О (AHog N) + О (jVlog N) = О (TVlog N). (6)

Алгоритм комбинации инкремента и заметающей линии имеет много преимуществ: прост в реализации; используются простые структуры данных, и они не требуют большой дополнительной памяти для своей работы; один из самых быстродействующих (на практике) из алгоритмов построения триангуляции Делоне, трудоёмкость О (jV log АО-

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

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

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

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

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

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

Таблица 1

№ Количество точек Время работы алгоритмов (секунды)

Инкремент Заметающая линия Комбинация"инкремента и заметающей линии"

1 9 744 0.500 0.141 0.051

2 25 344 0.648 0.441 0.148

3 50 000 1.410 0.941 0.324

4 100 000 3.082 1.945 0.672

Время работы алгоритмов в зависимости от числа исходных данных приведено в графическом виде на рис. 18.

---е---Инкремент

Заметающая линия Инкремент-гЗаметающал линия

10 ООО 20 ООО 30 ООО 40 ООО 50 ООО 60 000 70 ООО 80 000 30 000 100 000

Количество точек Рис. 18. График времени работы алгоритмов

Время работы алгоритмов не только зависит от количества исходных данных, но и от распределения точек (рис. 19).

ШшМ ш

Рис. 19. Распределение разных точек: а -униформа; 6 - гауссово; в - гроздь; г - сетка. В таблице 2 приведено время работы алгоритмов в зависимости от распределений исходных данных.

Таблица 2

Распределения точек (100 ООО точек) Времяоаботы алгоритмов (секунды)

Инкремент Заметающая линия Комбинация "инкремента и заметающей линии"

Униформа 3.043 1.930 0.680

Гауссово 3.043 2.645 0.672

Гроздь 3.125 1.863 0.660

Сетка 3.016 5.949 0.441

Результат экспериментального алгоритма "Комбинации инкремента и заметающей линии" на компьютере с процессором Intel Pentium 4.0 ГГц, памятью 3.0 Гб, работающим в операционной системе Windows ХР, приведён в таблице 3.

Таблица 3

Ко-во точек Время, с. Ко-во точек Время, с. Ко-во точек Время, с.

1 000 000 2.875 5 000 000 16.656 9 000 000 29.063

2 000 000 4.813 6 000 000 19.450 10 000 000 31.953

3 000 000 6.750 7 000 000 22.328 11 000 000 34.859

4 000 000 8.594 8 000 000 25.313 12 000 000 37.781

Сравнение скорости выполнения нашей программы (MapStudio) с другими программами.

Результат сравнения программы MapStudio с программой Photomod 4.4.736 на компьютере с процессором Intel Pentium 3.0 ГГц, памятью 512 Мб, работающим в операционной системе Windows ХР, приведён в таблице 4.

Таблица 4

№ Количество Время работы программ (секунды)

точек MapStudio Photomod 4.4.736

1 261 788 1.967 7.0

2 1 541 000 14.469 50.0

Результат сравнения нашей программы MapStudio с программой Autodesk Land Desktop 2005 на компьютере с Intel Pentium 1.5 ГГц, памятью 512 Мб, работающим в операционной системе Windows ХР, приведён в таблице 5.

Таблица 5

№ Количество Время работы программ (секунды)

точек MapStudio Land Desktop 2005

1 261 788 2.184 7.0

2 1 541 000 15.773 45.0

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

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

Интерполяция высот. Эта операция позволяет вычислить значение высоты поверхности для любой заданной плановой точки. Например, в треугольнике М^Х^ V/, М2(Х2, У2, 22), М3{Х3, У3, 23) требуется вычислить высоту точки Р{Хр, УР, 2р) на рис. 20.

М2

Рис. 20. Интерполяция высоты точки Р Построение профилей. Одной из базовых задач анализа триангуляционных поверхностей является построение профилей. Результатом этой работы будет вертикальный профиль (рис. 21).

i Studio - [Drawing]

\ File Edit Format Draw View Modify Topo D.T.M Test

41 ?547.237,249032?. 335

0.060" 0.070"! 9744; 0 out liashi 17623 T.Giac; 168/502 Mb

Рис. 21. Построение профилей разрезов поверхности Построение изолиний. Результат построения изолиний показан на рис. 22, трудоёмкость алгоритма, очевидно, является линейной относительно размера триангуляции.

ill5—.J52.?_ 0 060" i)063:- 9740 0 out hash: 17617 T.Giac 150/502 Mb

Рис. 22. Построение изолиний

Построение изоконтуров. Изоконтурами между уровнями А/ и к2 называется геометрическое место точек на поверхности, имеющих высоту И е (А/, к2). Результат построения изоконтуров показан на рис. 23.

..................................................................................................................К .! J I

^ File Edit Format Draw View Modify Topo D.T.M Test _ в X.

Oiii »O r*

417180.442.2490006.180

0.061"j 0.082"; 9744! 0 out hash 117527 T.Giac 1207/502 Mb

Рис. 23. Построение изоконтуров по модели рельефа

ОБЛАСТИ ПРИМЕНЕНИЯ РЕЗУЛЬТАТОВ РАБОТЫ

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

• Создание прогнозных пространственных моделей с учетом характерных особенностей ландшафта.

• Вычисление геометрических характеристик (площади, протяженности, периметра) с учетом рельефа для нужд архитектуры и городского планирования, инженерных изысканий, картографии, навигации.

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

• Расчет освещенности и ветрового режима для архитектуры и городского планирования, инженерных изысканий, экологического мониторинга.

• Построение зон видимости для телекоммуникационных и сотовых компаний, архитектуры и городского планирования.

• Ортотрансформирование материалов аэрофотосъемки и космической съемки.

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

22

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Проведено исследование и анализ методов представления и применения цифровых моделей рельефа.

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

3. Предложены методы повышения скорости вычисления для алгоритмов инкремента и заметающей линии.

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

5. Исследованы алгоритмы анализа поверхностей: построение профилей; построение горизонталей; построение изоконтуров; построение изоклин; расчет объемов земляных работ.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

(по перечню ВАК 2 статьи)

1. Майоров А. А., Нгуен Тхе Конг. Эффективный алгоритм построения триангуляции Делоне // Известия высших учебных заведений. Геодезия и аэрофотосъемка. Московский государственный университет геодезии и картографии. 2011. № 1.С. 105-108.

2. Майоров А. А., Нгуен Тхе Конг. Перспективы развития компьютерных технологий создания цифровых моделей рельефа // Известия высших учебных заведений. Геодезия и аэрофотосъемка. Московский государственный университет геодезии и картографии. 2011. №4. С. 107-110.

3. Чан Зыонг, Нгуен Тхе Конг. Разработка алгоритмов и графических программ, предназначенных для цифрового картографирования // Научно-технический журнал. Ханойский горно-геологический университет. 2004. № 5. С. 47-55.

4. Чан Хань, Чан Зыонг, Нгуен Тхе Конг. Оптимизация использования ресурсов памяти при программировании уравнивания геодезических сетей // Научно-технический журнал. Ханойский горно-геологический университет. 2005. № 9. С. 68-72.

Подписано в печать 10.11.2011. Гарнитура Тайме Формат 60790/16. Бумага офсетная. Печать офсетная. Объем 1,5 усл. печ. л. Тираж 80 экз. Заказ .№230 Цена договорная Издательство МИИГАиК 105064, Москва, Гороховский пер., 4

Содержание диссертации, кандидата технических наук, Нгуен Тхе Конг

ВВЕДЕНИЕ.

ГЛАВА 1. ОБОБЩЕНИЕ ЦИФРОВЫХ МОДЕЛЕЙ РЕЛЬЕФА.

1.1. ПОНЯТИЕ О ЦИФРОВОЙ МОДЕЛИ РЕЛЬЕФА.

1. 2. МЕТОДЫ ПРЕДСТАВЛЕНИЯ ЦИФРОВЫХ МОДЕЛЕЙ РЕЛЬЕФА

1.2. 1. Регулярные модели данных (GRID).

1.2. 1. 1. Метод Кригинга (Kriging).

1.2. 1.2. Метод радиальных базисных функций.

1.2. 1.3. Метод обратных расстояний.

1.2.1.4. Метод Шепарда (Shepard).

1.2. 1.5. Метод естественного соседа.

1. 2. 2. Триангуляционная модель данных (TIN).

1.3. ПРИМЕНЕНИЕ ЦИФРОВЫХ МОДЕЛЕЙ РЕЛЬЕФА.

ГЛАВА 2. АНАЛИЗ АЛГОРИТМОВ ПОСТРОЕНИЯ ЦИФРОВЫХ МОДЕЛЕЙ РЕЛЬЕФА.

2. 1. ОБОБЩЕННЫЙ МЕТОД ВОРОНОГО-ДЕ ЛОНЕ.

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

2. 1. 1. 1. Определение триангуляции Делоне.

2. 1. 1.2. Проверка условия Делоне.

2. 1.2. Диаграмма Вороного.

2. 1.3. Связь между диаграммой Вороного и триангуляцией Делоне.

2. 1.4. Метод Вороного-Делоне.

2. 2. АЛГОРИТМ ИНКРЕМЕНТА (INCREMENTAL).

2. 2. 1. Обобщенный алгоритм.

2. 2. 2. Анализ алгоритма.

2. 2. 3. Методы повышения быстродействия вычисления.

2. 2. 4. Вычислительный алгоритм.

2.3. АЛГОРИТМ ЗАМЕТАЮЩЕЙ ЛИНИИ (SWEEP-LINE).

2.3. 1. Обобщенный алгоритм.

2.3.2. Структура данных.

2.3.3. Вычислительный алгоритм.

2. 3. 4. Анализ алгоритма.

2.4. КОМБИНАЦИЯ АЛГОРИТМОВ ИНКРЕМЕНТА И

ЗАМЕТАЮЩЕЙ ЛИНИИ.

2.4. 1. Обобщенный алгоритм.

2. 4. 2. Вычислительный алгоритм.

2. 4. 3. Структура данных.

2. 4. 4. Анализ алгоритма.

2.5. ВЫВОДЫ ПО ГЛАВЕ.

ГЛАВА 3. РАЗРАБОТКА ПРОГРАММЫ ПОСТРОЕНИЯ ЦИФРОВЫХ МОДЕЛЕЙ РЕЛЬЕФА.

3. 1. БЛОК-СХЕМЫ АЛГОРИТМОВ В ПРОГРАММЕ.

3. 1. 1. Блок-схема алгоритма инкремента (рис. 3.1).

3. 1.2. Блок-схема алгоритма заметающей линии (рис. 3.2).

3.1.3. Блок-схема комбинации алгоритмов инкремента и заметающей линии (рис. 3.3).

3.2. ПРОЕКТИРОВАНИЕ СТРУКТУР ДАННЫХ.

3.3. ЭКСПЕРИМЕНТАЛЬНЫЕ АЛГОРИТМЫ.

3.3.1. Экспериментальные качества алгоритмов.

3.3.2. Экспериментальные скорости алгоритмов.

3.4. СОЗДАНИЕ ПРИКЛАДНЫХ ИНСТРУМЕНТОВ.

3. 4. 1. Интерполяция высот.

3. 4. 2. Построение профилей.

3. 4. 3. Построение изолиний (горизонталей).

3. 4. 4. Построение изоконтуров.

3. 4. 5. Построение изоклин.

3. 4. 6. Расчет объемов земляных работ.

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

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

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

Для получения ЦМР на большие территории наиболее эффективным решением является обработка космических снимков, лазерная локация.

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

Актуальность темы.

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

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

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

Цель и основные задачи исследования.

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

1. Обзор и анализ методов представления и применения цифровых моделей рельефа.

2. Исследование алгоритмов инкремента и заметающей линии для построения триангуляции Делоне.

3. Предложение методов повышения скорости вычисления для алгоритмов инкремента и заметающей линии.

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

5. Исследование алгоритмов анализа поверхностей: построение профилей; построение горизонталей; построение изоконтуров; построение изоклин; расчет объемов земляных работ.

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

Научная новизна работы.

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

Предложены методы повышения скорости вычисления для алгоритмов инкремента и заметающей линии.

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

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

Положения, выносимые на защиту.

1. Алгоритмы инкремента и заметающей линии построения триангуляции Делоне.

2. Методы повышения скорости вычисления для алгоритмов инкремента и заметающей линии.

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

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

Вклад автора в проведенное исследование.

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

Практическая значимость работы.

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

Структура и объем диссертации.

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

Заключение Диссертация по теме "Геоинформатика", Нгуен Тхе Конг

Тоб = Т1 + Т2 = О (TVlog N) + О (Nlog АО = О (NlogN). (2.10) 2.5. ВЫВОДЫ ПО ГЛАВЕ

Алгоритм инкремента является самым простым алгоритмом. Идея алгоритма очень понятна и использует простую структуру данных. Если используется ацикличное дерево для хранения и поиска треугольника, тогда трудоёмкость алгоритма оценивается в среднем О(N log TV). Вычислительный алгоритм очень простой, особенно при окончании процесса построения триангуляции, когда существует дерево поиска треугольника. Эта проблема очень важна для процесса редактирования и анализа цифровых моделей рельефа, например, когда нужно вставить или удалить несколько точек, построить профили и т.д. Но всё-таки алгоритм зависит от распределения исходных данных, в худшем случае алгоритм инкремента может выполняться с трудоёмкостью О(N2).

Алгоритм заметающей линии Фортуне (Fortune's sweep-line) является одним из самых популярных методов ускорения для построения триангуляции. Алгоритм заметающей линии выполняется очень быстро с трудоёмкостью О(N log N). В алгоритме существует N событий точки, самое большее 2N-5 событий круга, но алгоритм требует использования очень сложных структур данных, например, нужна еще одна структура для

60

3. 2. ПРОЕКТИРОВАНИЕ СТРУКТУР ДАННЫХ

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

В триангуляции можно выделить 3 основных вида объектов: узлы (точки, вершины), рёбра (отрезки) и треугольники. Для простой операции мы выбираем структуру "Узлы и треугольники".

Type POINT3D //координат. X As Double Y As Double Z As Double

End Type

Type TRIANGLE iD (0 To 2) As Long //Указатель на узел (образующие узлы). iT (0 То 2) As Long /ГУказатель на соседние треугольники.

End Туре

В структуре "Узлы и треугольники" для каждого треугольника хранятся три указателя на образующие его узлы и три указателя на смежные треугольники (рис. 3.4) ч ч

Рис. 3.4. Связи треугольников структуры «Узлы и треугольники» памятью 3.0 Гб, работающим в операционной системе Windows ХР, приведём в таблице 3.3 и на рисунке (рис. 3.8).

ЗАКЛЮЧЕНИЕ

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

1. Обзор и анализ методов представления и применения цифровых моделей рельефа.

2. Исследованы алгоритмы инкремента и заметающей линии для построения триангуляции Делоне.

3. Предложены методы повышения скорости вычисления для алгоритмов инкремента и заметающей линии.

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

5. Исследованы алгоритмы анализа поверхностей: построение профилей; построение горизонталей; построение изоконтуров; построение изоклин; расчет объемов земляных работ.

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

Автором разработан и протестирован пакет программ для обработки созданной триангуляционной модели:

- построение профилей;

- построение горизонтали;

- построение изоконтуров;

- построение изоклин;

- расчет объемов земляных работ.

Проводились сравнительные исследования скорости вычислений для различного количества исходных точек, которые подтвердили эффективность разработанного метода по сравнению с программой

82 конференции. Томск: Издательство Томского университета, 2000. С. 37-41.

10. Костюк IO.JL, Фукс A.JI. Приближенное вычисление оптимальной триангуляции // Геоинформатика. Теория и практика. Вып. 1. Томск: Издательство Томского университета, 1998. С. 61-66.

11. Ласло М. Вычислительная геометрия и компьютерная графика на С++: Пер. с англ. М.: БИНОМ, 1997. 304 с.

12. Майоров А. А., Нгуен Т. К. Перспективы развития компьютерных технологий создания цифровых моделей рельефа // Известия высших учебных заведений. Геодезия и аэрофотосъемка. Московский государственный университет геодезии и картографии. 2011. № 4. С. 107-110.

13. Майоров А. А., Нгуен Т. К. Эффективный алгоритм построения триангуляции Делоне // Известия высших учебных заведений. Геодезия и аэрофотосъемка. Московский государственный университет геодезии и картографии. 2011. № 1. С. 105-108.

14. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. М.: Мир, 1989. 478 с.

15. Роджерс Д., Адаме Дж. Математические основы машинной графики / Пер. с англ. М.: Машиностроение, 1980. 204 с.

16. Синицын С.И. Гибридный рекурсивно-инкрементный алгоритм построения триангуляции Делоне. Материалы конференции GraphiCon. Нижний Новгород. 2001.

17. Скворцов A.B. Триангуляция Делоне и ее применение. Томск. Издательство ТГУ. 2002.

18. Скворцов A.B., Костюк Ю.Л. Применение триангуляции для решения задач вычислительной геометрии // Геоинформатика: Теория и практика. Вып. 1. Томск: Издательство Томского университета, 1998. С. 127-138.

19. Скворцов А.В., Костюк Ю.Л. Эффективные алгоритмы построения триангуляции Делоне // Геоинформатика. Теория и практика. Вып. 1. Томск: Издательство Томского университета, 1998. С. 22—47.

20. Скворцов А.В., Поспелов П.И., Крысин С.П. Геоинформатика в дорожной отрасли (на примере IndorGIS). М.: Издательство МАДИ, 2005. 389 с.

21. Фукс А.Л. Изображение изолиний и разрезов поверхности, заданной нерегулярной системой отсчётов // Программирование. 1986. № 4. С. 87-91.

22. Фукс А.Л. Предварительная обработка набора точек при построении триангуляции Делоне // Геоинформатика. Теория и практика. Вып. 1. Томск: Издательство Томского университета, 1998. С. 48-60.

23. Robert Sedgewick Cam nang thuat toan: Пер. с англ. NXB Khoa hoc Ky thuat, Thanh ph6 H6 Chi Minh, 1998. Том 1: 409 с. Том 2: 340 с.

24. Vera В. Anand Do hoa may tinh va mo hinh hoa hinh hoc: Пер. с англ. NXB Thanh ph6 Ho Chi Minh, 2000. 408 c.

25. Agarwal P.K., Suri S. Surface approximation and geometric partitions // Proc. 5th ACM-SIAM Symp. on Discrete Algorithms. 1994. P. 24-33.

26. De Floriani L. A pyramidal data structure for triangle-based surface description // IEEE Computer Graphics and Applications. 1989. Vol. 9. N. 2. P. 67-78.

27. De Floriani L., Falcidieno В., Nagy G., Pienovi C. On sorting triangles in a Delaynay tessellation // Algorithmica. 1991. N. 6. P. 522-535.

28. De Floriani L., Magillo P., Puppo E. Compressing Triangulated Irregular Networks // Geoinformatica. 2000. Vol. 1. N. 4. 67-88.

29. De Floriani L., Marzano P., Puppo E. Multiresolution Models for Topographic Surface Description // The Visual Computer. 1996. Vol. 12. N. 7. P. 317-345.

30. Evans F., Skiena S., Varshney A. Optimizing triangle strips for fast rendering//Proc. IEEE Visualization. 1996. P. 319-326.

31. Fowler R.J., Little J.J. Automatic extraction of irregular network digital terrain models // Computer Graphics. 1979. Vol. 13. N. 3. P. 199-207.

32. Gilbert P.N. New results on planar triangulations. Tech. Rep. ACT-15, Coord. Sci. Lab., University of Illinois at Urbana, July 1979.

33. Guibas L., Stolfi J. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams // ACM Transactions on Graphics. Vol. 4. N. 2. 1985. P. 74-123.

34. Guttmann A., Stonebraker M. Using a Relational Database Management System for Computer Aided Design Data // IEEE Database Engineering.

1982. Vol. 5.N. 2.

35. Heller M. Triangulation algorithms for adaptive terrain modeling // Proc. of the 4th Intern. Symp. on Spatial Data Handling, July 1990. P. 163-174.

36. J. L. Bentley, B. W. Weide, and A. C. Yao. Optimal expected time algorithms for closest point problems. ACM Transactions on Mathematical Software, 6(4):563-580, 1980.

37. Kirkpatrik D.G. Optimal search in planar subdivisions // SIAM J. Comput.,

1983. Vol. 12. N. l.P. 28-35.

38. L. Guibas, D. Knuth, and M. Sharir. Randomized incremental construction of delaunay and voronoi diagrams. Algorithmica, 7:381^113, 1992.

39. Lawson C. Transforming triangulations // Discrete Mathematics. 1972. N. 3. P. 365-372.

40. Lee D. Proximity and reachability in the plane // Tech. Rep. N. R-831, Coordinated Sci. Lab. Univ. of Illinois at Urbana. 1978.

41. Lee D., Schachter B. Two algorithms for constructing a Delaunay triangulation // Int. Jour. Comp. and Inf. Sc. 1980. Vol. 9. N. 3. P. 219-242.

42. Lee J. Comparison of existing methods for building triangular irregular network models of terrain from grid digital elevation models // Int. Journal of GIS. 1991. Vol. 5. N. 3. P. 267-285.

43. Lewis B., Robinson J. Triangulation of planar regions with applications // The Computer Journal. 1978. Vol. 21. N. 4. P. 324-332.

44. Lingas A. The Greedy and Delaunay triangulations are not bad. // Lect. Notes Comp. Sc. 1983. Vol. 158. P. 270-284.

45. Lloyd E. On triangulation of a set of points in the plain // MIT Lab. Comp. Sc. Tech. Memo. 1977. N. 88. 56 p.

46. M. T.Goodrich, J.-J. Tsay,D. E.Vengroff, , and J. S. Vitter. External-memory computational geometry. Symposium on Foundations of Computer Science, 34, 1993.

47. Manacher G., Zobrist A. Neither the Greedy nor the Delaunay triangulation of planar point set approximates the optimal triangulation // Inf. Proc. Let. 1977. Vol. 9. N. l.P. 31-34.

48. Mark de Berg, Marc van Kreveld, Marc Overmars, Otfried Schwarzkopf Computational Geometry: algorithms and applications. 2nd edition. Springer-Verlag, 2000, 367 p., ISBN 3-540-65620-0.

49. McCullagh M.J., Ross C.G. Delaunay triangulation of a random data set for isarithmic mapping // The Cartographic Journal. 1980. Vol. 17. N. 2. P. 9399.

50. Midtbo T. Spatial Modeling by Delaunay Networks of Two and Three Dimensions. Dr. Ing. thesis. Department of Surveying and Mapping, Norwegian Institute of Technology, University of Trondheim, February 1993.

51. Nagy G. Terrain visibility // Computers and Graphics. 1994. Vol. 18. N. 6.

52. P. Green and R. Sibson. Computing dirichlet tessellations in the plane. Computing Journal, 21:168-173, 1977.

53. Puppo E. Variable resolution triangulations // Computational Geometry. 1998. Vol. 11. P. 219-238.

54. R. A. Dwyer. A faster divide-and-conquer algorithm for constructing delaunay triangulations. Algorithmica, 2:137-151, 1987.

55. S. Fortune. A sweepline algorithm for voronoi diagrams. Algorithmica, 2:153-174, 1987.

56. S. Fortune. Numerical stability of algorithms for delaunay triangulations and voronoi diagrams. Annual ACM Symposium on Computational Geometry, 1992.

57. S. Fortune. Stable maintenance of point-set triangulations in two dimensions. IEEE Symposium on Foundations of Computer Science, pages 494-499, 1989.

58. Shapiro M. A note on Lee and Schachter's algorithm for Delaunay triangulation // Inter. Jour, of Comp. and Inf. Sciences. 1981. Vol. 10. N. 6. P. 413-418.

59. Sibson R. Locally equiangular triangulations // Computer Journal. 1978. Vol.21.N.3.P. 243-245.

60. Sloan S.W. A fast algorithm, for constructing Delaunay triangulations in the plane // Adv. Eng. Software. 1987. Vol. 9. N. 1. P. 34-55.

61. Tourna G., Rossignac J. Geometric compression through topological surgery // ACM Transactions on Graphics. 1998. Vol. 17. N. 2. P. 84-115.

62. Watson D.F. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes // The Computer Journal. 1981. Vol. 24. N. 2. P. 167-172.

63. Zalik B. An efficient sweep-line Delaunay triangulation algorithm // Computer-Aided Design, (37) 2005, pp. 1027-1038.