Комплексное исследование и разработка эффективных алгоритмов триангуляции простого многоугольника

Вычислительная геометрия (computational geometry) в настоящее время является одной из быстро развивающихся областей компьютерной науки. В значительной степени это связано с научным прогрессом в области компьютерных технологий. Достижения вычислительной геометрии и компьютерной графики используются во многих классах программных систем: в геоинформационных системах (ГИС) — системах автоматизированного проектирования (САПР) — в системах интерпретации данныхв системах визуализации и анализа данных и т. п. С ростом мощности вычислительной техники появляется возможность решать задачи, в том числе геометрического характера, все больших и больших размеров. Триангуляции простого многоугольника (ТПМ, декомпозиция многоугольника без самопересечений в коллекцию треугольников) как одной из базовых задач вычислительной геометрии уделяется немалое внимание. Множество специалистов по всему миру внесли свой вклад в решение задачи триангуляции, среди них Ф. Препарата, М. Шеймос, Б. Чазелли, Д. Киркпатрик, Д. О’Рурк, Р. Сайдель, Р. Тарьян, Н. Амато, Д. Шевчук, М. Ласло, М. Гудрич, М. Хелд, Д. Рупперт, Т. Сеусл, Д. Добкин, Г. Туссан, К. Конг, А. Фурнье, Д. Монтуно, Д. Инчерпи, С. Скиена, А. С. Скворцов, Ю. J1. Костюк, A. J1. Фукс и многие другие.

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

В России исследования в основном связаны с задачей триангуляции Делоне (т.е. триангуляции заданного множества точек), так как она является базовым блоком в построении геоинформационных систем. Есть хорошие и эффективные алгоритмы триангуляции Делоне и триангуляции Делоне с ограничениями, предложенные А. С. Скворцовым, A. J1. Фуксом, Ю. Л. Костюком. Именно А. С. Скворцов одним из первых использовал технику кэширования для построения триангуляции Делоне, a A. J1. Фукс предложил специальную технику предобработки входных данных, что позволило получить довольно быстрые алгоритмы триангуляции Делоне, имеющие линейную асимптотическую оценку в среднем. Задача ТПМ в работах российских авторов почти не встречается.

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

Одна из основных проблем связана с вычислительной устойчивостью алгоритмов. Алгоритмы ТПМ оперируют с вещественными координатами. Однако в силу особенностей реальных вещественных операций в компьютерах почти всегда существует возможность некорректной работы алгоритмов. При современных объемах обрабатываемых данных такая вероятность очень велика. Именно поэтому в последние годы все большее внимание уделяется созданию вычислительно устойчивых (робастных) алгоритмов.

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

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

Задачи работы.

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

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

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

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

Предложены эффективные и вычислительно устойчивые алгоритмы.

ТПМ.

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

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

Положения, выносимые на защиту.

1 Предложен последовательный рандомизированный алгоритм ТПМ с использованием кэширования и динамической коррекции, который имеет наилучшие временные показатели среди всех исследованных алгоритмов.

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

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

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

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

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

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

По теме диссертации опубликовано 11 научных работ, из них — 7 статей и 4 работы в материалах международных и всероссийских научно-технических конференций.

Структура диссертации.

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

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

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

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

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

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

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

Выводы по главам подробно представлены в работе. В данном разделе представлены общие выводы по работе и перспективы использования результатов.

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

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

7.

ЗАКЛЮЧЕНИЕ

.