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

ВВЕДЕНИЕ.

Глава 1. ПОСТРОЕНИЕ ТРИАНГУЛЯЦИИ ДЕЛОНЕ.

1.1. Введение.

1.1.1. Диаграмма Вороного и триангуляция Делоне.

1.1.2. Свойства триангуляции Делоне.

1.1.3. Структуры данных для представления триангуляции

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

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

1.3. Практическая реализация алгоритма.

1.4. Вычислительный эксперимент.

1.5. Выводы.

Глава 2. ПРИБЛИЖЕННОЕ ВЫЧИСЛЕНИЕ

ОПТИМАЛЬНОЙ ТРИАНГУЛЯЦИИ.

2.1. Введение.

2.2. Локальные приближенные алгоритмы построения оптимальной триангуляции.

2.3. Экспериментальное исследование локальных перестроений на плоскости.

2.4. Экспериментальное исследование локальных перестроений на однозначной поверхности.

2.5. Выводы.

Глава 3. ПОСТРОЕНИЕ СЕЧЕНИЙ

ОДНОЗНАЧНОЙ ПОВЕРХНОСТИ.

3.1. Введение.

3.2. Построение коридора для изолиний.

3.3. Построение ломаной минимальной длины в коридоре.

3.4. Сглаживание ломаной минимальной длины кривыми Безье.

3.5. Сглаживание ломаной минимальной длины локальными сплайнами.

3.6. Построение визуально гладкой коридорной кривой.

3.7. Выводы.

Глава 4. ГЛАДКАЯ ИНТЕРПОЛЯЦИЯ

ОДНОЗНАЧНОЙ ПОВЕРХНОСТИ.

4.1. Введение.

4.2. Расчет нормальных векторов в узлах сетки.

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

4.4. Выводы.

Глава 5. РЕАЛИЗАЦИЯ И ИСПОЛЬЗОВАНИЕ АЛГОРИТМОВ

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

5.1. Введение.

5.2. Исходные данные и их топологическая корректность.

5.3. Триангуляция с ограничениями.

5.4. Быстрая проверка топологической корректности и правильности задания высот.

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

5.6. Преимущества использования предложенных алгоритмов в системах моделирования рельефа.

5.7. Выводы.

Актуальность проблемы

В последнее десятилетие интенсивно развиваются самостоятельные и актуальные направления информатики - геоинформатика и вычислительная геометрия. Новые методы и алгоритмы, применяемые в геоинформационных системах (ГИС), способствуют повышению скорости обработки данных, появлению новых функциональных возможностей и расширению областей применения этих систем. В большинстве случаев объекты исследования современных ГИС считаются планарными, но часто они характеризуются не только привязкой на плоскости, но и значениями пространственно распределенных параметров (например, температуры, уровня загрязнения или просто высот точек). Если каждой точке на плоскости XOY соответствует только одно значение параметра, то такая зависимость описывается некоторой функцией z = F{х, у) и может быть представлена трехмерной однозначной поверхностью.

Как правило, исследуемая поверхность задается некоторым нерегулярным набором точек большого объема. В качестве ограничений на форму поверхности дополнительно могут быть заданы структурные линии поверхности. Наиболее сложной по форме и количеству ограничений, а также наиболее часто используемой поверхностью является земной рельеф. Поэтому самые развитые многофункциональные ГИС, а также системы обработки данных дистанционного зондирования включают программные компоненты для построения и анализа рельефа [9, 17, 30, 46, 61, 65, 66, 86, 134, 135, 137].

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

Цифровая модель позволяет получать производные данные для анализа поверхности: вычислять углы наклона и экспозиции склонов, выделять зоны видимости, выпуклости и вогнутости, строить изолинии и профили поперечных сечений, вычислять объемы, расстояния и площади на поверхности, проводить интерполяцию высот, визуализацию и другие операции. Цифровая модель рельефа необходима также для построения ортофотопланов местности на основе космо- и аэроснимков [13, 30, 31, 35, 86].

Для получения треугольной сетки в плоскости XOY строится триангуляция по проекциям исходных точек. Задание высот в вершинах триангуляции определяет систему пространственных треугольников - простейшую кусочно-линейную интерполирующую поверхность [9, 17, 25, 30, 35, 66, 77, 84, 89,90, 103, 120,142].

При переходе от исходных точек к прямоугольной сетке необходимо рассчитать высоты в ее узлах. Для этого обычно применяются различные алгоритмы локальной аппроксимации и интерполяции по значениям высот в нескольких соседних исходных точках [1, 3, 17, 25, 29, 30, 35, 65, 77, 84, 103, 121, 142].

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

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

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

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

1. На хранение треугольной сетки требуется много памяти (примерно 1 Мбайт на каждые 10000 исходных точек). В современных компьютерах, имеющих большую оперативную память, эта проблема снимается, если треугольная сетка строится настолько быстро, что ее выгоднее рассчитывать повторно, чем сохранять в файле.

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

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

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

Методы исследования

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

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

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

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

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

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

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

Практическая ценность

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

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

Пакет программ построения изолиний и разрезов был внедрен вместе с базовой системой обеспечения графического вывода СМОГ на ряде предприятий, где он применялся в научных исследованиях. Комплекс программ построения цифровых моделей рельефа использовался при выполнении работ по созданию цифровых карт местности для республик Алтай и Хакасия, одного из районов Красноярского края, а также города Томска. Кроме того, материалы исследований использовались при чтении курса лекций «Вычислительная геометрия и интерактивные графические системы» на факультете информатики Томского госуниверситета. Апробация и публикации

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

1. V региональной научно-практической конференции «Молодые ученые и специалисты - ускорению научно-технического прогресса» (Томск, 1986).

2. Всесоюзной научно-технической конференции молодых ученых и специалистов «Проблемы совершенствования управления народным хозяйством на основе средств вычислительной техники (Управление-86)» (Москва, 1986).

3. Всесоюзной конференции «Методы и средства обработки сложной графической информации» (Горький, 1988).

4. Международной конференции «ИНПРИМ-98» (Новосибирск, 1998).

5. Международной конференции «Дискретный анализ и исследование операций» (Новосибирск, 2000).

6. Международной научно-практической конференции «Геоинформатика-2000» (Томск, 2000).

7. Сибирской конференции «Методы сплайн-функций» (Новосибирск, 2001).

По результатам выполненных исследований опубликовано 19 печатных работ [7, 8, 13, 19-24, 26-28, 43, 52-57], среди них 7 статей, 3 доклада, 7 тезисов и 2 информационных листка ЦНТИ. Структура диссертации

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

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

Во второй главе исследуется задача приближенного построения оптимальной триангуляции. Наиболее известным в настоящее время алгоритмом решения данной задачи является жадный алгоритм, имеющий временную сложность 0{n2\ogn) и емкостную сложность 0(п2). Вопросы получения приближенного решения на основе быстрых локальных проверок исследованы недостаточно. Предлагаются простые локальные алгоритмы перестроения начальной триангуляции Делоне, позволяющие за время 0(п) получить триангуляцию с весом, близким к весу жадной триангуляции и даже более низким. Рассматривается также обобщение этих алгоритмов для триангуляции точек, расположенных на однозначной поверхности z = F(x,y). Приводятся результаты вычислительного эксперимента для плоского и пространственного случая. Результаты, полученные автором, опубликованы в работах [22, 24].

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

В четвертой главе проведен анализ существующих методов гладкой интерполяции поверхности на треугольной сетке. Из-за большого числа ячеек сетки алгоритмы сглаживания должны быть только локальными и, по возможности, простыми в вычислительном отношении. Для поверхностей, используемых в геоинформационных системах, не требуется обеспечивать высокий порядок гладкости, обычно достаточно только непрерывности наклона. В качестве наиболее подходящих предлагается применять кубические поверхности Кунса или Безье, для расчета которых достаточно определить касательные плоскости (направление нормальных векторов касательных) во всех узлах сетки. Для обеспечения возможности выбора наиболее подходящей формы интерполирующей поверхности приводятся 5 способов расчета нормалей касательных. Описывается метод расчета касательных при моделировании разрыва наклона поверхности на заданной линии. Разработан алгоритм, позволяющий заменять поверхность Кунса или Безье, построенную на треугольной сетке с п узлами, кусочно-линейной поверхностью с предельным числом вершин N > п, которая будет визуально настолько близка к гладкой, насколько это позволяет значение N. Результаты, полученные автором, опубликованы в работах [27, 28].

Пятая глава посвящена вопросам практической реализации предложенных алгоритмов в комплексе программ построения цифровых моделей рельефа. Разработаны эффективные алгоритмы триангуляции с двумя типами ограничений, задаваемых структурными линиями поверхности. Предлагаются методы проверки топологической корректности и правильности задания высот исходных линий и точек. Описываются разработанные комплексы программ, проведен анализ преимуществ использования треугольной сетки и предложенных алгоритмов для решения основных задач обработки и анализа рельефа. Результаты, полученные автором, приводятся в работах [7, 8, 13, 19, 20, 43, 52].

5.7. Выводы

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

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

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

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

151—

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

-152-ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

1. Аронов Б.С. Методы математической обработки геологических данных на ЭВМ. - М.: Недра, 1977. - 184 с.

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

3. Баяковский Ю.М., Галактионов В.А., Михайлова Т.Н. Графор. Графическое расширение фортрана. М.: Наука. Гл. ред. физ.-мат. лит., 1985. -288 с.

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

5. Гаек Я., Шидак 3. Теория ранговых критериев. М.: Наука, 1971.

6. Гилой В. Интерактивная машинная графика: Структуры данных, алгоритмы, языки. Пер. с англ. М.: Мир, 1981. - 384 с.

7. Иваненко С.А. Адаптивные сетки и сетки на поверхности // Ж. вычисл. матем. и матем. физ., Т. 33, № 9, 1993, с. 1333-1351.

8. Иванов В.П., Батраков А.С. Трехмерная компьютерная графика. / Под ред. Г.М. Полищука. М.: Радио и связь, 1995. - 224 с.

9. Иванов В.П., Рюмкин А.И., Фукс A.JT. Построение электронных моделей территории г. Томска на основе высокодетальной космосъемки // Геоинформатика: Теория и практика. Выпуск 1. Томск: Изд-во Томск, ун-та, 1998, с. 235-244.

10. Ильман В.М. Алгоритмы триангуляции плоских областей по нерегулярным сетям точек // Алгоритмы и программы, ВИЭМС. Вып. 10(88). М.: 1985, с. 3-35.

11. Ильман В.М. Экстремальные свойства триангуляции Делоне // Алгоритмы и программы, ВИЭМС. Вып. 10(88). М.: 1985, с. 57-66.

12. Кнут Д. Искусство программирования для ЭВМ. Т.З. Сортировка и поиск. -М.: Мир, 1978.-848с.

13. Ковин Р.В., Марков Н.Г. Цифровые модели рельефов в среде ГИС Maplnfo Professional // Геоинформатика-2000. Труды межд. научно-практ. конф. -Томск: Изд-во Томск, ун-та, 2000, с. 96-101.

14. Костюк Ю.Л. Применение сплайнов для изображения линий в машинной графике // Автоматизация эксперимента и машинная графика. Томск: Изд-во Томск, ун-та, 1977, с. 116-130.

15. Костюк Ю.Л., Фукс А.Л. Генерализация кривых в иллюстративной машинной графике // Методы и средства обработки сложной графической информации. Тезисы докладов Всес. конференции. Горький: Изд-во Горьковского ун-та, 1988, ч. 1, с. 84.

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

17. Костюк Ю.Л., Фукс А.Л. Построение и аппроксимация изолиний однозначной поверхности, заданной набором исходных точек // Геоинформатика: Теория и практика. Выпуск 1. Томск: Изд-во Томск, ун-та. 1998, с. 119-126.

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

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

20. Костюк Ю.Л., Фукс А.Л. Гладкая аппроксимация изолиний однозначной поверхности, заданной нерегулярным набором точек // Геоинформати-ка-2000. Труды межд. научно-практ. конф. Томск: Изд-во Томск, ун-та, 2000, с. 37-41.

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

22. Кошель С.М., Мусин О.Р. Методы цифрового моделирования: кригинг и радиальная интерполяция // Информационный бюллетень ГИС-ассоциации, № 4(26)-5(27), 2000, с. 32-33.

23. Кошкарев А.В., Тикунов B.C. Геоинформатика. М.: Картгеоцентр-Геодезиздат, 1993. - 213 с.

24. Кравцова В.И. Космические методы картографирования. М.: Изд-во МГУ, 1995.-240 с.

25. Лавров Е.И. Автоматизированная генерализация линейных элементов гидрографии // Геодезия и картография, № 11, 2000, с. 38-45.

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

27. Лисейкин В.Д. Обзор методов построения структурных адаптивных сеток //Ж. вычисл. матем. и матем. физ., Т. 36, № 1, 1996, с. 3-41.

28. Лисицкий Д.В. Основные принципы цифрового картографирования местности. М.: Недра, 1988. - 259 с.

29. Математика и САПР: В 2-х кн. Кн. 1. Пер. с франц. / Шенен П., Коснар М., Гардан И. и др. М.: Мир, 1988. - 204 с.

30. Математика и САПР: В 2-х кн. Кн. 2. Пер. с франц. / Жермен-Лакур П., Жорж П., Пистр Ф., Безье П. М.: Мир, 1989. - 264 с.-15838. Норри Д., де Фриз Ж. Введение в метод конечных элементов. М.: Мир, 1981.-304 с.

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

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

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

34. Салищев К.А. Картоведение. М.: Изд-во МГУ, 1976. - 439 с.

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

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

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

38. Скворцов А.В. Система ГрафИн // Геоинформатика: Теория и практика. Выпуск 1. Томск: Изд-во Томск, ун-та. 1998, с. 181-192.

39. Справочник по прикладной статистике. В 2-х т. Т. 1: Пер. с англ. / Под ред. Э. Ллойда, У. Ледермана, Ю.Н. Тюрина. М.: Финансы и статистика, 1989. -510 с.

40. Справочник по прикладной статистике. В 2-х т. Т. 2: Пер. с англ. / Под ред. Э. Ллойда, У. Ледермана, С.А. Айвазяна, Ю.Н. Тюрина. М.: Финансы и статистика, 1990. -526 с.

41. Стренг Г., Фикс Дж. Теория метода конечных элементов. М.: Мир, 1977. - 349 с.-15950. Фокс А., Пратт М. Вычислительная геометрия: Применение в проектировании и на производстве. М.: Мир, 1982. - 304 с.

42. Фоли Дж., вэн Дем А. Основы интерактивной машинной графики: В 2-х книгах. Кн. 2. Пер. с англ. М.: Мир, 1985. - 368 с.

43. Фукс A.JI. Пакет программ «Изолинии». Томск: Томский ЦНТИ, 1985. -4 с. - (Информационный листок № 17-85).

44. Фукс А.Л. Кусочно-линейная интерполяция и графическое отображение поверхности, заданной нерегулярной системой отсчетов. М. - 1985 - 18 с. - Рукопись представлена редкол. журн. «Изв. АН СССР. Техн. кибернетика". Деп. в ВИНИТИ 12 мая 1985, № 3227-85 Деп.

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

46. Фукс A.JI. Быстрый алгоритм триангуляции Делоне. // Методы и средства обработки сложной графической информации. Тезисы докладов Всес. конференции. Горький: Изд-во Горьковского ун-та, 1988, ч. 1, с. 83.

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

48. Фукс A.JI. Быстрый алгоритм триангуляции Делоне, основанный на предварительной обработке набора точек // Геоинформатика-2000. Труды межд. научно-практ. конф. Томск: Изд-во Томск, ун-та, 2000, с. 45-50.

49. Чеботарев А.С. Геодезия, ч. 1. М.: Изд-во геодезич. литературы, 1955. -627 с.

50. Шикин Е.В., Боресков А.В. Компьютерная графика. Динамика, реалистические изображения. М.: ДИАЛОГ-МИФИ, 1995. - 288 с.

51. Шикин Е.В., Плис Л.И. Кривые и поверхности на экране компьютера. Руководство по сплайнам для пользователей. М.: ДИАЛОГ-МИФИ, 1996. -240 с.-16061. Vertical Mapper. Модуль трехмерного анализа для Maplnfo. http://www.esti-map.ru/vertmap.htm.

52. Abdelli Н. Bivariate interpolation of extension modified Akima procedure // Indian J. Pure and Appl. Math., Vol. 29, № 2, 1998, pp. 151-161.

53. Akima H. A method of bivariate interpolation and smooth surface fitting for irregulary distributed data points // ACM Trans, for Math. Software, № 4, 1978, pp. 148-159.

54. Anglada M.V., Garcia M.P., Crosa P.B. Directional adaptive surface triangula-tion // Comput. Aided Geom. Des., Vol. 16, № 2, 1999, pp. 107-126.

55. ARC/INFO User's Guide: Cell-based Modeling with GRID. Environmental Systems Research Institute Inc., NY, 1992. 305 p.

56. ARC/INFO User's Guide: Surface Modeling with TIN. Environmental Systems Research Institute Inc., NY, 1992. 240 p.

57. ArcView GIS. Environmental Systems Research Institute Inc., NY, 1997. -350 p.

58. Barnhill R.E. Surfaces in computer aided geometric design: a survey with new results // Comput. Aided Geom. Des., Vol. 2, № 1-3, 1985, pp. 1-17.

59. Bertram M., Barnes J.C., Hahmann В., Joy K.I., Pottmann H., Wushour D. Piecewise optimal triangulation for the approximation of scattered data in the plane // Comput. Aided Geom. Des., Vol. 17, № 8, 2000, pp. 767-787.

60. Boissonnat J.D., Faugeras O.D., Le Bras-Mehlman E. Representing stereo data with the Delaunay triangulation // Proc. IEEE Int. Conf. Rob. and Autom., Philadelphia, Pa, Apr. 24-29, 1988. Philadelphia, Pa, 1988, pp. 1798-1803.

61. Brown J.L. Vertex based data dependent triangulations // Comput. Aided Geom. Des., Vol. 8, № 3, 1991, pp. 239-251.

62. CGAL Basic Library Reference Manual. http://www.cgal.org/Manual/dochtml/frameset/fsBasic.html.

63. Chang L.H.T., Said H.B. A C2 triangular patch for the interpolation of functional scattered data // Comput.-Aided Des., Vol. 29, № 6, 1997, pp. 407-412.

64. Chen Xin, Schmitt F. Surface modelling of range data by constrained triangula-tion // Comput.-Aided Des., Vol. 26, № 8, 1994, pp. 632-645.

65. Chrisman N. Exploring Geographic Information Systems. N.Y. a.o.: Wiley, 1997.-297 p.

66. Cignoni P., Montani C., Scopigno R. DeWall: A fast divide and conquer Delau-nay triangulation algorithm in Ed // Comput.-Aided Des., Vol. 30, № 5, 1998, pp. 333-341.

67. Costantini P., Manni C. A local shape-preserving interpolation scheme for scattered data // Comput. Aided Geom. Des., Vol. 16, № 5, 1999, pp. 385-405.

68. Cottin C., van Damme R. Construction of a VC1 interpolant over triangles via edge deletion // Comput. Aided Geom. Des., Vol. 11, № 6, 1994, pp. 675-686.

69. De Marchi S. On computing derivatives for C1 interpolating schemes: an optimization // Computing, Vol. 60, № 1, 1998, pp. 29-53.

70. Douglas D.H., Peucker Т.К. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature // The Canadian Cartographer, Vol. 10, № 2, 1973, pp. 112-122.

71. Dyn N., Levin D., Rippa S. Data dependent triangulations for piecewise linear interpolation // IMA J. Num. Anal., Vol. 10, № 1, 1990, pp. 137-154.

72. ERDAS Field Guide. ERDAS Inc. 1997. 672 p.

73. ESRI Shapefile: A Technical Description. Environmental System Research Institute Inc., USA, 1997. 23 p.

74. Farm G. A modified Clough-Tocher interpolant // Comput. Aided Geom. Des., Vol. 2, № 1-3, 1985, pp. 19-27.

75. Fowler R.J. Automatic extraction of irregular network digital terrain model // Comput. Graph., Vol. 13, № 2, 1979, pp. 199-207.

76. Gleue J. Triangulierung und Interpolation von im R2 unregelmassig verteilten Daten // Ber. Hahn-Meitner Inst. Kernforsch. Berlin, № 357, 1981, pp. 1-66.

77. Gueziec A. Locally toleranced surface simplification // IEEE Trans. Visual, and Comput. Graph., Vol. 5, № 2,1999, pp. 168-189.

78. Hagen H., Nielson G., N akajima Y. S urface de sign us ing t riangular p atches // Comput. Aided Geom. Des., Vol. 13, № 9, 1996, pp. 895-904.

79. Hahmann S., Bonneau G.-P. Triangular C1 interpolation by 4-splitting domain triangles // Comput. Aided Geom. Des., Vol. 17, № 8, 2000, pp. 731-757.

80. Handbook of grid generation / Ed. J.F. Thompson, B.K. Soni, N.P. Weatherill. -Boca Raton, Fl.: CRC Press, 1999.

81. Heckbert P.S., Garland M. Optimal triangulation and quadric-based surface simplification// Comput. Geom., Vol. 14, № 1-3, 1999, pp. 49-65.

82. Herron G. Smooth closed surfaces with discrete triangular interpolants // Comput. Aided Geom. Des., Vol. 2, № 4, 1985, pp. 297-306.

83. Hu Shi-Min Conversion of a triangular Bezier patch into three rectangular Be-zier patches // Comput. Aided Geom. Des., Vol. 13, № 3, 1996, pp. 219-226.

84. Kirkpatrick D. G. A note on Delaunay and Optimal triangulations // Inform. Process. Lett., Vol. 10, № 3, 1980, pp. 127-128.-163

85. Klucewicz I.M. A piecewise С1 interpolant to arbitrary spaced data // Comput. Graph, and Image Process., Vol. 8,1978, pp. 92-112.

86. Kocic L.M., Milosevic D.M. Contouring of interpolating surfaces // Math, balkan., Vol. 10, № 2-3, 1996, pp. 189-201.

87. Kornmann D. The Super Delaunay Triangulation Library. http://www.dlc.fi/~dkpa.

88. Lai Ming-Jun Scattered data interpolation and approximation using bivariate C1 piecewise cubic polynomials II Comput. Aided Geom. Des., Vol. 13, № 1, 1996, pp. 81-88.

89. Laurini R., Thompson D. Fundamentals of Spatial Information Systems. -London a.o.: Academic Press, 1996. 680 p.

90. Lawson C.L. Transforming triangulations // Discrete Mathematics, Vol. 3, №4, 1972, pp. 365-372.

91. Lee D., Schachter B. Two algorithms for constructing a Delaunay triangulation // Int. Jour, of Сотр. and Inf. Sci., 1980, Vol. 9, № 3, pp. 219-242.

92. Lee D.T., Lin A.K. Generalized Delaunay triangulation for planar graph //Discrete Comput. Geom., Vol. 1,1986, pp. 201-217.

93. Lemaire C., Moreau J.-M. A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case // Comput. Geom., Vol. 17, № 1-2, 2000, pp. 69-96.

94. Levcopoulos Ch., Krznaric D. The greedy triangulation can be computed from the Delaunay triangulation in linear time // Comput. Geom., Vol. 14, № 4, 1999, pp. 197-220.

95. Lewis B.A., Robinson J.S. Triangulation of planar regions with applications // Comput. J, Vol. 21, № 4, 1978, pp. 324-332.

96. Liu Qijin, Sun T.C. G1 interpolation of mesh curves // Comput.-Aided Des., Vol. 26, № 4, 1994, pp. 259-267.

97. Loop Ch. A G1 triangular spline surface of arbitrary topological type // Comput. Aided Geom. Des., Vol. 11, № 3, 1994, pp. 303-330.

98. Luo Wei Hypsometric analysis with a geographic information system // Comput. and Geosci., Vol. 24, № 8, 1998, pp. 815-821.

99. Manacher G. K., Zobrist A., L. Neither the Greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation // Inform. Process. Lett., 1979, Vol. 9, № 1, pp. 31-34.

100. McLain D.H. Two dimensional interpolation from random data // Comput. J., Vol. 19, 1976, pp. 178-181.

101. Min Weidong, Tang Zesheng, Zhang Zhenming, Zhou Yu, Wang Minzhi Automatic mesh generation for multiply connected planar regions based on mesh grading propagation // Comput.-Aided Des., Vol. 28, № 9, 1996, pp. 671-681.

102. Miicke E.P., Saias I., Zhu Binhai Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations // Comput. Geom., Vol. 12, № 1-2, 1999, pp. 63-83.

103. Nelson J.M. A triangulation algorithm for arbitrary planar domains // Appl. Math. Modell., Vol. 2,№ 3, 1978, pp. 151-159.

104. Oxley A. Surface fitting by triangulation // Comput. J., Vol. 28, № 3, 1985, pp. 335-339.

105. Reif U. A note on degenerate triangular Bezier patches // Comput. Aided Geom. Des., Vol. 12, № 5, 1995, pp. 547-550.

106. Sablonniere P. Bernstein-Bezier methods for the construction of bivariate spline approximants // Comput. Aided Geom. Des., Vol. 2, № 1-3, 1985, pp. 29-36.

107. Saux E., Daniel M. Data reduction of polygonal curves using B-splines // Comput.-Aided Des, Vol. 31, № 8, 1999, pp. 507-515.

108. Schroeder W.J., Shephard M.S. Geometry-based fully automatic mesh generation and the Delaunay triangulation // Int. J. Numer. Meth. Eng., Vol. 26, № 11, 1988, pp. 2503-2515.

109. Sederberg T.W. Piecewise algebraic surface patches // Comput. Aided Geom. Des., Vol. 2, № i3? 1985, pp. 53-59.

110. Seldner D, Westermann T. Algorithms for interpolation and localization in irregular 2D meshes // J. Comput. Phys, Vol. 79, № 1, 1988, pp. 1-11.

111. Sibson R. Locally equiangular triangulations // Comput. J, Vol. 21, № 3, 1978, pp. 243-245.

112. Sloan S.W. A fast algorithm for constructing Delaunay triangulations in the plane // Advances in Engineering Software, Vol. 9, № 1, 1987, pp. 34-55.

113. Spitzmiiller K. Partial derivatives of Bezier surfaces // Comput.-Aided Des, Vol. 28, № 1, 1996, pp. 67-72.

114. Subraminian G, Raveendra V.U.S, Kamath M.G. Robust boundary triangulation and Delaunay triangulation of arbitrary planar domains // Int. J. Numer. Meth. Eng., Vol. 37, № 10, 1994, 1779-1789.

115. Sugihara K. Surface interpolation based on new local coordinates // Comput.-Aided Des, Vol. 31, № 1, 1999, pp. 51-58.-166

116. Surfer®. A powerful contouring, gridding and surface mapping package for scientist and engineers.http://www.goldensoftware.com/frames/surferframe.htm.

117. TNTmips®. The map and image processing system. http://www.microimages.com/ product/tntmips.htm.

118. Tookey R., Ball A. Approximate G1 continuous interpolation of a rectangular network of rational cubic curves // Comput.-Aided Des., Vol. 28, № 12, 1996, pp. 1007-1016.

119. Vertical Mapper. North wood Geosciense Ltd. http://www.northwoodgeo.com/ verticalmapper.htm.

120. Vida J., Martin R.R., Varady T. A survey of blending methods that use parametric surfaces // Comput.-Aided Des., Vol. 26, № 5, 1994, pp. 341-365.

121. Walton D.J., Meek D.S. A triangular G1 patch from boundary curves // Comput.-Aided Des., Vol. 28, № 2, 1996, pp. 113-123.

122. Watson D.F., Philip G.M. Systematic triangulations // Comput. Vision, Graph. And Image Process., Vol. 26, № 2, 1984, pp. 217-223.

123. Watson D.F., Philip G.M. Triangle based interpolation // J. Int. Assoc. Math. Geol., Vol. 16, № 8, 1984, pp. 779-795.

124. Worboys M.F. GIS: a computing perspective. London, Bristol: Taylor & Francis, 1997.-376 p.1. UU- г.ии .'.м, -------—'—!< t. I M< >*1. J. 1'I8 r.1. Г, K. .

125. Акт it n eяpс n и я № 4у <S Ъ ' -: от „ & " а^гил, 1983 г.." . ■ (цакменовяннс организации, . , '. .,-., ;

126. B%?J-t<c{. /?'.pel11cLc'4 e-Z-cVT- с одной rvup.Miu И

127. Гилу клея В, Д, fryV0 jj'"1. Cl-iei.*:.,:}1. Гр^Ф^б -J* я. а^Ж"-"фукс A.Jl Ijj"1. Ирсдстапители . iJi^H—•пл.-пчагсля»

128. В результате на территорию Республики Алтай была получена кондиционная региональная (Ml: 500 ООО Ml: 1 ООО ООО) цифровая модель рельефа, как составная часть карты недропользования.

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

130. Заместитель декана по научно-производственной работе

131. Декан факультета информатики1. Б.А. Гладких1. С.П. Сущенко