Главная » 2014 » Сентябрь » 1 » Скачать Комплексное исследование и разработка эффективных алгоритмов триангуляции простого многоугольника. Дворцов, Владислав Игоревич бесплатно
21:14
Скачать Комплексное исследование и разработка эффективных алгоритмов триангуляции простого многоугольника. Дворцов, Владислав Игоревич бесплатно
Комплексное исследование и разработка эффективных алгоритмов триангуляции простого многоугольника
Диссертация
Автор: Дворцов, Владислав Игоревич
Название: Комплексное исследование и разработка эффективных алгоритмов триангуляции простого многоугольника
Справка: Дворцов, Владислав Игоревич. Комплексное исследование и разработка эффективных алгоритмов триангуляции простого многоугольника : диссертация кандидата технических наук : 05.13.18 Санкт-Петербург, 2006 140 c. : 61 06-5/1324
Объем: 140 стр.
Информация: Санкт-Петербург, 2006
Содержание:
1 Триангуляция простого многоугольника: аналитический обзор
11 Триангуляция простого многоугольника
12 Известные алгоритмы триангуляции простого многоугольника
121 Алгоритм декомпозиции на монотонные многоугольники
122 Алгоритм триангуляции простого многоугольника методомрасщепления вдоль хорды
123 Алгоритм триангуляции простого многоугольника методомсканирования Грэхема
124 Алгоритм трапецеидальной декомпозиции Тарьяна
125 Алгоритм трапецеидальной декомпозиции Киркпатрика
126 Алгоритм трапецеидальной декомпозиции Сайделя
127 Алгоритм трапецеидальной декомпозиции Чазелли
128 Алгоритм трапецеидальной декомпозиции АГР
129 Двойственность задач триангуляции простого многоугольника ипостроения трапецеидальной декомпозиции
1210
Выводы
2 Предложенные алгоритмы триангуляции простого многоугольника
21 Классификация алгоритмов триангуляции простогомногоугольника
22 Индексирование и кэширование
221 Модификация алгоритма Грэхема с использованиеминдексирования
222 Рандомизированный алгоритм триангуляции простогомногоугольника с использованием кэширования
223 Последовательный рандомизированный алгоритм триангуляциипростого многоугольника с использованием кэширования идинамической коррекции
224 Алгоритм трапецеидальной декомпозиции Сайделя с2использованием кэширования
225 Алгоритм триангуляции простого многоугольника спредобработкой
226 Параллельный алгоритм псевдотриангуляции простогомногоугольника
23
Выводы
3 Генерация простых многоугольников
31 Задача построения простого многоугольника
32 Алгоритмы генерации простого многоугольника
321 Алгоритм построения монотонных и немонотонных простыхмногоугольников методом сортировки
322 Алгоритм построения простых многоугольников методомполярной сортировки
323 Алгоритм построения простого многоугольника методом разделения пространства
324 Алгоритм построения простого многоугольника методомпоследовательной вставки
325 Алгоритм построения простого многоугольника методомтриангуляции Делоне
33 Примеры построенных простых многоугольников
34
Выводы
4 Вычислительная устойчивость алгоритмов триангуляции игенерации простого многоугольника
41 Причины возникновения ошибок при вычислениях
42 Применение целочисленной арифметики
43 Применение адаптивных операций вычисления
44 Поведение алгоритмов при применении вычислительноустойчивых схем
45
Выводы
5 Реализация и экспериментальное исследование алгоритмов
51 Проверка правильпости построенпых результатов
52 Основа экспериментального исследования
6 Сравнительный анализ алгоритмов триангуляции и генерациипростого многоугольника
61 Сравнительный анализ алгоритмов генерации простогомногоугольника
62 Сравнительный анализ алгоритмов триангуляции простыхмногоугольников
Введение:
Вычислительная геометрия (computational geometry) в настоящее времяявляется одной из быстро развивающихся областей компьютерной науки. Взначительной степени это связано с научным прогрессом в областикомпьютерных технологий. Достижения вычислительной геометрии икомпьютерной графики используются во многих классах программных систем:в геоинформационных системах (ГИС); системах автоматизированногопроектирования (САПР); в системах интерпретации данных; в системахвизуализации и анализа данных и т.п. С ростом мощности вычислительнойтехники появляется возможность рещать задачи, в том числе геометрическогохарактера, все больших и больших размеров. Триангуляции простогомногоугольника (ТПМ, декомпозиция многоугольника без самопересечений вколлекцию треугольников) как одной из базовых задач вычислительнойгеометрии уделяется немалое внимание. Множество специалистов по всемумиру внесли свой вклад в решение задачи триангуляции, среди них Ф. Препарата, М. Шеймос, Б. Чазелли, Д. Киркпатрик, Д. О'Рурк, Р. Сайдель, Р. Тарьян, Н. Амато, Д. Шевчук, М. Ласло, М. Гудрич, М. Хелд, Д. Рупперт, Т. Сеусл, Д. Добкин, Г. Туссан, К. Конг, А. Фурнье, Д. Монтуно, Д. Инчерпи, Скиена, А. Скворцов, Ю. Л. Костюк, А. Л. Фукс и многие другие.В сообществе специалистов по вычислительной геометрии в концепрошлого века были определены основные стратегические направленияразвития области. В качестве одного из основных стимулов развитиявычислительной геометрии рассматривается необходимость преодолениясуществующего разрыва между значительными теоретическими результатами,как правило, связанными с разработкой асимптотически оптимальных посложности алгоритмов, и практическим применением этих результатов вреальных вычислительных системах использующих комбинаторныегеометрические алгоритмы. В связи с этим актуальной темой становитсяразработка алгоритмов, возможно, имеющих неоптимальные асимптотическиехарактеристики сложности, но обеспечивающих лучшие характеристики в5среднем (при этом худший случай становится маловероятным) и имеющихэффективную программную реализацию (с учетом всей совокупности операцийалгоритма и накладных расходах, сопровождающих исполнение программы).Отметим, что для задачи ТПМ эта сторона дела особенно актуальна, так как,несмотря на наличие «математического» алгоритма Чазелли, имеющеголинейную сложность в худшем случае, но «безнадежного» для практическойреализации, задача ТПМ остается в известном списке «открытых проблемвычислительной геометрии».В России исследования в основном связаны с задачей триангуляцииДелоне (т.е. триангуляции заданного множества точек), так как она являетсябазовым блоком в построении геоинформационных систем. Есть хорошие иэффективные алгоритмы триангуляции Делоне и триангуляции Делоне сограничениями, предложенные А. Скворцовым, А. Л. Фуксом, Ю.Л. Костюком. Именно А. Скворцов одним из первых использовал техникукэширования для построения триангуляции Делоне, а А. Л. Фукс предложилспециальную технику предобработки входных данных, что позволило получитьдовольно быстрые алгоритмы триангуляции Делоне, имеющие линейнуюасимптотическую оценку в среднем. Задача ТПМ в работах российских авторовпочти не встречается.В зарубежных исследованиях ТПМ уделяется время не меньшее, чемтриангуляции Делоне, так как применение алгоритмов для ТПМ широкоиспользуется в различных прикладных областях. А именно: в системахавтоматизированного проектирования и разработки; в графических системахмоделирования и компьютерной графики; в космических и биологическихсистемах проектирования. И существует целый ряд задач в вычислительнойгеометрии, эффективное решение которых требует вычисления ТПМ как шагапредобработки, например, геометрическая декомпозиция, задача видимости,вычисление внутреннего расстояния между двумя точками многоугольника,определение видимости многоугольника из точки находящейся внутри6многоугольника, решение задачи о кратчайшем пути внутри многоугольника,проверка многоугольников на пересечение.Одна из основных проблем связана с вычислительной устойчивостьюалгоритмов. Алгоритмы ТПМ оперируют с веш,ественными координатами.Однако в силу особенностей реальных вещественных операций в компьютерахпочти всегда существует возможность некорректной работы алгоритмов. Присовременных объемах обрабатываемых данных такая вероятность очень велика.Именно поэтому в последние годы все большее внимание уделяется созданиювычислительно устойчивых (робастных) алгоритмов.Важно решить задачу ТПМ асимптотически хорошим алгоритмом всреднем, который бы учитывал вычислительные проблемы, работал быстро истроил правильную структуру триангуляции. При этом актуально поведениеизвестных алгоритмов на очень больших размерах и разных типах входныхданных.Целью диссертационной работы является комплексное исследование иразработка эффективных (быстрых и учитывающих специфику вещественнойарифметики) алгоритмов триангуляции простого многоугольника, разработкаэффективных алгоритмов генерации простых многоугольников заданного типас большим количеством вершин для проведения тестирования алгоритмовтриангуляции, создание набора программ реализующих алгоритмы ТПМ исравнительное исследование алгоритмов.Задачи работыВ рамках поставленной цели требовалось исследовать существующиеалгоритмы ТПМ. Предложить эффективные алгоритмы ТПМ с хорошимиасимптотическими оценками в среднем. Проанализировать вычислительныепроблемы, возникающие в алгоритмах ТПМ и методы их решения. Разработатьалгоритмы генерации простых многоугольников различных типов и размеров,обеспечивающих тестирование алгоритмов ТПМ. Провести сравнительныйанализ и исследование алгоритмов ТПМ. Методы исследования7При выполнении диссертационной работы использовались методывычислительной геометрии, компьютерной графики, аналитической геометрии,теории сложности алгоритмов и теории вероятности.Научная новизнаПредложены новые алгоритмы построения ТПМ, отличающиеся отизвестных применением различных методов предобработки входных данных, сиспользованием индексирования, кэширования и рандомизации, имеющиеасимптотически линейную или почти линейную сложность в среднем наравномерном распределении и обладающие лучшими временнымихарактеристиками, чем известные алгоритмы ТПМ. Предложены эффективные и вычислительно устойчивые алгоритмыТПМ. Практическая ценностьРазработан набор программ, реализующих предложенные алгоритмы иструктуры данных, которые позволяют эффективно строить ТПМ, а такженабор программ для генерации представительного класса простыхмногоугольников.Положения, выносимые на защиту1 Предложен последовательный рандомизированный алгоритм ТПМ сиспользованием кэширования и динамической коррекции, который имеетнаилучшие временные показатели среди всех исследованных алгоритмов.2 Предложена модификация алгоритма Грэхема с использованиеминдексирования, которая на не очень больших размерах многоугольника(до 20 000 вершин) имеет наилучшие временные показатели.3 Предложена модификация алгоритма Сайделя, основанная накэшировании трапеций в дереве локализации, улучшаюшаяпроизводительность оригинального алгоритма.4 Предложен параллельный алгоритм построения псевдотриангуляциипростого многоугольника85 Предложены алгоритмы генерации простых многоугольников, которыепозволяют генерировать представительный класс простыхмногоугольников.6 Разработан набор программ для решения задачи триангуляции(обеспечивающий, на основе рекомендаций, возможность выбораалгоритма для различных типов и размеров исходных данных) игенерации простого многоугольника7 Разработаны вычислительно устойчивые алгоритмы с использованиемадаптивной вещественной арифметики, корректно работающие наразличных многоугольниках с большим количеством вершин.ПубликацииПо теме диссертации опубликовано 11 научных работ, из них - 7 статей и4 работы в материалах международных и всероссийских научно-техническихконференций.Структура диссертацииРабота состоит из введения, 6 глав, заключения, списка литературы иприложений.В первой главе формулируется задача триангуляции, проводитсяаналитический обзор алгоритмов и методов решения задачи.Во второй главе приводится классификация алгоритмов триангуляциипростого многоугольника, описываются предложенные алгоритмы длятриангуляции. Вводятся предложенные автором алгоритмы триангуляциипростого многоугольника с асимптотическими оценками в среднем и худшемслучае, с использованием кэширования, индексирования, динамическойкоррекции, параллельной обработки и предобработки.В третьей главе приводится классификация и ставится задача построенияпростого многоугольника, описываются известные алгоритмы и вводятсяпредложенные автором алгоритмы для генерации простого многоугольника.Объясняется необходимость решения и сложность этой задачи. Приводятся9асимптотические оценки в среднем и худшем случаи. Даются примерысгенерированных многоугольников.В четвертой главе, обсуждается задача вычислительной устойчивостиалгоритмов генерации и триангуляции простого многоугольника, причинывозникновения ошибок при внутренних вычислениях, а также различныеметоды решения проблем, такие как целочисленная арифметика и применениеадаптивных алгоритмов точной арифметики. Рассматривается поведениеалгоритмов до, и после использования точной арифметики.В пятой главе описываются особенности реализации и постановкиэкспериментального исследования.В шестой главе проводится сравнительный анализ всех реализованныхалгоритмов, выявляются особенности поведения алгоритмов, предлагаютсярекомендации по использованию.101. ТРИАНГУЛЯЦИЯ ПРОСТОГО МНОГОУГОЛЬНИКА:АНАЛИТИЧЕСКИЙ ОБЗОР
