Исследование и разработка высокопроизводительного алгоритм а построения цифровых моделей рельефа
На правах рукописи
НГУЕН ТХЕ КОНГ
ИССЛЕДОВАНИЕ И РАЗРАБОТКА ВЫСОКОПРОИЗВОДИТЕЛЬНОГО АЛГОРИТМА ПОСТРОЕНИЯ ЦИФРОВЫХ МОДЕЛЕЙ РЕЛЬЕФА
Специальность: 25.00.35 – “Геоинформатика”
Автореферат
диссертации на соискание учёной степени
кандидата технических наук
Москва – 2011
Диссертация выполнена на кафедре Информационно-измерительных систем Московского государственного университета геодезии и картографии (МИИГАиК)
Научный руководитель: доктор технических наук, профессор
Майоров Андрей Александрович
Официальные оппоненты: доктор технических наук, профессор
Цветков Виктор Яковлевич,
кандидат технических наук
Матвеев Александр Станиславович
Ведущая организация: ФГУП “Госцентр “Природа”
Защита состоится « 15 » декабря 2011 г. в 10 часов на заседании диссертационного совета Д.212.143.03 в Московском государственном университете геодезии и картографии (МИИГАиК) по адресу: 105064 Москва, Гороховский пер., 4, зал заседания Ученого совета.
С диссертацией можно ознакомиться в библиотеке Московского государственного университета геодезии и картографии (МИИГАиК).
Автореферат разослан « 11 » ноября 2011 г.
Ученый секретарь
диссертационного совета Климков Ю.М.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы.
В настоящее время при моделировании местности, выполнении картографических работ в различных геоинформационных приложениях широко используются цифровые модели рельефа (ЦМР). Для получения ЦМР на большие территории наиболее эффективным решением является обработка космических снимков, лазерная локация. Обработка огромных массивов исходных данных (сотни гигабайт дискового пространства) выполняется на компьютерах в режиме реального времени, что является большой проблемой. Особенно актуальной является проблема построения триангуляции, что связано с неустойчивостью и неудовлетворительным временем работы многих существующих алгоритмов на современных наборах данных.
Актуальность применения ЦМР объясняется, прежде всего, тем, что ЦМР обеспечивает большую наглядность и интерпретируемость данных, предоставляет возможность наиболее полно передавать информацию об изменениях объектов и исследуемой среды с течением времени, а также позволяет реализовать ряд прикладных задач, недоступных для решения с использованием двумерных данных. Кроме того, по таким моделям пользователи легко могут производить расчеты площадных и объемных характеристик поверхностей и уклонов, экспозиций и отмывки рельефа, а также выполнять построение профилей и изолиний рельефной поверхности.
Цель и основные задачи исследования.
Целью диссертационной работы является разработка и исследование компьютерной технологии, позволяющей эффективно создавать цифровые модели рельефа с использованием большого количества точек. При выполнении исследования решались следующие задачи:
1. Обзор и анализ методов представления и применения ЦМР.
2. Исследование алгоритмов инкремента и заметающей линии для построения триангуляции Делоне.
3. Предложение методов повышения скорости вычисления для алгоритмов инкремента и заметающей линии.
4. Разработка эффективного алгоритма построения триангуляции Делоне на основе комбинации алгоритмов инкремента и заметающей линии.
5. Исследование алгоритмов анализа поверхностей.
6. Разработка программы построения цифровых моделей рельефа с прикладными инструментами для реализации разработки алгоритмов.
Научная новизна работы.
Обоснованы и предложены методы и алгоритмы инкремента и заметающей линии для построения триангуляции Делоне.
Предложены методы повышения скорости вычисления для алгоритмов инкремента и заметающей линии.
Разработан высокопроизводительный алгоритм построения триангуляции Делоне на основе комбинации алгоритмов инкремента и заметающей линии.
Разработана программа построения цифровых моделей рельефа с прикладными инструментами, реализующая разработанные алгоритмы.
Результаты, выносимые на защиту.
1. Методы повышения скорости вычисления алгоритмов инкремента и заметающей линии.
2. Высокопроизводительный метод и алгоритм построения триангуляции Делоне на основе комбинации алгоритмов инкремента и заметающей линии.
3. Программа построения цифровых моделей рельефа с визуальным интефейсом пользователя предметной области, реализующая разработанные алгоритмы.
Вклад автора в проведенное исследование.
Автором разработаны все алгоритмы и методы, выносимые на защиту, и разработана программа построения цифровых моделей рельефа.
Практическая значимость работы.
Выполненные анализы популярных алгоритмов и экспериментальные исследования показали, что предложен весьма эффективный алгоритм построения триангуляции Делоне. Примененные результаты исследования можно использовать для разработки программы построения цифровых моделей рельефа.
Апробация результатов работы.
Изложенные в диссертации материалы научных исследований докладывались и обсуждались на 65-ой научно-технической конференции студентов, аспирантов и молодых ученых МИИГАиК (апрель 2010 г.).
Структура и объем диссертации.
Диссертация состоит из введения, трёх глав, заключения, списка литературы, приложения и глоссария. Общий объем работы составляет 101 страница машинописного текста, 60 рисунков, 5 таблиц.
Публикации.
По материалам диссертации опубликовано 4 работы, две из которых в журнале, включенном в перечень ВАК.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы, сформулирована цель, поставлены задачи и описаны граничные условия для разработки алгоритмов обработки. Кратко рассмотрен круг вопросов, исследуемых в данной диссертационной работе. Далее, в каждой главе диссертации рассматривается одна из задач исследования, делается обзор публикаций по данной теме, производится обоснование выбора метода решения задачи, подробно описываются разработанные методы и алгоритмы, и в заключении кратко перечисляются основные результаты глав.
В первой главе “Обобщение цифровых моделей рельефа” представлены понятия о цифровой модели рельефа, методы представлений и применений цифровых моделей рельефа.
Во второй главе “Анализ алгоритмов построения цифровых моделей рельефа” представлены и проанализированы известные алгоритмы построения триангуляции Делоне.
Среди нескольких известных типов триангуляций на практике обычно применяется триангуляция Делоне. К настоящему времени разработано множество алгоритмов построения триангуляции Делоне: алгоритмы прямого построения, алгоритмы слияния, двухпроходные алгоритмы, итеративные алгоритмы.
В главе 2 представлены алгоритмы: инкремент, заметающая линия и новый алгоритм, который основывается на алгоритме заметающей линии и комбинации с характерного алгоритма инкремента.
Мы выбрали два алгоритма (инкремент, заметающая линия), поскольку они сейчас очень популярны и известны, каждый алгоритм имеет характерные особенности. Алгоритм инкремента является самым простым алгоритмом. Идея алгоритма достаточно понятна и использует простую структуру данных. Алгоритм заметающей линии выполняется очень быстро.
Алгоритм инкремента. Все инкрементные алгоритмы имеют в своей основе простую идею последовательного добавления точек в частично построенную триангуляцию Делоне. Формально это выглядит так.
Шаг 1. Построение выпуклой оболочки.
Шаг 2. Триангуляция выпуклой оболочки.
Шаг 3. Выполняется цикл по N для всех точек в соответствии с шагами 4–6.
Шаг 4. Добавляется n-я точка в уже построенную структуру триангуляции, то есть находится треугольник (построенный ранее), в который попадает очередная точка.
Шаг 5. Находится треугольник, содержащий новую точку.
Если новая точка совпадает с одной из вершин на ранее построенном треугольнике, в этом случае она пропускается и следующая точка взята непосредственно. Если новая точка не совпадает с вершинами на ранее построенном треугольнике, в этом случае она служит вершиной.
Если точка попадает на некоторое ребро, то определяется ребро, в которое попала новая точка. Затем разделяем два треугольника, которые имеют это общее ребро, на четыре новых треугольника.
Если точка попадает на внутренние треугольники, то разделяем этот треугольник на три новых треугольника (рис. 1).
Рис. 1. Две ситуации, возникающие при триангуляции после добавления новой внутренней точки.
Шаг 6. Проверяются все треугольники на соответствие условию Делоне с соседними треугольниками и выполняются необходимые перестроения (рис. 2).
.
Рис. 2. Переброска ребра
Конец алгоритма
Методы повышения быстродействия вычисления алгоритма инкремента.
1. Построение первоначального треугольника p01p02p03, покрывающего всё множество исходных точек Pi, i=1,2,3,…,N (рис. 3).
Треугольник p01p02p03 гарантирует, что P содержится в треугольнике p01p02p03. Чтобы не вводить большие координаты, определяем p01,p02,p03 по формуле (1):
р01 = (Xcp, Ycp + 3M),
p02 = (Xcp + 3M, Ycp), ( 1)
p03 = (Xcp - 3M, Ycp - 3M),
где Xcp, Ycp – среднее арифметическое значение координат Х, Y; M – наибольшее значение величин (Xmax - Xmin)/2 и (Ymax - Ymin)/2, как показано на рис. 3.
Рис. 3. Первоначальный треугольник p01p02p03
2. Использование дерева для хранения триангуляций D.
Чтобы найти треугольник, содержащий pr (рис. 4), мы используем структуру дерева триангуляции D, которая направлена на ациклический график. Листья D соответствуют треугольнику текущей триангуляции, и можно указывать кросс между листьями и триангуляцией. Внутренние узлы D соответствуют треугольникам, которые находились в триангуляции на некоторых более ранних стадиях, но уже были уничтожены.
Структура дерева D строится следующим образом. Сначала мы инициализируем структуру дерева D с одним узлом, который соответствует треугольнику p01p02p03 (рис. 3). Затем добавлением точки мы разделим текущий треугольник, содержащий точку, на три (или два) новых треугольника. К соответствующим изменениям в D добавим три (или два) новых листа до D и создадим лист для треугольника pipjpk в один внутренний узел с исходящим указателем на эти три (или два) листа. Аналогичным образом, когда мы поменяли два треугольника pkpipj и pipjpl на треугольники pkpipl и pkplpj переброской ребра pipj, мы создаем листья для двух новых треугольников pkpipl и pkplpj, и узлы треугольников pkpipj и pipjpl получают указатели на два новых листа. На рисунке (рис. 4) показан пример изменения в D, вызванного добавлением точки. Заметим, что когда мы делаем лист на внутреннем узле, он получает не более трёх исходящих указателей.
Используя дерево D, мы можем локализовать следующую точку pr, которая добавлена в текущей триангуляции. Это делается следующим образом. Мы начинаем в корне D, что соответствует первоначальному треугольнику p01p02p03. Мы проверяем три треугольника поддерева корня для того, чтобы увидеть, в каком треугольнике pr лежит, и спускаемся к соответствующему треугольнику потомка. Затем, проверив три треугольника поддерева этого узла, спускаемся к треугольнику потомка, который содержит точку pr, и так далее, до тех пор пока мы достигнем одного листа D. Этот лист соответствует треугольнику в текущей триангуляции, который содержит pr.
Рис. 4. Эффект добавления точки рr в треугольник 1
Поскольку любые узлы представляют собой не больше чем три листа, берётся линейное время для поиска в числе узлов, или, другими словами, в числе треугольников, сохраняемых в D, что содержит pr.
Алгоритм использует простую структуру данных. Если используется ацикличное дерево для хранения и поиска треугольника, тогда трудоёмкость алгоритма оценивается в среднем O (N log N). В худшем O (N2). Блок-схема алгоритма инкремента (рис. 5).
Рис. 5. Блок-схема алгоритма инкремента
Алгоритм “заметающей линии”. Идея алгоритма заметающей линии является весьма простой: во-первых, геометрические элементы сортируются. Тогда вообразим, что заметающая линия l скользит сверху вниз над плоскостью и останавливается на так называемых точках события. Часть проблемы решена, и структура данных обновляется. А другая часть проблемы остаётся не решенной до конца. Граница между решенной и нерешенной частью делится на так называемую береговую линию, которая состоит из связанных цепей параболических дуг (рис. 6).
Как заметающая линия движется через плоскость, так и береговая линия осуществляется в различных формах, контролирующих два типа событий. Первое событие, так называемое событие точки, появляется, когда заметающая линия попадает на новую точку из P. В этом случае вертикальная проекция сделана по цепочке параболических дуг, и новая параболическая дуга создана (рис. 7).
Рис. 6. Береговая линия вверх заметающей линии
Каждая парабола определяется по формуле (2)
i = y = 
, ( 2)
где ly – значение y-координат заметающей линии, pix, piy – значение координат любой точки pi на параболе.
Рис. 7. Береговая линия попадает на точку
Парабола определяется этим краем и находится на первой вырождающейся параболе с нулевой шириной: вертикальная линия подключает новый край на береговую линию. По мере того как заметающая линия продолжает двигаться вниз, новая парабола получается шире и шире. Часть новой параболы ниже старой береговой линии является одной частью новой береговой линии. Рис. 7 иллюстрирует этот процесс.
Рис. 8. Событие круга
Второе событие (так называемое событие круга) появляется, когда существующая дуга береговой линии уменьшается до точки и исчезает. Событие точки q на рис. 8 является центром круга вершин vi, vj, и vk, c самой низкой точки движения по заметающей линии. Таким образом, любая точка из P не может находиться внутри этого круга, который гарантирует ненарушение свойств пустого круга.
Блок-схема алгоритма заметающей линии (рис. 9).
Рис. 9. Блок-схема алгоритма заметающей линии.
Алгоритм заметающей линии является одним из самых популярных методов ускорения для построения триангуляции. Алгоритм заметающей линии выполняется очень быстро с трудоёмкостью O (N log N). Вычислительный алгоритм заметающей линии очень сложен.
Комбинация алгоритмов инкремента и заметающей линии. Идея комбинации алгоритмов инкремента и заметающей линии является весьма простой: рассмотрим рис. 10 и предположим, что заметающая линия s движется снизу вверх и уже проходит 15 первоначальных точек. Окружение алгоритма является двумя полилиниями:
- нижняя полилиния (представлена линией точка-тире на рис. 10) состоит из частей выпуклой оболочки. Назовем её нижняя выпуклая оболочка.
- верхняя полилиния (представлена пунктирной линией) рассматривается как продвижение фронта. Продвижение фронта отделяет вершины заметающей и вершины незаметающей. Форма продвижения фронта зависит от расположения точек, которые уже заметены.
Нижняя выпуклая оболочка и продвижение фронта имеют точно две совместных вершины с минимальной и максимальной x-координатой (вершины 4 и 7 на рис. 10а). Все точки между нижней выпуклой оболочкой и продвижением фронта являются триангуляциями, соответствующими свойству пустого круга (условие Делоне).
Рис. 10. Основная идея алгоритма
Когда заметающая линия встречает очередную точку (вершина 15 на рис. 10б), алгоритм выполняется следующим образом: вначале делается вертикальная проекция вершины 15 на продвижении фронта. Она попадает на ребро 14,11. В этом случае легко построить новый треугольник 15,11,14 и заменить продвижение фронта, что соответствует новой ситуации (рис. 10б). К сожалению, нет гарантии, что новый треугольник 15,11,14 допустим, и необходимо проверить его с соседом 8,14,11, соответствуют ли они свойству пустого круга. Как видно на рис. 10в, свойство пустого круга нарушено, и диагональ изменена. На рис. 10г показана ситуация после того, как точки заметены.
Для комбинации алгоритма инкремента и заметающей линии нужно выполнить следующие операции.
1. Инициирование
Сортировка исходных точек относительно y-координат. Инициируют продвижение фронта и нижней выпуклой оболочки из двух первоначальных точек. Вершины в продвижении фронта и нижней выпуклой оболочке расположены относительно x координаты.
2. Триангуляция
Очередная точка v проектируется вертикально на продвижении фронта. Возможем один из четырёх случаев:
- проекция попадает на продвижение фронта,
- проекция не попадает на продвижение фронта,
- точка v локализуется на продвижении фронта,
- точка v совпадает с одной из вершин на продвижении фронта.
а. Проекция попадает на продвижение фронта.
Одно ребро продвижения фронта, на которое попадает вертикальная проекция точки v, определяет две вершины выражения L и R, как на рис. 11а. Легко построить новый треугольник v,R,L. От вершины L соседнего треугольника k,L,R исходит прямое влияние, и надо проверить рекурсивно условие Делоне. Продвижение фронта обновляется вставкой вершины v между вершиной L и R (рис. 11б).
Рис. 11. Продвижение фронта попадает на точку
Рассмотрим угол между векторами, который определяется вершинами v, R, R1 на рис. 11б. Если значение угла меньше, чем 3/4, то строим еще треугольник v,R1,R (рис. 11в). Проверим условие Делоне для нового треугольника с двумя соседними треугольниками v,R,L и R1,l,R. Удалим вершину R из продвижения фронта (рис. 11в) и повторим процесс для v, R1, R2, пока угол между ними не будет больше, чем 3/4 (рис. 11г). Треугольники, полученные таким способом, резко нарушают условие Делоне.
б. Проекция не попадает на продвижение фронта.
Очередная точка v проектируется вертикально на продвижении фронта и, возможно, не попадает на левостороннее и правостороннее продвижения фронта. На рис. 12 показан случай непопадания v на левостороннее продвижение фронта. В этом случае новый треугольник v,L1,L построен и проверен условием Делоне. Новый треугольник на правостороннем продвижении фронта порождён как случай, когда проекция попадает на продвижение фронта.
Рис. 12. Проекция не попадает на продвижение фронта
в. Точка v локализуется на продвижении фронта.
Рис. 13. Решение особого случая
Этот случай появляется, когда вершины v, L и R имеют одинаковую координату y. В этом случае разделим треугольник L,R,k на два треугольника L,v,k и v,R,k (рис. 13). Оба треугольника согласованы с соседними треугольниками и вершина v вставлена между L и R.
г. Точка v совпадает с одной из вершин на продвижении фронта.
В этом случае точка v пропущена, и следующая точка взята непосредственно.
3. Окончание
Когда все точки добавлены, несколько вершин продвижения фронта остаются вогнутыми и несколько треугольников еще не построены (рис. 14а). При решении этой проблемы можно применять алгоритм сканирования Грэхема. Полные триангуляции Делоне показаны на рис. 14б.
Рис. 14. Переход продвижения фронта до верхней выпуклой оболочки
Структуры данных. Продвижение фронта определяется простой хэш-таблицей (hash-table) c двусвязным списком структуры (рис. 15).
Рис. 15. Сохранение продвижения фронта
Вершины в продвижении фронта расположены относительно x-координаты. Каждая запись продвижения фронта сохраняет ключ (Key), индекс вершины (vi) и индекс треугольника (Ti), который использует совместные ребро с продвижением фронта.
Данные точки и треугольники представляются обычной структурой “Узлы и треугольники”. В структуре “Узлы и треугольники” для каждого треугольника хранятся три указателя на образующие его узлы и три указателя на смежные треугольники. При 8-байтовом представлении координат (x, y, h) и 4-байтовых представлении указателей данная структура “узлы и треугольники” требует (24·N + 24·M) байт (где N – число исходных точек, M – число треугольников, M 2·N - 5).
Блок-схема комбинации алгоритмов “инкремента и заметающей линии” на рис. 16.
Рис. 16. Блок-схема комбинации алгоритмов инкремента и заметающей линии.
Анализ алгоритма. Во-первых, сортировка всех исходных точек, соответствующих y координате. Используя QuickSort, сортировка выполняется в T1 времени, определяемом по формуле (3)
T1 = O(N log N), ( 3)
где N является числом исходных точек для триангуляции.
Вторая часть алгоритма, то есть построение триангуляции, оценивает следующее. Вход на хэш-таблице для каждой точки выполняется в константе времени. Предполагаем, что элемент на хэш-таблице HashSize, HashSize > 0, и m вершин на продвижении фронта. Для локализации ребра на продвижении фронта в среднем является m / HashSize. Новый треугольник порождён и проверен по условию Делоне, эти операции сделаны за одинаковое время. Легализация новых треугольников выполняется в логарифмическом времени. Сумма времени во второй части вычисляется по формуле:
T2 = N (m / HashSize + log N). (4)
Обычно m << N и HashSize >> 1. В случае (m / HashSize) << N и можно опускать (m / HashSize), тогда
T2 = O (N log N). (5)
Общее время для процесса алгоритма таково:
Tоб. = T1 + T2 = O (N log N) + O (N log N) = O (N log N). (6)
Алгоритм комбинации инкремента и заметающей линии имеет много преимуществ: прост в реализации; используются простые структуры данных, и они не требуют большой дополнительной памяти для своей работы; один из самых быстродействующих (на практике) из алгоритмов построения триангуляции Делоне, трудоёмкость O (N log N).
Большую часть времени выполнения алгоритмов занимает время нахождения треугольника, содержащего новую точку. Время нахождения треугольника зависит от количества треугольников. В среднем случае алгоритм “инкремента” нужно находить в 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.
Рис. 18. График времени работы алгоритмов
Время работы алгоритмов не только зависит от количества исходных данных, но и от распределения точек (рис. 19).
Рис. 19. Распределение разных точек:
а - униформа; б - гауссово; в - гроздь; г - сетка.
В таблице 2 приведено время работы алгоритмов в зависимости от распределений исходных данных.
Таблица 2
| Распределения точек (100 000 точек) | Время работы алгоритмов (секунды) | ||
| Инкремент | Заметающая линия | Комбинация “инкремента и заметающей линии” | |
| Униформа | 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 XP, приведён в таблице 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 XP, приведён в таблице 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 XP, приведён в таблице 5.
Таблица 5
| № | Количество точек | Время работы программ (секунды) | |
| MapStudio | Land Desktop 2005 | ||
| 1 | 261 788 | 2.184 | 7.0 |
| 2 | 1 541 000 | 15.773 | 45.0 |
Таким образом, скорость выполнения нашей программы значительно выше по сравнению с другими программами.
Создание прикладных инструментов в программе построения цифровых моделей рельефа.
Интерполяция высот. Эта операция позволяет вычислить значение высоты поверхности для любой заданной плановой точки. Например, в треугольнике M1(X1, Y1, Z1), M2(X2, Y2, Z2), M3(X3, Y3, Z3) требуется вычислить высоту ZP точки P(XP, YP, ZP) на рис. 20.
Рис. 20. Интерполяция высоты точки Р
Построение профилей. Одной из базовых задач анализа триангуляционных поверхностей является построение профилей. Результатом этой работы будет вертикальный профиль (рис. 21).
Рис. 21. Построение профилей разрезов поверхности
Построение изолиний. Результат построения изолиний показан на рис. 22, трудоёмкость алгоритма, очевидно, является линейной относительно размера триангуляции.
Рис. 22. Построение изолиний
Построение изоконтуров. Изоконтурами между уровнями h1 и h2 называется геометрическое место точек на поверхности, имеющих высоту h є (h1, h2). Результат построения изоконтуров показан на рис. 23.
Рис. 23. Построение изоконтуров по модели рельефа
ОБЛАСТИ ПРИМЕНЕНИЯ РЕЗУЛЬТАТОВ РАБОТЫ
Методы построения цифровых моделей рельефа, созданные с применением разработанного алгоритма, могут применяться в областях:
- Создание прогнозных пространственных моделей с учетом характерных особенностей ландшафта.
- Вычисление геометрических характеристик (площади, протяженности, периметра) с учетом рельефа для нужд архитектуры и городского планирования, инженерных изысканий, картографии, навигации.
- Расчет крутизны склонов, мониторинг и прогнозирование геологических и гидрологических процессов, например, зон затопления паводковыми водами или смыв плодородного слоя почв для сельского хозяйства и другое.
- Расчет освещенности и ветрового режима для архитектуры и городского планирования, инженерных изысканий, экологического мониторинга.
- Построение зон видимости для телекоммуникационных и сотовых компаний, архитектуры и городского планирования.
- Ортотрансформирование материалов аэрофотосъемки и космической съемки.
- Формирование атрибутивных и геометрических характеристик при создании и обновлении цифровых топографических карт.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
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.
