Расшифровка подписи

Вид материала

Расшифровка

Содержание Жусова А.В. Постановка задачи Цель работы Задачи программного комплекса Обзор гис, использующих построение изолиний ArcGIS ArcInfo MapInfo Professional Панорама (Россия) ER Mapper Erdas imagine Описание метода построения треангуляции Описание метода упррощения треангуляции делоне Шаг 3. Для каждого ребра r Описание метода построения изолиний с помощью триангуляции делоне Алгоритм построения изолиний. Шаг 2. Для каждого треугольника с C Алгоритм построения гладких изолиний.

Подобный материал:

• Расшифровка подписи, 648.16kb.
• Расшифровка подписи, 20.28kb.
• Расшифровка подписи, 107.69kb.
• Расшифровка подписи, 7.15kb.
• Расшифровка подписи, 71.62kb.
• Расшифровка подписи, 79.59kb.
• О. Ф. Головач (дата) (номер) (подпись) (расшифровка подписи), 60.4kb.
• М. А. Шолохова Утверждаю: Ректор мггу им. М. А. Шолохова Нечаев В. Д. 20 г. Основная, 327.6kb.
• М. А. Шолохова Утверждаю: Ректор мггу им. М. А. Шолохова Нечаев В. Д. 20 г. Основная, 2177.72kb.
• М. А. Шолохова Утверждаю: Ректор мггу им. М. А. Шолохова Нечаев В. Д. 20 г. Основная, 1838.96kb.

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

ГОУВПО Самарский государственный архитектурно-строительный университет

Факультет информационных систем и технологий

Кафедра прикладной математики и вычислительной техники


ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе:


КОМПЬЮТЕРНЫЙ КОМПЛЕКС ФОРМИРОВАНИЯ

ИЗОЛИНИЙ


СТУДЕНТА ГИП-104 ЖУСОВОЙ АЛЁНЫ ВЛАДИМИРОВНЫ

			Подпись, дата	Расшифровка подписи
		ВЫПОЛНИЛ:
		студент		/ Жусова А.В. /
		ПРОВЕРИЛ:
		профессор, д.т.н.		/ /

Самара 2008 г.

ПОСТАНОВКА ЗАДАЧИ

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

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

Задачи программного комплекса:

- ввод картографических, текстовых и числовых данных;

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

- ведение БД хранения и манипуляции данными;

- обработка цифровых изображений, построение по введенным данным;

- исследование известных методов построения изолиний;

- построение эффективного интерфейса;

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

- ведение статистического анализа данных.


ОБЗОР ГИС, ИСПОЛЬЗУЮЩИХ ПОСТРОЕНИЕ ИЗОЛИНИЙ

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

Характеризуя свойства полнофункциональных ГИС можно отметить их общие черты.  Все системы работают на платформе Windows. Только некоторые из них имеют версии, работающие под управлением других операционных систем («Горизонт» - MS DOS, Unix, Linux, MC BC, Free BSD, Solaris, ИНТРОС; ПАРК – MS DOS; Arc GIS Arc Info-Solaris, Digital Unix, AIX и др.; ArcView GIS – Unix).

Все системы поддерживают обмен пространственной информацией (экспорт и импорт) со многими ГИС и САПР через основные обменные форматы.

Еще более однородными являются возможности по работе с атрибутивной информацией. Большинство систем обеспечивают работу со всеми основными СУБД через драйверы ODBC, BDE. Первой в ряду поддерживаемых или используемых СУБД стоит Oracle.

Наиболее распространенными зарубежными системами по разным причинам являются ArcView GIS, MapInfo Professioal, MicroStation/J. Аналогичный перечень отечественных систем возглавляют ГеоГраф, Панорама (Карта 2000), ПАРК, GeoLink.

Коротко охарактеризуем наиболее распространенные программные продукты, отмечая особенности и области применения.  

ArcGIS ArcInfo (разработчик фирма ESRI, США). Полнофункциональная ГИС, состоящая из двух независимо устанавливаемых программных пакетов – ArcInfo Workstation и ArcInfo Desktop. Первый состоит из трех базовых модулей:  ArcMap – отображение, редактирование и анализ данных,  ArcCatalog – доступ к данным и управление ими,  ArcToolbox – инструмент расширенного пространственного анализа, управление проекциями и конвертацией данных. Дополнительные модули обеспечивают решение следующих задач: работа с геодезическими данными; анализ и управление непрерывно распределенными числовыми и качественными признаками, представляемыми в виде регулярных моделей, а также моделирование сложных процессов; моделирование топографических поверхностей.

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

MapInfo Professional (разработка фирмы MapInfo Corp.США), одна из самых распространенных настольных ГИС в России. MapInfo специально спроектирован для обработки и анализа информации, имеющей адресную или пространственную привязку.

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

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

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

Отдельно следует выделить профессиональные многофункциональные  инструментальные ГИС, обеспечивающие возможность непосредственной обработки данных ДЗ. К ним относятся ERDAS IMAGINE, ERMapper и др.

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

ERDAS IMAGINE (разработка Leica) – программный пакет, разработанный специально для обработки и анализа данных дистанционного зондирования, предоставляет полный набор инструментов для анализа данных из любого источника и представление результатов в различных формах – от печатных карт до трехмерных моделей.  ERDAS IMAGINE построен по модульному принципу в виде базовых комплектов – IMAGINE Essential, IMAGINE Advantage и  IMAGINE Professional.

В  ERDAS IMAGINE  реализованы: широкие возможности по визуализации и импорту данных (поддерживает более 100 форматов); геометрическая коррекция; улучшающие преобразования и ГИС-анализ; дешифрирование снимков; инструменты обработки изображений и построение алгоритмов пространственных вычислений; создание карт.

Необходимо отметить, что в профессиональных ГИС для построения изолиний на практике используются два основных метода:

• построение изолиний по равномерной квадратной сетке
  
• построение изолиний по триангуляции (Делоне)
  

Перечисленные варианты построения изолиний описаны и их можно реализовать, создавая свой авторский программный код или используя уже готовые компоненты программ. Авторский программный код можно после его разработки и реализации в виде готового программного модуля можно зарегистрировать в РОСПАТЕНТА. Недостаток готовых компонентов состоит в следующем:

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

Построение по равномерной квадратной сетке состоит из следующих стадий:

• построение сетки
  
• построение изолиний по значениям сетки
  

Построение сетки выполняется следующим образом:

Площадь карты месторождения внутри контура ВНК делится на квадраты с постоянным шагом по горизонтали и вертикали. Задаются значение параметра на ВНК. Задаются значения в вершинах скважин. Рассчитывается значения остальных узлов сетки, в которых нет скважин.



Рис. 1. Пример разбивки карты на сетку с заданием ячеек, содержащих скважины и ячеек, через которые проходит ВНК.


Расчет может производиться различными методами. В основном это итерационные методы расчета поверхности.

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



Рис. 2. Пример построения трехмерной поверхности по заданным значениям параметра в скважинах и наВНК.

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

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

Построение изолиний по значениям сетки выполняется следующим образом:

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



Рис. 3. Пример построения изолиний по значениям сетки


Недостатки:

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



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


Выход из этой ситуации - это увеличение частоты сетки, до тех пор. пока в одной ячейке не будет одной скважины. Это влечет за собой:

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

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



Рис. 5. Пример возникновения возвышения значения показателя между близлежащих скважин с более низкими значениями.


Построение изолиний с использованием триангуляции (Делоне)


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

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

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

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

Общий алгоритм состоит из следующих стадий:

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

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

• по линейному закону
  
• по нелинейному
  

Нанесение отсечек по линейному закону.

Алгоритм построения представлен на следующем рисунках 6 и 7:



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



Рис. 7. Пример построения на плоскости карты кривой изолинии по нанесенным осечкам для плоскости F1

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

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



Рис. 8 Пример построения поверхности с использованием триангуляции

и нанесением отсечек по линейному закону.

I - Построенная трехмерная поверхность,

А - центральная скважина. В, С, D, Е – ближайшие скважины.

А-А₁ - значение параметра в скважине А. В-B₁ - значение параметра в скважине В.

A₁-B₁ - проекция на плоскость линии соединяющей значений параметра в скважинах А и В.

II - Пример сечения вертикального разреза трехмерной поверхности горизонтальными

плоскостями F₁, F₂, F₃ (нанесение отсечек).

Мной было предложено усовершенствовать линейный метод нанесение отсечек:

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

Алгоритм построения представлен на следующем рисунке:



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



Рис. 10. Пример построения на плоскости карты кривой изолинии по нанесенным осечкам для плоскости F₁.

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

Преимущества:

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

Недостатки:

• необходимо найти простой способ расчета нелинейного закона
  

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

Состоит из следующих стадий:

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

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

Сетка может быть достроена с ячейками квадратной формы или нет.

Преимущества:

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

Недостатки:

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

ОПИСАНИЕ МЕТОДА ПОСТРОЕНИЯ ТРЕАНГУЛЯЦИИ

«УДАЛЯЙ И СТРОЙ»

В итеративном алгоритме «Удаляй и строй» не выполняется никаких перестроений. Вместо этого при каждой вставке нового узла (рис. 19,а) сразу же удаляются все треугольники, у которых внутрь описанных окружностей попадает новый узел (рис. 19,б). При этом все удаленные треугольники неявно образуют некоторый многоугольник. После этого на месте удаленных треугольников строится заполняющая триангуляция путем соединения нового узла с этим многоугольником (рис. 19,в) [49].



Рис. 19. Вставка точки в итеративном алгоритме «Удаляй и строй»: а – локализация точки в треугольнике; б – удаление треугольников; в – построение новых треугольников.

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

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

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

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


ОПИСАНИЕ МЕТОДА УПРРОЩЕНИЯ ТРЕАНГУЛЯЦИИ ДЕЛОНЕ

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

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

Определение 27. Пусть имеется триангуляция T, содержащая N=Т узлов. В задаче построения упрощающей триангуляции (задаче генерализации) требуется найти такую триангуляцию t, что:

1. она содержит заданное количество узлов n=|t| и имеет минимальное отклонение d от T: d(T,t) = min d(T,τ), | τ |=n (задача, управляемая геометрией);
   
2. она имеет отклонение d по вертикали от T не более чем на заданную величину ε и имеет минимальное количество узлов n(t) = min n(τ), d(T,τ)<ε (задача, управляемая ошибкой).
   

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

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

Уменьшение числа элементов обычно выполняется с помощью локальной модификации триангуляции – операции, заменяющей некоторую маленькую группу смежных треугольников на другую, покрывающую ту же область. На практике обычно применяют 3 вида локальных модификаций (рис. 74): а) удаление узла, б) коллапс ребра и в) коллапс треугольника.




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

Алгоритм локального упрощения триангуляции. Дана исходная триангуляция T и задана требуемая точность ε или нужное количество треугольников n.

Шаг 1. Создаем новую триангуляцию как копию исходной T’:=T.

Шаг 2. Для каждого узла p_j ϵ T’ устанавливаем отклонение от исходной модели π_j: =0 и вычисляем потенциальное новое отклонение π’_j, которое возникнет на поверхности при его удалении (среднее высот его соседей Делоне, взвешенных по их удаленности от узла p ).

Шаг 3. Для каждого ребра r_j ϵ T’ , соединяющего узлы p_j1 и p_j2 , вычисляем отклонение его центра от исходной модели p_j:=0 и вычисляем потенциальное новое отклонение p’_j := (π_j1+ π’_j1+ π_j2+ π’_j2)/3, которое возникнет при его коллапсе.

Шаг 4. Для каждого треугольника τ_j ϵ T’, соединяющего узлы p_j1, p_j2 и p_j3, вычисляем отклонение его центра от исходной модели τ_j:=0 и потенциальное отклонение τ_j:= (π_j1+ π’_j1+ π_j2+ π’_j2+ π_j3+ π’_j3)/6 , которое возникнет при его коллапсе.

Шаг 5. Все объекты триангуляции – узлы, рёбра и треугольники – помещаем в сбалансированное дерево поиска по значениям π_j+ π’_j , p_j+ p’_j и τ_j+ τ’_j соответственно.

Шаг 6. Пока не будет превышена допустимая точность или будет достигнуто заданное количество треугольников, выполняется следующий цикл. В триангуляции выбирается объект (узел, ребро или треугольник) с минимальным значением величин π_j+ π’_j , p_j+ p’_j или τ_j+ τ’_j. В соответствии с найденным минимумом выполняется удаление узла, коллапс ребра или коллапс треугольника. После этого необходимо выполнить расчет текущих и потенциальных отклонений для всех вновь появившихся объектов триангуляции и обновить дерево поиска. Конец алгоритма.

Трудоемкость данного алгоритма зависит главным образом от сложности расчета отклонений для вновь появившихся объектов триангуляции, когда необходимо находить в исходной триангуляции треугольник, в который попадает исследуемая точка. Если для исходной триангуляции имеется кэш поиска (как в алгоритмах триангуляции с кэшированием), то поиск одной точки будет происходить в среднем за время O(1). Так как в среднем при одной локальной модификации триангуляции затрагивается O(1) объектов, а обновление дерева поиска занимает время O(log n_i), где n_i – текущий размер триангуляции, то в целом данный алгоритм имеет трудоемкость в среднем около O (N log N).


ОПИСАНИЕ МЕТОДА ПОСТРОЕНИЯ ИЗОЛИНИЙ С ПОМОЩЬЮ ТРИАНГУЛЯЦИИ ДЕЛОНЕ

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



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

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

Алгоритм построения изолиний.

Шаг 1. Помечаем каждый треугольник триангуляции, по которому проходят изолинии (т.е. выполняется условие min(z₁, z₂, z₃) < h < max(z₁, z₂, z₃), где z – высоты трех его вершин), флагом С:=1, а вес остальные треугольники – С:=0 (рис. 83,а). Если обнаружен хотя бы один треугольник, у которого хотя бы одно ребро лежит в плоскости изолинии, то h уменьшается на некоторое малое Δ и алгоритм повторяется заново.

Шаг 2. Для каждого треугольника с C_i :=1 выполняем отслеживание очередной изолинии в обе стороны от данного треугольника, пока один конец не выйдет на другой или на границу триангуляции (рис. 83,б). Каждый пройденный при отслеживании треугольник помечается C_i :=0. Конец алгоритма.



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

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

Алгоритм построения гладких изолиний. Пусть необходимо построить изолинии уровней h₁ < h₂ < … < h_n.

Шаг 1. Вычисляем максимально допустимое отклонение высот сглаженной изолинии от истинной



Шаг 2. Вычисляем для каждой изолинии h коридор в виде обычных несглаженных изолиний



Шаг 3. В полученных коридорах строится сглаживающая изолиния. Конец алгоритма.

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



Рис. 85. Построение ломаной минимальной длины: а – в исходном коридоре; б – в модифицированном коридоре.

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