WWW.KNIGI.KONFLIB.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

 
<< HOME
Научная библиотека
CONTACTS

Pages:     || 2 | 3 | 4 | 5 |   ...   | 18 |

«А.В. Скворцов Триангуляция Делоне и её применение Издательство Томского университета 2002 УДК 681.3 ББК 22.19 C 42 Скворцов А.В. C 42 Триангуляция Делоне и её ...»

-- [ Страница 1 ] --

Томский государственный университет

Факультет информатики

А.В. Скворцов

Триангуляция Делоне

и её применение

Издательство Томского университета

2002

УДК 681.3

ББК 22.19

C 42

Скворцов А.В.

C 42 Триангуляция Делоне и её применение. – Томск: Изд-во Том.

ун-та, 2002. – 128 с.

ISBN 5-7511-1501-5

В книге рассматриваются триангуляция Делоне и её обобщение – триангуляция Делоне с ограничениями. Приводятся 5 вариантов структуры данных, 4 способа проверки условия Делоне, 4 группы алгоритмов построения триангуляции Делоне (всего 28 алгоритмов) с оценками трудоемкости, 4 алгоритма построения триангуляции Делоне с ограничениями.

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

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

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

УДК 681. ББК 22. Рецензент – докт. техн. наук проф. Н.Г. Марков © А.В. Скворцов, ISBN 5-7511-1501-5 © Обложка: А.Л. Коваленко, Содержание Предисловие

Глава 1. Триангуляция Делоне

1.1. Определения

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

1.2.1. Структура данных «Узлы с соседями»

1.2.2. Структура данных «Двойные рёбра»

1.2.3. Структура данных «Узлы и треугольники»

1.2.4. Структура данных «Узлы, рёбра и треугольники»

1.2.5. Структура данных «Узлы, простые рёбра и треугольники»....... 1.3. Проверка условия Делоне

1.3.1. Проверка через уравнение описанной окружности

1.3.2. Проверка с заранее вычисленной описанной окружностью...... 1.3.3. Проверка суммы противолежащих углов

1.3.4. Модифицированная проверка суммы противолежащих углов. 1.4. Алгоритмы триангуляции Делоне

Глава 2. Итеративные алгоритмы построения триангуляции Делоне

2.1. Простой итеративный алгоритм

2.1.1. Итеративный алгоритм «Удаляй и строй»

2.2. Алгоритмы с индексированием поиска треугольников............. 2.2.1. Итеративный алгоритм с индексированием треугольников....... 2.2.2. Итеративный алгоритм с индексированием центров треугольников k-D-деревом

2.2.3. Итеративный алгоритм с индексированием центров треугольников квадродеревом

2.3. Алгоритмы с кэшированием поиска треугольников................. 2.3.1. Итеративный алгоритм со статическим кэшированием поиска. 2.3.2. Итеративный алгоритм с динамическим кэшированием поиска 2.3.3. Трудоемкости алгоритмов с кэшированием поиска

2.4. Итеративные алгоритмы триангуляции с изменённым порядком добавления точек

2.4.1. Итеративный полосовой алгоритм

2.4.2. Итеративный квадратный алгоритм

2.4.3. Итеративный алгоритм с послойным сгущением

4 Содержание 2.4.4. Итеративный алгоритм с сортировкой вдоль кривой, заполняющей плоскость

2.4.5. Итеративный алгоритм с сортировкой по Z-коду

Глава 3. Алгоритмы построения триангуляции Делоне слиянием

3.1. Алгоритм слияния «Разделяй и властвуй»

3.1.1. Слияние триангуляций «Удаляй и строй»

3.1.2. Слияние триангуляций «Строй и перестраивай»

3.1.3. Слияние триангуляций «Строй, перестраивая»

3.2. Рекурсивный алгоритм с разрезанием по диаметру

3.3. Полосовые алгоритмы слияния

3.3.1. Выбор числа полос в алгоритме полосового слияния................. 3.3.2. Алгоритм выпуклого полосового слияния

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

Глава 4. Алгоритмы прямого построения триангуляции Делоне

4.1. Пошаговый алгоритм

4.2. Пошаговые алгоритмы с ускорением поиска соседей Делоне. 4.2.1. Пошаговый алгоритм с k-D-деревом поиска

4.2.2. Клеточный пошаговый алгоритм

Глава 5. Двухпроходные алгоритмы построения триангуляции Делоне

5.1. Двухпроходные алгоритмы слияния

5.2. Модифицированный иерархический алгоритм

5.3. Линейный алгоритм

5.4. Веерный алгоритм

5.5. Алгоритм рекурсивного расщепления

5.6. Ленточный алгоритм

Глава 6. Триангуляция Делоне с ограничениями

6.1. Определения

6.2. Цепной алгоритм построения триангуляции с ограничениями 6.3. Итеративный алгоритм построения триангуляции Делоне с ограничениями

6.3.1. Вставка структурных отрезков «Строй, разбивая»

6.3.2. Вставка структурных отрезков «Удаляй и строй»

6.3.3. Вставка структурных отрезков «Перестраивай и строй»............ 6.4. Классификация треугольников

6.5. Выделение регионов из триангуляции

Глава 7. Вычислительная устойчивость алгоритмов триангуляции

7.1. Причины возникновения ошибок при вычислениях.................. 7.2. Применение целочисленной арифметики



7.3. Вставка структурных отрезков

Глава 8. Пространственный анализ на плоскости............... 8.1. Построение минимального остова

8.2. Построение оверлеев

8.3. Построение буферных зон

8.4. Построение зон близости

8.5. Построение взвешенных зон близости

8.6. Нахождение максимальной пустой окружности

Глава 9. Триангуляционные модели поверхностей.................. 9.1. Структуры данных

9.2. Упрощение триангуляции

9.3. Мультитриангуляция

9.4. Пирамида Делоне

9.5. Детализация триангуляции

9.6. Сжатие триангуляции

Глава 10. Анализ поверхностей

10.1. Построение разрезов поверхности

10.2. Сглаживание изолиний

10.3. Построение изоклин

10.4. Построение экспозиций склонов

10.5. Вычисление объемов земляных работ

10.6. Построение зон и линий видимости

Литература

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

В гл. 1 даются определения триангуляции, рассматриваются основные её свойства, приводятся 5 основных используемых структур данных, а также 4 способа проверки условия Делоне.

В гл. 2-5 рассматриваются 4 группы алгоритмов построения триангуляции Делоне, всего 28 алгоритмов. Предлагается классификация алгоритмов, приводятся их трудоемкости, а также общие оценки алгоритмов.

В гл. 6 рассматривается обобщение триангуляции Делоне – триангуляция Делоне с ограничениями, используемая для решения широкого круга задач.

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

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

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

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

Описываемые в гл. 8–10 применения триангуляции Делоне с ограничениями реализованы автором в рамках геоинформационной системы ГрафИн 4.0 и прошли апробацию на реальных задачах.

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

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

skv@csd.tsu.ru.

Глава 1. Триангуляция Делоне Впервые задача построения триангуляции Делоне была поставлена в 1934 г. в работе советского математика Б.Н. Делоне [1]. Трудоёмкость этой задачи составляет O ( N log N ). Существуют алгоритмы, достигающие этой оценки в среднем и худшем случаях. Кроме того, известны алгоритмы, позволяющие в ряде случаев достичь в среднем O ( N ).

Для дальнейшего обсуждения введём несколько определений [1,12]:

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

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

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

Задача построения триангуляции по исходному набору точек является неоднозначной, поэтому возникает вопрос, какая из двух различных триангуляций лучше?

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

В [37,39] обосновано, что задача построения такой триангуляции, видимо, является NP-полной. Поэтому для большинства реальных задач существующие алгоритмы построения оптимальной триангуляции неприемлемы ввиду слишком высокой трудоёмкости. При необходимости на практике применяют приближенные алгоритмы [8].

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

Жадный алгоритм построения триангуляции.

Шаг 1. Генерируется список всех возможных отрезков, соединяющих пары исходных точек, и он сортируется по длинам отрезков.

Шаг 2. Начиная с самого короткого, последовательно выполняется вставка отрезков в триангуляцию. Если отрезок не пересекается с другими ранее вставленными отрезками, то он вставляется, иначе он отбрасывается.

Конец алгоритма.

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

Определение 5. Триангуляция называется жадной, если она построена жадным алгоритмом.

Трудоемкость работы жадного алгоритма при некоторых его улучшениях составляет O ( N 2 log N ) [26]. В связи со столь большой трудоемкостью на практике он почти не применяется.

Кроме оптимальной и жадной триангуляции, также широко известна триангуляция Делоне, обладающая рядом практически важных свойств [1,4,37,39].

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



Pages:     || 2 | 3 | 4 | 5 |   ...   | 18 |
 



Похожие работы:

«Е.А. Медведева Основы международного бизнеса Учебно-методический комплекс Москва 2008 1 УДК 339.1 ББК 65.5 М 42 Медведева Е.А. ОСНОВЫ МЕЖДУНАРОДНОГО БИЗНЕСА: Учебно-методический комплекс. – М.: Изд. центр ЕАОИ. – 116 с. © Медведева Е.А., 2008 © Евразийский открытый институт, 2008. 2 Содержание 1. Условия и причины создания фирмы за рубежом 2. Процедура учреждения обществ за рубежом 3. Финансовая отчетность фирмы 4. Оффшорный бизнес Понятие и признаки оффшорных юрисдикций История и причины...»

«Психологическое консультирование и диагностика практическое руководство ЧАСТЬ I Москва ГЕНЕЗИС 2001 1 УДК 159.923 (075.8) ББК 88я 73 В 29 Венгер А. Л. В 29 Психологическое консультирование и диагностика. Практическое руководство. Часть 1. — М.: Генезис, 2001. — 160 с. ISBN 5-85297-031-Х Настоящее пособие рассчитано на психологов, работающих с детьми и подростками. Оно содержит конкретные рекомендации по проведению диагностического обследования ребенка, интерпретации результатов и...»

«А. В. Осин Мультимедиа в образовании: контекст информатизации © © Осин А.В., 2003 Мультимедиа в образовании: контекст информатизации Оглавление От автора Глава 1. Образовательные электронные издания и ресурсы 1.1. Образование и компьютер 1.2. Издания и ресурсы 1.3. Новые педагогические инструменты 1.4. Компоненты мультимедиа 1.5. Уровень интерактивности 1.6. ЭИР и педагогические технологии 1.7. ЭИР и книга Глава 2. Концепция развития образовательных ЭИР 2.1. Цель и задачи концепции 2.2. Анализ...»

«ИЗ ИСТОРИИ КИБЕРНЕТИКИ Ответственный редактор академик А.С. Алексеев Редактор-составитель д.т.н. Я.И. Фет НОВОСИБИРСК 2006 УДК 681.3 ББК 22.18 И32 Из истории кибернетики / Редактор-составитель Я.И. Фет. – Новосибирск: Академическое издательство Гео, 2006.– 339 с. – ISBN 5-9747-0038-4 Герои и авторы публикуемых очерков – выдающиеся ученые разных стран, пионеры кибернетики. Они делятся воспоминаниями с читателями, высказывают свои взгляды на прошлое, настоящее и будущее кибернетики и выросшей из...»

«КОНЦЕПЦИЯ РАЗВИТИЯ ИССЛЕДОВАТЕЛЬСКОГО УНИВЕРСИТЕТА НОВОГО ТИПА В ГОРОДЕ ПУЩИНО Утверждено Ученым советом ПущГУ от 09.09.2010г. Поддержано администрацией г. Пущино 24.09.2010г. Пущино 2010 г. Концепция развития исследовательского университета нового типа в городе Пущино Оглавление Введение 4 1.1. Биология и биотехнология — лидер науки и ведущая отрасль экономики XXI века 1 Биология в стране и мире: взгляд на кадровую проблему 8 1.2. Кадры для биологии: проблема качества 2.1. Создание ПущГУ:...»

«1. Цели и задачи освоения дисциплины. Цель преподавания данной дисциплины заключается в том, чтобы дать бакалаврам знания в области социальной информатики, современных научных и практических методов работы с научной информацией. Основной задачей преподавания данной дисциплины является ознакомление магистрантов с существующими социальными проблемами информатизации, приобретение навыков работы с научной информацией (поиск, анализ, структурирование), навыков подготовки и представления...»

«ТИХООКЕАНСКИЙ ИНСТИТУТ ДИСТАНЦИОННОГО ОБРАЗОВАНИЯ И ТЕХНОЛОГИЙ РАГУЛИН П. Г. ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ (электронный учебник) ВЛАДИВОСТОК 2004 г. УДК 007 ББК 32.81 Р 59 Рецензент: С. Н. Мартышенко, к.т.н., профессор, зав. кафедрой информатики, компьютерной и инженерной графики Владивостокского государственного университета экономики и сервиса Рагулин П.Г. Р 59 Информационные технологии. Электронный учебник. — Владивосток: ТИДОТ Дальневост. ун-та, 2004. - 208 с. Формирование информационного...»

«Организация групповой проектной деятельности в начальной школе с использованием средств информатизации Материалы на районный тур фестиваля 2014 Описание системы работы администрации ОУ по организации проектной деятельности в начальной школе Образовательная программа ГБОУ средняя общеобразовательная школа № 619 Калининского района Санкт-Петербурга определяет выбор проектного метода как ведущего для проектирования и осуществления воспитательной работы с учащимися школы. Этот выбор основан на...»

«С.В. Абламейко, А.М. Недзьведь Обработка оптических изображений клеточных структур в медицине Минск 2005 ЧЕРНОВОЙ АВТОРСКИЙ ВАРИАНТ МОНОГРАФИИ: Абламейко С.В., Недзьвед ь А.М. Обработка оптических изображений клеточных структур в медицине. – Мн.: ОИПИ НАН Беларуси, 2005. – 155с. УДК 681.327.12.001.362 А б л а м е й к о С. В., Н е д з ь в е д ь А. М. Обработка оптических изображений клеточных структур в медицине. – Мн.: ОИПИ НАН Беларуси, 2005. – 156с. ISBN 985-6744-09-1 Рассматриваются...»






 
© 2013 www.knigi.konflib.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.