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

На правах рукописи

Чернова Лидия Ивановна

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

Специальность: 05.13.18 — «Математическое моделирование, численные методы и комплексы программ»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Иркутск - 2006

Работа выполнена в ГОУ ВПО «Иркутский государственный технический университет»

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

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

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

доктор технических наук, профессор Массель Людмила Васильевна

кандидат технических наук, доцент Науменко Александр Иванович

Ведущая организация: Сибирская государственная геодезическая академия

Зашита состоится 22 декабря 2006 г. в 10 часов на заседании диссертационного совета Д 2L8.004.01 при Иркутском государственном университете путей сообщения по адресу:

<>¿4074, Иркутск, ул. Чернышевского,! 5, ауд. А-803.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Иркутский государственный университет путей сообщения».

Автореферат разослан 22 ноября 2006 г.

Ученый секретарь диссертационного совета д-р техн. наук, профессор

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

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

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

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

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

Основополагающий вклад в теорию моделирования рельефа внесли работы Ю.Л. Костюка, В.Я. Цветкова, A.B. Скворцова, А.Л. Фукса, С.А. Жихарева. Вопросы геоинформатики и картографирования рассмотрены в работах A.M. Берлянта, B.C. Тикунова, К.Л, Проворова, Е.Г, Капралова, A.A. Лютого, A.B. Кошкарева, И.Г. Журкина, В.Я. Цветкова, В.А. Коугия, В.П. Кулагина. Визуализацией в reo информатике занимались: ВЛ. Цветков, СИ. Матвеев, Б.А. Левин, У .Д. Ниясгулов, A.C. Масленников, A.M. Берлянт, B.C. Тикунов, Е.Г. Капралова, A.A. Лютый, A.B. Кошкарев, И.Г. Журкин, В.А. Коугия, В.П. Кулагин. Вопросами обработки изображений в аспекте визуального моделирования занимались: В.Я. Цветков, С.И. Матвеев, Ю.Г. Якушенков, Л.М. БугаевскиЙ, В.П. Павлов, И.Г. Журкин. Аппроксимация функций подробно отражена в работах Ю.Ф. Мухопада, ЮЛ. Кеткова, П.Ж. Лорана и др.

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

Предметом исследования являются цифровые модели рельефа.

Объект исследования. Объектом исследования являются

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

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

Научная новизна н защищаемые научные положения.

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

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

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

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

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

На защиту выносятся:

1. Новая методика нелинейного сглаживания и представления цифровой модели рельефа с использованием теории полюсов.

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

2. Обоснование метода моделирования «изломов» топографической поверхности на основе расщепления вершин вдоль структурных линий рельефа в рамках обшей нелинейной модели.

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

Практическая значимость н реализация работы. Результаты работы могут быть использованы при алгоритмизации решения инженерных задач по топографическим поверхностям. Основные положения работы реализованы в программном обеспечении «Гео», которое применяется для обработки геодезических съемок камеральным подразделением предприятия ФГУП Госзем кадастр съемка - В ИСХАГИ (Восточно-Сибирский филиал).

Апробация работы. Основные результаты работы докладывались и обсуждались на: региональной научно-практической конференции с международным участием "Геодезия, картография, кадастр земель Прибайкалья" (Иркутск, 2004 г.); региональной научно-практической конференции ФГУП Госземкадастрсъемка - ВИСХАГИ "Организация и проведение мониторинга земель" (Иркутск, 2004 г.); 2-й региональной научно-практической конференции "Геодезия, картография, кадастровое и маркшейдерское дело в освоении природных ресурсов Байкальского региона" (Иркутск, 2006 г.); научном конгрессе "ГЕО-Сибирь-2006" (Новосибирск, ССГА, 2006 г.); заседании объединенного семинара кафедр ИрГУПС.

Публикации. По теме диссертации опубликовано 9 работ, из них 7 авторских.

Структура н объем диссертации. Диссертационная работа состоит из введения, четырех глав и заключения. Работа содержит 123 страницы машинописного текста, 54 рисунка и 12 таблиц. Библиографический список включает 13S наименований.

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

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

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

Обычно первичные данные с использованием тех или иных операций приводят к одному из двух наиболее широко распространенных представлений поверх но ста в ГИС: растровому представлению модели (матрица рельефа) и триангуляционному (TIN). Матрица рельефа представляет собой регулярную двумерную таблицу, коордннатно-привязанную к местности, в ячейках которой хранятся значения высот, соответствующие либо центру ячейки, либо среднему значению высоты по площади данной ячейки. Триангуляционная модель представляет собой сеть треугольников, опирающихся своими вершинами на нерегулярно

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

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

Анализ и синтез моделируемых поверхностей показал, что на сегодняшний день имеется большое количество программ, позволяющих создавать и редактировать трёхмерные поверхности. Рельеф в этих программах может быть представлен: в виде изолиний, с помощью полосовых контуров (contour bands), а также в трехмерном виде.

Установлено, что в основном эти представления не совсем корректно передают действительную, реальную поверхность Земли, как следствие, -требуется разработка методов качественного формирования ЦМР.

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

Предложен метод кусочно-нелинейной интерполяции ЦМР. Предполагается, что ничейная интерполяция цифровой модели выполняется на основе триангуляции Делоне, а кусочно-нелинейная - функцией 3-го порядка для каждого треугольника. Для «гладкого склеивания» нелинейных функций 3-го порядка на уровне касательных (первых производных) необходимо иметь значения этих производных в узлах интерполяции. Значение первой производной для нелинейной функции поверхности в точке р определяет положение нормали к поверхности в этой точке.

Кусочно-нелинейная интерполяция ЦМР рассматривается поэтапно.

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

На основе теории полюсов, для каждого треугольника определяются нелинейные, гладко склеенные на уровне касательных с соседями функции 3-го порядка.

Для иллюстрации рассматриваются плоские кусочно-нелинейный кривые (двумерный случай) с обобщением этих представлений на соответствующие функции поверхности. Одним из ' распространенных подходов к кусочно-нелинейной интерполяции является метод, основанный на построении сплайнов (spline). С точки зрения механики сплайн является

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

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

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

Для сравнения отметим, что для кубического сплайна (рис. 1) задача решается в два этапа. На первом этапе для каждой вершины сплайна определяются положения нормалей к кривой, затем для каждого участка формируются кубические параболы (рис.2).

Рис. I. Кубический сплайн (а) и профильная кривая (б)

Значения коэффициентов а, Ь, с и Ы уравнения кубической параболы у = ахъ+Ьх*+сх+Ы определяются из решения четырех уравнений ~ два уравнения функции и два уравнения касательных:

у, = ох;' + Ьх' +£*,+</ у, = о*2 + Ьх* + агг + </ #(£,) = За*,1+2йх, +с = + 2Ьхг + с

Здесь ^- = tg(g) = За*1 + 2&с+с - уравнение касательной, полученное в

сЬг

результате дифференцирования уравнения кубической параболы. Для известныхзначениЯх!,^,*:,^г и tg(gг}, tg (g1} получит

в - 7—цг(- + /£(£>) + , с - ) ,

V *г3

Ь - . ' - > -«(г.)] -

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

нормалей определяются автоматически, исходя из «похожих» упругих свойств сплайна. Однако при этом не учитываются специфика результатов топографических съемок и неупругий характер топографических кривых. Выбор пикетов для формирования ЦМР определяется не случайным образом, а избирательно, то есть в первую очередь снимаются характерные точки перегиба рельефа (точки экстремума), а остальные точки заполняют пространство между ними. На примере построения профильной линии рельефа (см. рис.1,6) показано, что кубический сплайн (см .рис.1,а) неверно интерполирует результаты топографической съемки. Для данных топографической съемки, очевидно, что пикет 3 — вершина, а пикет 4 ~ низина топографической кривой. Поэтому других точек экстремума в их окрестности быть не должно; они сами являются таковыми, и значения первой производной в этих точках должно равняться нулю (вертикальная нормаль). В кубическом сплайне в окрестности пикетов 3 и 4 формируются новые значения точек экстремума, отличных от этих пикетов.

"Ч, >

Т

Рис. 2. Кубическая парабола Формальное использование сплайнов может приводить к ошибочным с точки зрения топографии результатам. Учитывая, во-первых, «избирательный», а не случайный характер распределения пикетов рельефа, а во-вторых, «неупругий» характер топографической кривой, в диссертации предлагается назначить для пикетов 3 и 4 конкретное (вертикальное) положение нормали, а не определять их из уравнения «упругой балки». Пикет 2 является «точкой склона», для которого, следуя принципу равных влияний направлений, вполне допустимо назначение нормали вдоль биссектрисы угла 1-2-3.

Предлагается алгоритм формирования нормалей по чередованию знаков соседних превышений. Формально алгоритм определяется в работе как подсчет п - числа чередования знаков превышений:

м«0 — низина или вершина, нормаль с координатам» N (0,0,1)-, п=2 — «точка склона» с к смежными треугольниками,

нормаль = =

п>2 — (п/2)~главая седловина, нормаль с координатами N(0,0,1);

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

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

В основании теории полюсов лежит понятие характеристической фигуры. Так для кривой на участке АО (рис.3) характеристической фигурой является ломаная АВСО с полюсами А, В, С и О.

■ Рис, 3. Характеристическая фигура АВСО

Ребра АВ и СО в проекции на образующую линию (АО) составляют треть длины отрезка АО и по направлению совпадают с касательными к кривой в точках А и й. Уравнение кривой /(I) задается параметрически, где значение параметра I изменяется от 0 до 1. ^

Рис. 4. Вычисление значения функции по характеристической фигуре

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

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

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

параметры 0>и (3 • барицентрические координаты точки р (рис.6).

Рис. Поверхность 3-го порядка (а) и ее характеристическая фигура б) а) б)

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

На первом этапе с помощью барицентрических координат I,, /3 для каждого треугольника характеристической фигуры (рис.б.а) определяются вершины характеристической фигуры 2-го порядка (рис.б,б). На втором этапе по /¡, ¡2, /э и фигуры 2-го порядка (рис.б,б) находятся вершины фигуры 1-го порядка (рис.б,в). На третьем этапе по ¡г, и треугольнику фигуры 1-го порядка (рис.б,в) находятся координаты точки р на поверхности 3-го порядка.

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

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

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

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

Предложенный подход, опирающийся на «метод полюсов», не имеет перечисленных недостатков H позволяет качественно решать задачи топографии на ЦМР; может послужить также основой для задачи сгущения ЦМР. Использование «метода полюсов» вызывает необходимость хранить значения нормалей в съемочных пикетах (если это не точка экстремума). Это приводит к дополнительным затратам памяти, но при пространственном отображении ЦМР на компьютерах (обычно такие программы для 3D визуализации используют OpenGL или Direct3D из состава DirectX) все равно необходимо формировать нормали в узлах триангуляции. При отсутствии информации о нормалях системы 3D визуализации определяют их как среднее значение нормалей по граням, инцидентным данному узлу. Непосредственный ввод значений нормалей позволяет более качественно выполнять 3D визуализацию ЦМР.

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

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

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

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

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

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

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

Точка с индексом т+1 не лежит на прямой из первых т точек, поэтому можно сформировать веер из т-1 треугольников с основанием в вершине т+1(рис.7). Частным случаем такого веера является один треугольник с т-2.

Рис. 7. Стартовый веер триангуляции

Предложенный метод, используемый для триангуляции точек, поясняется при анализе 1-го шага процесса (рис.8).

Рис. 8. Пример формирования триангуляции

Для любого шага триангуляции справедливы следующие утверждения;

1. Ребра граней, ограничивающие триангуляцию, формируют выпуклую границу. Это утверждение очевидно, так как стартовый веер имеет выпуклую границу. Любое присоединение новой точки тоже выполняется до образования новой выпуклой границы. При этом к триангуляции присоединяется новый веер граней Ье&п-епЛ-г (рис.8).

2. Любая присоединяемая точка лежит вне выпуклой границы триангуляции. Это условие обеспечивается в результате заданного лексикографического порядка сортировки на этапе фильтрации точек.

После каждого шага присоединения точки выполняется оптимизация формы граней из веера Ьг&п-етЛА. Оптимизация строится на основании сравнения двух смежных граней, где сравниваются длина их общего ребра с расстоянием между несвязанными вершинами (рнс.9). Осуществляется попытка соединить эти несвязанные вершины. Если общее ребро и условная связь между вершинами пересекаются и длина условной связи короче общего ребра, то осуществляется перестройка общего четырехугольника. Общее ребро удаляется и устанавливается новое ребро на место условной связи.

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

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

Алгоритм триангуляции можно представить следующим образом:

1. Формирование стартового веера граней.

2. Цикл по множеству точек (исключая точки стартового веера). Для точки i-й точки и выпуклой границы поиск начала и конца (begin, end) нового веера. Поиск начинается с точки i-1, так как она лексикографически (но не геометрически) - самая ближайшая к i точка.

3. Присоединение к треугольникам веера begin-end-i.

4. Оптимизация треугольников веера begm-end-i.

5. Изменение выпуклой границы. Теперь она проходит через вершины begjn-end-i.

Конец цикла.

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

1

Рис, 10. Оконтуривание выпуклой границы триангуляции

На рисЛО представлены результаты триангуляции: слева - триангуляция без оконтуривания с выпуклой внешней границей, справа - результат охонтуриеания с невыпуклой внешней границей.

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

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

2. Для каждого ребра вычислить вес, в качестве которого используется длина ребра (точнее, квадрат этого расстояния).

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

4. Выполнить циклическую процедуру:

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

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

Особенности предложенного алгоритма триангуляции следующие:

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

2). Формирование триангуляции развивается в положительном направлении координатной оси X (для сортировки х-у-2, а для сортировки по у-х-г - по оси У) и по всей ширине фронта. Процедура позволят легко расщеплять модель на фрагменты заданного размера в направлении триангуляции. Необходимо отметить, что сама реализация алгоритма не зависит от порядка сортировки х-у или у-х.

3). Алгоритм - условно оптимальный в части геометрии граней. Оптимизация выполняется на ограниченную глубину. Однако число неогтшальных граней по тестовым расчетам не превышает 1-2%.

Оценка .качества получаемых результатов.

Качество результатов гарантируется; предлагаемая методика обработки исключает следующие ошибки:

критические ошибки пересечения изолиний ЦМР;

несовпадение исходных точек экстремума (вершины, низины) и этих же точек для сглаженных поверхностей;

ошибки «укладки горизонталей» (плавного изменения заложения горизонталей), которые зависят от плавного изменения первых производных от функции поверхности;

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

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

Блок-схема построения ЦМР представлена на рис. II, где каждый блок представляет отдельный алгоритм:

Рис. 11. Алгоритм построения цифровой модели рельефа А) - ввод данных о пикетах топографической съемки; сц. способ съемки ( автоматизированный или избирательный); Аг - построение ЦМР - триангуляция пикетов по условно-оптимальному алгоритму;

Аз - построение ЦМР (триангуляция Делоне с ограничениями - структурными линиями рельефа);

А4 - Окошуривание выпуклой внешней границы триангуляции;

А$ - анализ вершин триангуляции и назначение для них нормалей к поверхности по вариациям знаков превышений;

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

А? - объединение фрагментов изолиний в по ли лини и и назначение им атрибутов в зависимости от типа горизонталей - основные или выделенные; Ag - вывод результатов обработки.

Четвертая глава посвящена вопросам машинного эксперимента и анализу представленных поверхностей. Для подтверждения теоретических разработок и установления их практической значимости выполнен комплекс экспериментальных исследований. В результате определена эффективность предложенных методики и программно-реализованных алгоритмов создания ЦМР. В качестве исходных данных было отобрано четыре репрезентативных участка местности. Тестирование поверхностей производилось среди поверхностей, построенных в наиболее популярных (при производстве топографических съемок) программных комплексах: Карта - 2000, GeoniCS, Credo, Photomod,

На рис. 12 - рис.14 показаны технология оценивания и типичные ошибки построения горизонталей тестируемых программных средств.

Рис. I I. Пример критичных и некритичных ошибок: эталонные горизонтали и горизонтали, построенные в ГИС Карта-2000, сплайном. Тест-

объект «Ольхой»

Рис. 12. Пример хорошей укладки горизонталей программой ОеотСЭ н программой ГЕО

Рис. 14. Некритичная ошибка; нет укладки горизонталей (СеошСБ, сплайн). Ошибка - 0,5 сечения горизонталей

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

горизонтали, построенные путем сечения сознанной цифровой поверхности, не пересекаются по определению;

укладка горизонталей плавная, корректная, отвечающая нормативным документам Роскартографии;

высокая адекватность созданной ЦМР топографической поверхности.

Заключение

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

1. Разработана методика кусочно-нелинейной интерполяции цифровой модели рельефа на основе теории полюсов. Дано теоретическое обоснование методики определения первых производных интерполяционных функций для геодезических съемочных пикетов с учетом особенности их распределения. Выполнена алгоритмизация вычислительного процесса по построению гладких изолиний.

2. В рамках предложенной кусочно-нелинейной интерполяции разработан метод моделирования «изломов» топографической поверхности на основе расщепления вершин вдоль структурных линий рельефа.

3. Разработай алгоритм триангуляции больших объемов съемочных пикетов (3-5 млн.) для автоматизированных геодезических съемок (лазерное сканирование). Разработан алгоритм оконтуриваиия выпуклых границ триангуляции при формировании ЦМР. Выполнен сравнительный анализ качества различных интерполяционных решений при построении изолиний. Сформулирован ряд критериев оценки качества таких задач.

Основные положения работы реализованы в программном обеспечении «Гео», которое применяется для обработки геодезических съемок камеральным подразделением предприятия ФГУП Госземкадастрсьемка ВИСХАГИ (Восточно-Сибирский филиал).

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Чернова Л.И., Кошечкин И.С.. Кусочно-нелинейная интерполяция цифровой модели рельефа / Л.И. Чернова, И.С. Кошечкин // Вестник ИрГТУ,-2004.-№1. - С. 39-44.

2. Чернова Л.И.. Теория полюсов, использованная при создании цифровой модели рельефа /Л.И. Чернова // Проблемы освоения минеральной базы Восточной Сибири,- Иркутск, 2004. - Вып.4,- С.328 - 332. ^

3. Чгрнояа Л.И., Кошечкин И.С.. Использование кусочно-нелинейной интерполяции для 3D — визуализации цифровой модели рельефа / Л.И. Чернова, И.С. Кошечкин // Организация и проведение мониторинга земель. — Москва - Иркутск, 2004. - С.61 -65.

4. Чернова Л.И.. Топологический анализ модели для создания ЦМР/Л.И. Чернова И Проблемы освоения минеральной базы Восточной Сибири. — Иркутск, 2005. - Вып. 5. -С. 171- 175.

5. Чернова Л.И.. Алгоритм оконтуривания выпуклой границы триангуляции /Л.И. Чернова // Проблемы освоения минеральной базы Восточной Сибири, — Иркутск, 2005. - Вып. 6. -С. 17- 21.

6. Чернова Л.И.. Триангуляция для задач топологического анализа автомэтизиро ванных съемок /Л.И. Чернова // Информационные и математические технологии в науке, технике и образовании: труды X Байкальской Всерос. конф., Иркутск, 24 — 25 май. 2005 г. - Иркутск, 2005. — Ч, II. -С.160-165.

7. Чернова Л.И.. Критерии оценки качества рельефа /Л.И. Чернова // Геодезия, картография, кадастр в освоении природных ресурсов Байкальского региона: материалы 2 регион, научно-практ. конф., Иркутск, 23 - 24 март. 2006 г. Иркутск,2006. - С.60-63.

8. Чернова Л.И.. Оконтуривание выпуклой границы триангуляции пикетов/Л.И. Чернова // ГЕО — СИБИРЬ - 2006: материалы межд. научн. конгресса, Новосибирск, 24-28 апр. 2006 г. — Новосибирск, 2006.—Т. 1. —Ч, 1,-С.121-125.

9. Чернова Л.И.. Интерполяция поверхности /Л.И. Чернова // ГЕО -СИБИРЬ - 2006: материалы межд. научн. конгресса., Новосибирск, 24-28 апр. 2006 г. - Новосибирск, 2006. -Т. 1.-Ч. J. - C.125-I29.

Подписано в печать 17.11.2006. Формат 60x84/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1,25. Уч.-изд. л. 1,5. Тираж 100 экз. Зак. 533. Поз. плана 23н.

ИД №06506 от 26.12.2001 Иркутский государственный технический университет 664074. г. Иркутск, ул. Лермонтова, 83

Перечень условных обозначений

Введение

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

1.1. Модели рельефа.

1.2. Способы задания поверхностей

1.3. Теория полюсов.

Выводы по главе

Постановка задачи.

2. Алгоритмы и методы построения поверхностей

2.1. Метод кусочно-нелинейной интерполяции ЦМР

2.2. Алгоритм кусочно-нелинейного сглаживания топографических поверхностей.

2.3. Алгоритм вычисления нормалей вершин триангуляции.

2.4. Метод кусочно-нелинейного сглаживания граней триангуляции.

Выводы по главе 2.

3. Модели и методы оптимизации в задачах триангуляции пикетов

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

3.2. Алгоритм оконтуривания группы пикетов

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

Выводы по главе.

4. Экспериментальные исследования алгоритмов и методики моделирования рельефа

4.1. Существующие технологии отображения рельефа на картографических материалах и создание ЦМР.

4.2. Обоснование метода оценки способов моделирования земной поверхности

4.3. Использованные критерии и технологии оценки способов создания ЦМР.

4.4. Сравнительный анализ результатов экспериментального тестирования.

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

В настоящее время, как правило, на территорию крупных городов имеются «бумажные» топографические планы масштаба 1:500, а на некоторые объекты -масштаба 1:200. Точность таких планов в целом удовлетворяет требованиям большинства потребителей (проектные, строительные и эксплуатирующие организации). Однако многие проектные организации работают с передовыми системами автоматизированного проектирования (САПР). Проектирование с помощью современных профессиональных САПР дает возможность создать на базе проектно-конструкторской документации такую информационную систему, которая позволяет отслеживать текущее состояние всех конструктивных и технологических элементов зданий и сооружений, оперативно вносить изменения и выдавать по запросу пользователя всю необходимую информацию, включая графическую. Кроме того, многие параметры (например, габариты) напрямую связаны с геометрией того или иного объекта, что предполагает их автоматическую коррекцию при изменении объекта на чертеже.

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

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

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

Очевидно, что для эффективного проектирования сооружений и инженерных сетей необходим переход к трехмерным моделям топографических данных. Это выражается в создании цифровой модели местности (ЦММ), под которой в соответствии с ГОСТ 22268-76 понимается «множество элементов топографо-геодезической информации о местности и правила обращения к ней». ЦММ представляет собой объединение цифровой модели рельефа земной поверхности (ЦМР) с моделью инженерного назначения — электронным планом. Насколько точно модель рельефа будет передавать действительную поверхность, настолько точно будут решаться инженерные задачи.

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

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

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

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

Основополагающий вклад в теорию моделирования рельефа внесли работы Ю.Л. Костюка, В.Я. Цветкова, А.В. Скворцова, A.JI. Фукса, С.А. Жихарева. Вопросы геоинформатики и картографирования рассмотрены в работах A.M. Берлянта, B.C. Тшсунова, K.JI. Проворова, И.Г. Журкина, Е.Г. Капралова, А.А. Лютого, А.В. Кошкарева, А.П. Гука, Е.А. Жалковского, Д.В. Лисицкого, А.И. Мартыненко, В.П. Савиных, B.C. Тикунова, А.К., Черкашина В.Я. Цветкова, В.А. Коугия, В.П. Кулагина. Проблемой визуализации в геоинформатике занимались

В.Я. Цветков, СИ. Матвеев, Б.А. Левин, У.Д. Ниясгулов, А.С. Масленников, A.M. Берлянт, B.C. Тикунов, Е.Г. Капралова, А.А. Лютый, А.В. Кошкарев, И.Г. Журкин, В.А. Коугия, В.П. Кулагин. Вопросы обработки изображений в аспекте визуального моделирования изучали В.Я. Цветков, СИ. Матвеев, Ю.Г. Якушенков, Л.М. Бугаевский, В.П. Павлов, И.Г. Журкин. Аппроксимация функций подробно отражена в работах Ю.Ф. Мухопада, Ю.Л. Кеткова, П.Ж. Лорана и др.

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

Предметом исследования являются цифровые модели рельефа.

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

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

Научная новизна и защищаемые научные положения.

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

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

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

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

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

На защиту выносятся:

1. Новая методика нелинейного сглаживания и представления цифровой модели рельефа с использованием теории полюсов.

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

2. Обоснование метода моделирования «изломов» топографической поверхности на основе расщепления вершин вдоль структурных линий рельефа в рамках общей нелинейной модели.

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

Практическая значимость и реализация работы. Результаты работы могут быть использованы при алгоритмизации решения инженерных задач по топографическим поверхностям. Основные положения работы реализованы в программном обеспечении «Гео», которое применяется для обработки геодезических съемок камеральным подразделением предприятия ФГУП Госземкадастрсъемка - ВИСХАГИ (Восточно-Сибирский филиал).

Апробация работы. Основные результаты работы докладывались и обсуждались на: региональной научно-практической конференции с международным участием "Геодезия, картография, кадастр земель Прибайкалья" (Иркутск, 2004 г.); региональной научно-практической конференции ФГУП Госземкадастрсъемка - ВИСХАГИ "Организация и проведение мониторинга земель" (Иркутск, 2004 г.); 2-й региональной научно-практической конференции "Геодезия, картография, кадастровое и маркшейдерское дело в освоении природных ресурсов Байкальского региона" (Иркутск, 2006 г.); научном конгрессе "ГЕО-Сибирь-2006" (Новосибирск, ССГА, 2006 г.); заседании объединенного семинара кафедр ИрГУПС.

Публикации. По теме диссертации опубликовано 9 работ, из них 7 авторских.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав и заключения. Работа содержит 123 страницы машинописного текста, 54 рисунка и 12 таблиц. Библиографический список включает 135 наименований.

Выводы по главе 4

Результаты экспериментальных исследований, выполненных на основе метода тестового сравнения программных средств построения ЦМР на примере репрезентативных участков местности, позволяют сделать следующие выводы:

1. Разработанные в предыдущих главах диссертационной работы методика и программно-реализованные алгоритмы обеспечивают создание цифровых моделей рельефа, которые отвечают заданным требованиям гладкости и согласованности структуры моделей при достаточной их адекватности исходным топографическим поверхностям. Укладка построенных с использованием ПС ГЕО горизонталей - плавная, корректная, согласованная между соседними горизонталями, отвечающая нормативным требованиям Роскартографии.

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

3. Получена хорошая адекватность ЦМР, созданной в ПС ГЕО, эталонному тестовому образцу, не уступающая лучшим на сегодняшний день программным продуктам, повсеместно используемым в топографо-геодезическом производстве.

4. Доказана состоятельность и практическая значимость подхода создания ЦМР методом кусочно-нелинейной интерполяции с использованием алгоритмов кусочно-нелинейного сглаживания и формирования нормалей к поверхностям.

ЗАКЛЮЧЕНИЕ

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

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

2. В рамках принятой кусочно-нелинейной модели разработан подход к моделированию «изломов» топографической поверхности на основе расщепления вершин вдоль структурных линий рельефа.

3. Разработан эффективный алгоритм триангуляции больших объемов съемочных пикетов (3-5 млн. пикетов) для автоматизированных геодезических съемок (например, лазерное сканирование). Разработан алгоритм оконтуривания выпуклых границ триангуляции при формировании ЦМР. Выполнен сравнительный анализ качества различных интерполяционных решений при построении изолиний. Сформулирован ряд критериев оценки качества таких задач.

Основные положения работы реализованы в программном обеспечении «ГЕО », которое применяется для обработки геодезических съемок камеральным подразделением предприятия ФГУП Госземкадастрсъемка -ВИСХАГИ (Восточно-Сибирский филиал).

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

1. Алберг Дж. Теория сплайнов и ее приложения / Дж, Альберг. Э. Нильсон, Дж. Уолш.- М.: Мир, 1972.-316 с.

2. Аммерал Л. Принципы программирования в машинной графике /Л. Аммерал. — М.: Сол. Систем, 1992.- 224с.

3. Ахо А. Построение и анализ вычислительных алгоритмов/ А. Ахо, Д. Хопкрофт, Д. Ульман ; пер. с англ.- М.: Мир, 1979,- 536 с.

4. Бахвалов Н.С. Численные методы /Н. С. Бахвалов, Н. П. Жидков, Г. М. Кобельков.—М.: Наука, 1987.- 598с.

5. Берлянт A.M. Картография. Толкование основных терминов/А. М. Берлянт // Программно-аппаратное обеспечение, фонд цифрового картографического материала, услуги и нормативно-правовая база геоинформатики : ежегод. обзор. М., 1998. - Вып.З. - С. 91-104.

6. Бирюков B.C. Анализ технических средств получения цифровой информации о рельефе по фотоснимкам /В. С. Бирюков, В. А. Радионов, В. А. Авдеев // Изв. вузов. Геодезия и аэрофотосъемка.-2001.- №1.- С. 19-22.

7. Бобков В.А. Способы обработки данных о рельефе/В. А. Бобков, С. Б. Белов, С. А. Кадничанский // Геодезия и картография.- №6.- 1995.- С. 37-41.

8. Борисов А.В. Обзор инструментальных средств создания ГИС- приложений / А. В. Борисов // Программно-аппаратное обеспечение, фонд цифрового материала, услуги, нормативно-правовая база геоинформатики : ежегод. обзор. -М., 1996.-Вып. 2,- С. 151-202.

9. Бронштейн И.Н. Справочник по математике для инженеров и учащихся втузов / И. Н. Бронштейн, К. А. Семендяев. -М.: Наука, 1986.- 544с.

10. Ю.Бугаевский Л. М. Геоинформационные системы : учеб. для вузов / Л. М.

11. Бугаевский, В. Я. Цветков. М.: Златоуст, 2000.- 224 с. П.Вабищевич П. Н. Численное моделирование: учеб. пособие /П. Н. Вабищевич . — М.: МГУ, 1993,— 152 с.

12. Вилкас Э.Й. Решения: теория, информация, моделирование / Э. Й. Вилкас, Е.

13. Майминас . М.: Радио и связь, 1981. -328 с.

14. Вирт Н. Алгоритмы и структуры данных / Н. Вирт ; пер. с англ.-М.: Мир, 1989.- 360 с.

15. Геоинформатика. Толковый словарь основных терминов /Ю. Б. Баранов и др.. М.: ГИС - Ассоциация, 1999.-204 с.

16. Девис Дж. Статистика и анализ геологических данных / Дж. Девис; перевод с англ. В.А. Голубевой.-М.: Мир, 1977. 575 с.

17. Делоне Б.Н. О пустоте сферы /Б. Н. Делоне // Изв. АН СССР.- 1934, Вып.4.- С. 793 800.

18. Дзядык В. К. Введение в теорию равномерного приближения функций полиномами / В. К. Дзядык. — М.: Наука, 1977.- 508 с.

19. Дорофеюк А. А. Методы кусочной аппроксимации многомерных кривых /А. А. Дорофеюк, А. Г. Дмитриев // Автоматика и телемеханика.- 1984- № 12.-С. 43-51.

20. Дорофеюк А. А.Применение методов автоматической классификации для построения статистической модели объекта/ А. А. Дорофеюк, А. Д. Косовин, И. Ш. Торговицкий // Автоматика и телемеханика.- 1970.- № 2. С. 44-49.

21. Ершов В. В. Автоматизация геолого-маркшейдерских графических работ / В.В. Ершов и др.. -М.: Недра, 1990. 348 с.

22. Жалковский Е.А. Цифровая картография и геоинформатика / Е. А. Жалковский и др.. М.: Картоцентр-Геодезиздат, 1999.- 44 с.

23. Жихарев С.А. Моделирование рельефа в системе ГрафИн /С. А. Жихарев, А. В. Скворцов // Геоинформатика: Теория и практика. Томск, 1998. -Вып. 1.-С. 194-205.

24. Завьялов Ю. С. Сплайны в инженерной геометрии /Ю. С. Завьялов, В. А. Леус, В. А. Скороспелое. — М.: Машиностроение, 1985,- 221 с.

25. Зайцев В.М. Построение карт, изолиний по стереомодели местности с помощью ЦВМ / В.М. Зайцев, B.C. Лаврова, А.А. Чигирев// Геодезия и картография, 1973. -№ 4. С. 48 -53.

26. Иванов А.П. Упрощенный метод аппроксимации рельефа без учета геоморфологии местности / А.П. Иванов, В.В. Яхман // Тр. НИИПГ, 1979. -№ 3. С. 113-122.

27. Инструкция по топографической съемке в масштабах 1:5000, 1:2000, 1:1000 и 1:500.- М.: Недра, 1985.- 152с.

28. Инструментарий геоинформационных систем /под ред. Б. С. Бусыгин. -Киев: ИРГ «ВБ», 2000.- 172 с.

29. Информационный бюллетень ГИС-ассоциации. 1997.-N 4(11).- 63 с.

30. Исаев В. К. О приближении функций сплайнами первой степени / В. К. Исаев, С. А. Плотников // Методы сплайн-функций в числовом анализе.-Новосибирск, 1983.-С.48—56.

31. Калиткин И. Н. Численные методы /Н. Н. Калиткин.— М.: Наука, 1978.152 с.

32. Капралов Е. Г. Введение в ГИС : учеб. пособие / Е. Г. Капралов, Н. В. Коновалова. Петрозаводск: Изд-во Петрозаводского ун-та, 1995.- 148 с.

33. Кетков Ю. Л. Об оптимальных методах кусочно-линейной аппроксимации / Ю. Л. Кетков // Изв. вузов. Радиофизика.- 1966.- Т. 9, N 6. С. 54-61.

34. Кнут Д. Искусство программирования: в 3 т. /Д. Кнут.- М.: Вильяме, 2000. Т. 3: Сортировка и поиск. - 832 с.

35. Копченова Н. В. Вычислительная математика в примерах и задачах/ Н. В. Копченова, И. Марон. — М.: Наука, 1972.- 367с.

36. Корн Т. Справочник по математике для научных работников и инженеров/

37. Т.Корн, Г. Корн . — М.: Наука, 1974.- 832 с.

38. Костюк Ю.Л. Построение цифровой модели рельефа местности на основе структурных линий и высотных отметок / Ю.Л. Костюк, А.Л. Фукс, Ф. Препарата; перевод с англ. Ф. Препарата, М. Шеймос.- М.: Мир, 1989.- 478 с.

39. Костюк Ю.Л. Визуально гладкая аппроксимация однозначной поверхности, заданной нерегулярным набором точек/Ю. Л. Костюк, А. Л. Фукс // Геоинформатика-2000: тр. межд. науч.-практ. конф. (Томск, сент. 2000 г.). -Томск, 2000.-с. 17-21.

40. Костюк Ю.Л. Представление рельефа земной поверхности в геоинформационных системах/Ю. Л. Костюк // Геоинформатика-2000: тр. межд. науч.-практ. конф. (Томск, сент. 2000 г.). Томск, 2000. - с. 42-45.

41. Костюк Ю.Л. Приближенное вычисление оптимальной триангуляции /Ю. Л. Костюк, А. Л. Фукс // Дискретный анализ и исследование операций : мат-лы межд. конф. (Новосибирск, 26 июня 1 июля 2000 г.). - Новосибирск, 2000.- С. 152.

42. Костюк Ю.Л. Предварительная обработка исходных данных для построения цифровой модели рельефа местности/ Ю. Л. Костюк, А. Л. Фукс // Вестник ТГУ.- 2003.- № 280.- С. 281-285.

43. Кошкарев А. В. Региональные геоинформационные системы / А. В. Кошкарев, В. Л. Каракин. М.: Наука, 1987. - 126 с.

44. Кошкарев А.В. Геоинформатика /А. В. Кошкарев, В. С. Тикунов ; под ред. Д.В.Лисицкого. М.: Картгеоцентр - Геоиздат, 1993. - 213 с.

45. Ковалевский В.А. Методы оптимальных решений в распознавании изображений / В.А. Ковалевский. -М.: Наука, 1976. 120 с.

46. Кравченко ЮЛ. Методы моделирования топографических поверхностей / Ю.А. Кравченко, М.:ЦНИИГАиК, 1984.-Вып. 1.-67 с.

47. Кулагин В.П. Новые информационные технологии и геоинформационные технологии /В. П. Кулагин, В. Я. Цветков // Информационные технологии.-2002.-№2,- С. 52-55.

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

49. Лоран П. Ж. Аппроксимация и оптимизация /П. Ж. Лоран.- М.:Мир, 1975.496 с.

50. Лурье И.К. Основы геоинформатики и создание ГИС. Дистанционное зондирование и географические информационные системы /И. К. Лурье ; под ред. А. М. Берлянта. М: ООО ИНЕЭКС - 2,2002. - 4.1. - 140 с.

51. Мазина А.С. Исследование технологии визуального моделирования в геинформатике: дис. канд. техн. наук: 25.00.35 Электронный ресурс. -М.: РГБ, 2005.

52. Максудова Л. Г. Информационное моделирование как фундаментальный метод познания /Л. Г. Максудова, В. Я. Цветков // Геодезия и аэрофотосъемка.- 2001,- №1.-С. 102-106.

53. Марчук Г. И. Методы вычислительной математики / Г. И. Марчук. М.: Наука, 1980,- 535 с.

54. Математика и САПР: в 2 кн. / П. Шенен и др.; пер. с франц.-М.: Мир, 1988.-Кн. 1.-206 с.

55. Мительман Е.Я. Исследование метода аппроксимации рельефа местности мультиквадриковыми функциями / Е.Я. Мительман. М.: ЦНИИГАиК, 1974. -Вып.211. - С. 76-87.

56. Мусин О. Р. Цифровые модели для ГИС / О. Р. Мусин // Информац. бюл. -1998,-№4 (16).- С. 30.

57. Мухопад Ю.Ф. Таблично-алгоритмический метод кодирования информации / Ю.Ф. Мухопад, Т.Б. Агафонов // Информационные системы контроля и управления на транспорте : сб. статей. Иркутск, 2002. - Вып.9. - С. 29-33.

58. Наумова В.В. Концепция создания региональных геологических ГИС ( на примере ГИС Минеральные ресурсы, минералогинезис и тектоника СевероВосточной Азии) : дис. . д-ра геол.-минерал. наук: 25.00.35/ В. В. Наумова. М.: РГБ, 2006.-244 с.

59. Неумывакин АЛО. О построении структурно-цифровой модели рельефа /А.Ю. Неумывакин, А.Ф. Яковлев //Геодезия и картография, 1986. -№. 2. С. 34-38.

60. Рийбман Н.С. Идентификация технологических объектов методами кусочной аппроксимации / Н. С. Рийбман, А. А. Дорофеюк, А. Д. Касавин.— М.: Ин-т проблем упр., 1977.- 108 с.

61. Роджерс Д. Алгоритмические основы машинной графики / Д. Роджерс .- М.: Мир, 1989.- 503 с.

62. Роджерс Д.Ф. Математические основы машинной графики / Д. Ф. Роджерс, Дж. А. Адаме. М.: Машиностроение, 1980.- 240 с.

63. Самарский А. А. Введение в численные методы /А. А. Самарский.— М.: Наука, 1982,- 271 с.

64. Симкин Б А. Аналитическое моделирование месторождений и их открытой разработки / Б.А. Симкин, Ю.К. Шкута. -М.: Наука, 1976. -152 с.

65. Скворцов А.В. Особенности реализации алгоритмов построения триангуляции Делоне с ограничениями /А. В. Скворцов // Вестник ТГУ.2002.- № 275.-С. 90-94.

66. Скворцов А.В. Построение триангуляции Делоне за линейное время / А. В. Скворцов // Изв. вузов. Физика.- 1999.- № 3.- С. 120-126.

67. Скворцов А.В. Применение триангуляции для решения задач вычислительной геометрии /А. В. Скворцов, Ю. JI. Костюк // Геоинформатика. Теория и практика. Томск: Изд-во Томск, ун-та, 1998. -Вып. 1.-С. 22-47.

68. Скворцов А.В. Применение цифровых моделей рельефа для задач планирования территории /А. В. Скворцов, С. А. Жихарев, A. JI. Фукс // ИНПРИМ-98: материалы межд. конф. (Новосибирск, 28 29 апр. 1998 г.). -С. 65.

69. Скворцов А.В. Триангуляция Делоне и её применение/А. В. Скворцов. -Томск: Изд-во Томск, ун-та, 2002.- 127 с.

70. Скворцов А.В. Эффективные алгоритмы построения триангуляции Делоне/ А. В. Скворцов, Ю. JI. Костюк // Геоинформатика: Теория и практика. Томск: Изд-во Томск, ун-та, 1998. Вып. 1. - С. 22^17.

71. Сплайн-функции и их приложения: сб. науч. тр.- Новосибирск: ИМ СО РАН, 1997.-Вып. 159.-228 с.

72. Стечкин С. Б. Сплайны в вычислительной математике /С. Б. Стечкин, Ю. Н. Субботин .—М.: Наука, 1976.- 248 с.

73. Соболевский П.К. Современная горная геометрия / П.К. Соболевский// Социалистическая реконструкция и наука. 1932. - № 7. - С. 42-78.

74. Фоли Д. Основы интерактивной машинной графики / Д. Фоли , ван Дэм А. -М.: Мир, 1985.-368 с.

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

76. Хмелен А. К. Методы приближения функции и кривых сплайнами с минимальным числом узлов и приложения к задаче формированияповерхностей моделей J1A : дис. . канд. физ.-мат. наук: 25.00.35 / А. К. Хмелен.-М., 1989.- 179 с.

77. Цветков В.Я. Визуальное моделирование в геоинформатике/ В. Я. Цветков, А. С. Мазина //Геодезия и аэрофотосъемка,- 2004,- №5.- С. 128-136.

78. Цветков В.Я. Геоинформационные системы и технологии /В. Я. Цветков . -М: Финансы и статистика, 1998.-286 с.

79. Цветков В.Я. Геоинформационные системы и технологии/В. Я. Цветков. М.: МГУГиК, 2000. - 69 с.

80. Чекалин В.Ф. Ортофототрансформирование фотоснимков / В.Ф. Чекалин. -М.: Недра, 1986.- 168 с.

81. Чернова Л.И. Интерполяция поверхности по методу полюсов /Л. И. Чернова, Ю. Ф. Мухопад // Информационные системы контроля и управления в промышленности и на транспорте. Иркутск, 2006.- Вып.14,- С. 30-35.

82. Чернова Л.И., Кошечкин И.С. Использование кусочно-нелинейной интерполяции для 3D визуализации цифровой модели рельефа / Л.И. Чернова, И.С. Кошечкин // Организация и проведение мониторинга земель. -Москва - Иркутск, 2004. - С.61 - 65.

83. Чернова Л.И., Кошечкин И.С. Кусочно-нелинейная интерполяция цифровой модели рельефа / Л.И. Чернова, И.С. Кошечкин // Вестник ИрГТУ.-2004,- №1. С. 39-44.

84. Чернова Л.И. Алгоритм оконтуривания выпуклой границы триангуляции /Л.И. Чернова // Проблемы освоения минеральной базы Восточной Сибири. -Иркутск, 2005.-Вып. 6. -С. 17-21.

85. Чернова Л.И. Интерполяция поверхности /Л.И. Чернова // ГЕО СИБИРЬ -2006: материалы межд. научн. Конгресса (Новосибирск, 24-28 апр. 2006 г.). -Новосибирск, 2006. - Т. 1. - Ч. 1. - С. 125-129.

86. Чернова Л.И. Критерии оценки качества рельефа /Л.И. Чернова // Геодезия, картография, кадастр в освоении природных ресурсов Байкальского региона:материалы 2 регион, научно-практ. конф. (Иркутск, 23 24 март. 2006 г. ). -Иркутск,2006. - С.60-63.

87. Чернова Л.И. Оконтуривание выпуклой границы триангуляции пикетов/JI.И. Чернова // ГЕО СИБИРЬ - 2006: материалы межд. научн. конгресса (Новосибирск, 24-28 апр. 2006 г.). - Новосибирск, 2006. -Т. 1. - Ч. 1. - С.121-125.

88. Чернова Л.И. Теория полюсов, использованная при создании цифровой модели рельефа /Л.И. Чернова // Проблемы освоения минеральной базы Восточной Сибири.- Иркутск, 2004. Вып.4 - С.328 - 332.

89. Чернова Л.И. Топологический анализ модели для создания ЦМР/Л.И. Чернова // Проблемы освоения минеральной базы Восточной Сибири. -Иркутск, 2005. Вып. 5. - С. 171- 175.

90. Шикин Е. В. Начала компьютерной графики/Е. В. Шикин, А. В. Боресков , А. А. Зайцев .-М.:Диалог-МИФИ, 1993,- 138с.

91. Шумилов Б. М. О локальной аппроксимации сплайнами первой степени /Б. М. Шумилов // Методы сплайн-функций. Новосибирск, 1978. - Вып. 75. -С. 57-63.

92. Ягодина Л.Л. Моделирование поля рельефа с помощью ортофотогональных полиномов Чебышева /Л.Л. Ягодина // Вестник Ленинградского университета.-1972. №24. - С. 136-142.

93. Ястребов А. И. Модификация триангуляции Делоне для создания моделей рельефа/ А. И. Ястребов, А. В. Рогачев // Геодезия и картография. 2005. - № 1.-471 с.

94. Ahlberg J.K. et al. The Theory of Splines and their Applications, N. Y., 1967.

95. Barnhill R. E. Representation and approximation of surfaces. In Mathematical Software III, New York, 1977.

96. Barnhill R. E. et al. Computer Aided Geometric Design (Proceedings of the Conference held at the University of UTAH SALT LAKE CITY, 1974).

97. Bohm W. Inserting new Knots into (3-spline Curves, Computer Aided Design, 12, p. 199-201, 1980.

98. Bonham-Carter, G.F. Geographic Information Systems for Geoscientists: Modelling with GIS; Computer Methods in the Geosciences. Pergamon Press (Elsevier Science Ltd.), New York. 1994.

99. Floriani L.De, P.Magillo, E. Puppo Selective Refinement of Surface Meshes: Data Structures and Algorithms, 1998.

100. Floriani L.De, P.Magillo, E. Puppo, 1997, Building and traversing a surface at variable resolution, Proceedings IEEE Visualization'97, Phoenix, AZ

101. Floriani L.De, P.Magillo, E. Puppo A Formal Approach to Multiresolution Hypersurface Modeling.

102. Forrest A. R. Computational Geometry, Proc. Royal Soc. London A, 1971.

103. Forrest A. R. The twisted Cubic Curve, A Computer Aided Geometric Design Approach, CAD, 12, p. 165-172, 1980.

104. Garland M., Heckbert P. Fast Triangular Approximation of Terrain and Height Fields. Course Notes for SIGGRAPH'97. LosAngeles, 1997.

105. Gordon W. J., Hall C. A. Exact Matching of Boundary Conditions and Incorporations of semi quantitative Solution Characteristics in initial Approximations toBoundary value Problems, J. Comput. Phys., 25, No. 2, p. 151-162, 1977.

106. Gunter Seeber. Satellite geodesy. Walter De Gruyter. New York, 1993.

107. Jonathan Richard Shewchuk Delaunay Refinement Algorithms for Triangular Mesh Generation, Computational Geometry: Theory and Applications 22(1-3):21-74, May 2002.

108. Klein R., Kramer J. Building multiresolution models for fast interactivevisualization, In Proceedings of the SCCG, 1997.

109. Klein R., Kramer J. Multiresolution representations for surfaces meshes. In Proceedings of the SCCG, 1997, pp. 57-66.

110. Moore I.D., Grayson R.B., Ladson A.R. Digital terrain modeling a review of hydrological, geomorphological and biological applications // Hydrol. Proc. 1991. N5, P. 3-30.

111. Pike R.J. Geomorphometry-progress, practice, and prospect // Z. Geomorph. Suppl. 1995. Vol. 101. P. 221-238.

112. Puppo E. Variable Resolution of Terrain Surfaces. Proceedings Eight Canadian Conf. on Comp.Geom., pp.202-210, 1996

113. Puppo E., Scopigno R., 1997, Simplification, LOD and multiresolution -Principles and applications, Eurographics'97 Tutorial Notes

114. Schoenberg I. J. Cardinal Interpolation and Spline Functions, Journal of Approximation Theory 2, p. 167-206, 1969.

115. Schroeder W.J. A Topology Modifying Progressive Decimation Algorithm. Course Notes for SIGGRAPH'97. Los Angeles, 1997.

116. Schroeder W.J., Zarge J.A., Lorensen W.E. Decimation of triangle meshes. Computer Graphics 26(2): 65-70, July 1992.121. http://www.cgal. org

117. Дмитрий Пауков. Демонстрация алгоритма триангуляции Делоне http://www.uran.donetsk.ua/MHasters/2003/fvti/paukov/librai'y/trifl ash.htm

118. Отдел геоинформсистем и цифровой картографии ГлавНИВЦ http://arcserver.gbdgi.ru

119. Геоинформационные системы, http://www.dataplus.ru/

120. Оптимальная триангуляция. http://search.rambler.ru/srch?oe=l 251 &words=%CE%EF%F2%E8%EC%E0%E B%FC%ED%E0%FF+%F2%F0%E8%E0%ED%E3%F3%EB%FF%F6%E8%FF &hilite=0C69AD75

121. GEOPROFI.RU Электронный журнал по геодезии, картографии и навигации, http://www.geoprofiли/

122. Сайт Autodesk, http; www.autodesk.com

123. Сайт ГИС-Ассоциации ГИС-Иркутск.иг1 http://gisa2.gubkin.ru/gis-irkutsk.html

124. Триангуляция Делоне http://www.tcen.ru/~max/bk2site/Delaunay/index.html

125. Скворцов А.В http://www.tsu.ru/

126. Создание ЦМР http://ru.innoter.com/Page/dem.htm132. http://www.brgm.fr/geofrance3d/geofrance3d.html

127. Чесалов JI. ГИС и картография, 2004 http://www.dataplus.ru

128. Петренко Д. А. Сравнение триангуляций с помощью хеш функций / Д. А. Петренко, А. В. Скворцов, Р. О.Куленов www.indorsoft.ru 263 КБ • 12.05.2003

129. Петренко Д.А., Мирза Н.С., Скворцов А.В. Взаимодействие объектов в системе автоматизированного проектирования IndorCAD http://onti.tpu.ru