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

• Автор: Фукс, Александр Львович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Томск
• Количество страниц: 173 с. : ил

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ.

Глава 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. Выводы.
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Выпуклой оболочкой множества 5 точек на плоскости называется граница наименьшей выпуклой области, которая охватывает 5. Определение 1. Триангуляцией конечного множества 5’ точек на плоскости называется плоский граф из вершин 5, имеющий наибольшее число ребер. Триангуляция 5 получается путем соединения точек из 5' прямолинейными непересекающнмися отрезками так, что любая грань, лежащая внутри выпуклой оболочки 5, является треугольником. Поэтому триангуляцией называют получаемую сетку непе/зесекающихся треугольников. S, а любое ребро будет либо общей границей двух смежных треугольников (внутреннее), либо одним из граничных ребер треугольной сетки. Дія упрощения изложения будем далее называть триангуляцией и получаемую треугольную сетку, и сам процесс ее построения. Если исходный набор включает п вершин, причем g из них принадлежат выпуклой оболочке, то, в соответствии с формулой Эйлера, любая триангуляция данного набора будет содержать ровно 3(/i-l)-g ребер и 2(n-)-g треугольников. Задача триангуляции набора точек на плоскости является неоднозначной, поэтому необходимо вводить дополнительные критерии дія сравнения разных систем треугольников. Триангуляция нужна, прежде всего, для структуризации исходного нерегулярного набора. Точки В1,В2,. Вк, которые соединяются ребрами сетки с точкой А, определяют ее окрестность и должны быть близкими соседями А. Тогда естественным критерием будет минимум суммы дтин ребер триангуляции. Отделение 1. Оптимальной или минимальной взвешенной называют триангу ляцию, у которой сумма длин всех ребер минимальна. В работе [1] доказана Л'Р-полнота задачи оптимальной триангуляции многосвязного полигона, поэтому есть все основания полагать, что и общая задача построения оптимальной триангуляции является не менее сложной. Следовательно, любой алгоритм ее решения будет экспоненциальным по трудоемкости и абсолютно непригодным для обработки реальных наборов точек. Для нахождения субоптимального решения теоретически можно использовать жадный алгоритм триангуляции, трудоемкость которого составляет 0(/г log/? Другим недостатком оптимальной триангуляции является возможное вырождение треугольников в линию в случае, когда 3 и более близкорасположенных точек лежат практически на одной прямой (рис. В большинстве приложений требуется учитывать не только расстояния между парами точек, но и форму получаемых треугольников, причем желательно, чтобы треугольники были но возможности близки к равносторонним. Рис. Определение 1. Ячейкой Вороного для точки А из заданного набора точек на плоскости называется множество точек плоскости, для которых А является ближайшей точкой из этого набора [, 0]. Точка А называется центром ячейки. Ячейка Вороного всегда будет выпуклым многоугольником: замкнутым, если ее центр находится внутри выпуклой оболочки набора, и открытым, если ее центр принадлежит выпуклой оболочке. Определение 1. Диаграммой (мозаикой) Вороного для набора из п точек называется разбиение плоскости на п соответствующих ячеек Вороного [,0]. В некоторых источниках диаграмму Вороного называют также разбиением Тиссена или Дирихле. Очевидно, что это разбиение единственно. Границами ячеек Вороного являются ломаные линии. Внутренние точки их ребер лежат на одинаковом расстоянии от центров пар ячеек, а узловые точки одинаково удалены от центров трех или более ячеек. Если каждая из узловых точек является общей граничной точкой ровно трех ячеек, то для диаграммы Вороного можно единственным образом построить двойственную структуру - триангуляцию Делоне. Вершинами этой триангуляции будут исходные точки, а ребра соединят центры ячеек, имеющих общие границы (рис. Если в исходном наборе найдется к > 3 точек, лежащих на одной окружности, внутри которой нет других исходных точек, то центром данной окружности будет общая г раничная точка к соответствующих ячеек Вороного. С-к оставшихся ребер (рис. Определение 1. Триангуляцией Делоне называется триангу ляция, удовлетворяющая условию Делоне-, внутрь окружности, описанной вокруг любого ее треугольника, не попадает никакая из вершин других треугольников [, ,, 5, 1, 9, 0].