Содержание к диссертации
Введение
1 Триангуляция простого многоугольника: аналитический обзор 10
1.1 Триангуляция простого многоугольника 10
1.2 Известные алгоритмы триангуляции простого многоугольника 15
1.2.1 Алгоритм декомпозиции на монотонные многоугольники 15
1.2.2 Алгоритм триангуляции простого многоугольника методом расщепления вдоль хорды 18
1.2.3 Алгоритм триангуляции простого многоугольника методом сканирования Грэхема 21
1.2.4 Алгоритм трапецеидальной декомпозиции Тарьяна 23
1.2.5 Алгоритм трапецеидальной декомпозиции Киркпатрика 24
1.2.6 Алгоритм трапецеидальной декомпозиции Сайделя 25
1.2.7 Алгоритм трапецеидальной декомпозиции Чазелли 31
1.2.8 Алгоритм трапецеидальной декомпозиции АГР 32
1.2.9 Двойственность задач триангуляции простого многоугольника и построения трапецеидальной декомпозиции 39
1.2.10 Выводы 40
2 Предложенные алгоритмы триангуляции простого многоугольника .. 41
2Л Классификация алгоритмов триангуляции простого многоугольника 41
2.2 Индексирование и кэширование 43
2.2.1 Модификация алгоритма Грэхема с использованием индексирования 43
2.2.2 Рандомизированный алгоритм триангуляции простого многоугольника с использованием кэширования 46
2.2.3 Последовательный рандомизированный алгоритм триангуляции простого многоугольника с использованием кэширования и динамической коррекции 49
2.2.4 Алгоритм трапецеидальной декомпозиции Сайделя с
использованием кэширования 53
2.2.5 Алгоритм триангуляции простого многоугольника с предобработкой 55
2.2.6 Параллельный алгоритм псевдотриангуляции простого многоугольника 58
2.3 Выводы 61
3 Генерация простых многоугольников 63
3.1 Задача построения простого многоугольника 63
3.2 Алгоритмы генерации простого многоугольника 65
3.2.1 Алгоритм построения монотонных и немонотонных простых многоугольников методом сортировки 66
3.2.2 Алгоритм построения простых многоугольников методом полярной сортировки 69
3.2.3 Алгоритм построения простого многоугольника методом разделения пространства 70
3.2.4 Алгоритм построения простого многоугольника методом последовательной вставки 72
3.2.5 Алгоритм построения простого многоугольника методом триангуляции Делоне 74
3.3 Примеры построенных простых многоугольников 77
3.4 Выводы 82
4 Вычислительная устойчивость алгоритмов триангуляции и генерации простого многоугольника 84
4.1 Причины возникновения ошибок при вычислениях 86
4.2 Применение целочисленной арифметики 94
4.3 Применение адаптивных операций вычисления 97
4.4 Поведение алгоритмов при применении вычислительно устойчивых схем 101
4.5 Выводы 102
5 Реализация и экспериментальное исследование алгоритмов 103
5.1 Проверка правильности построенных результатов 103
5.2 Основа экспериментального исследования 106
6 Сравнительный анализ алгоритмов триангуляции и генерации простого многоугольника 110
6.1 Сравнительный анализ алгоритмов генерации простого многоугольника 111
6.2 Сравнительный анализ алгоритмов триангуляции простых многоугольников 115
6.3 Выводы и рекомендации 131
7 Заключение 132
Список литературы
- Известные алгоритмы триангуляции простого многоугольника
- Рандомизированный алгоритм триангуляции простого многоугольника с использованием кэширования
- Алгоритм построения монотонных и немонотонных простых многоугольников методом сортировки
- Применение целочисленной арифметики
Введение к работе
Вычислительная геометрия (computational geometry) в настоящее время является одной из быстро развивающихся областей компыотерной науки. В значительной степени это связано с научным прогрессом в области компьютерных технологий. Достижения вычислительной геометрии и компьютерной графики используются во многих классах программных систем: в геоинформационных системах (ГИС); системах автоматизированного проектирования (САПР); в системах интерпретации данных; в системах визуализации и анализа данных и т.п. С ростом мощности вычислительной техники появляется возможность решать задачи, в том числе геометрического характера, все больших и больших размеров. Триангуляции простого многоугольника (ТПМ, декомпозиция многоугольника без самопересечений в коллекцию треугольников) как одной из базовых задач вычислительной геометрии уделяется немалое внимание. Множество специалистов по всему миру внесли свой вклад в решение задачи триангуляции, среди них Ф. Препарата, М. Шеймос, Б. Чазелли, Д. Киркпатрик, Д. О'Рурк, Р. Сайдель, Р. Тарьян, Н. Амато, Д. Шевчук, М. Ласло, М. Гудрич, М. Хелд, Д. Рупперт, Т. Сеусл, Д. Добкин, Г. Туссан, К. Конг, А. Фурнье, Д. Монтуно, Д. Инчерпи, С. Скиена, А. С. Скворцов, Ю. Л. Костюк, А. Л. Фукс и многие другие.
В сообществе специалистов по вычислительной геометрии в конце прошлого века были определены основные стратегические направления развития области. В качестве одного из основных стимулов развития вычислительной геометрии рассматривается необходимость преодоления существующего разрыва между значительными теоретическими результатами, как правило, связанными с разработкой асимптотически оптимальных по сложности алгоритмов, и практическим применением этих результатов в реальных вычислительных системах использующих комбинаторные геометрические алгоритмы. В связи с этим актуальной темой становится разработка алгоритмов, возможно, имеющих неоптимальные асимптотические характеристики сложности, но обеспечивающих лучшие характеристики в
среднем (при этом худший случай становится маловероятным) и имеющих эффективную программную реализацию (с учетом всей совокупности операций алгоритма и накладных расходах, сопровождающих исполнение программы). Отметим, что для задачи ТПМ эта сторона дела особенно актуальна, так как, несмотря на наличие «математического» алгоритма Чазелли, имеющего линейную сложность в худшем случае, но «безнадежного» для практической реализации, задача ТПМ остается в известном списке «открытых проблем вычислительной геометрии».
В России исследования в основном связаны с задачей триангуляции Делоне (т.е. триангуляции заданного множества точек), так как она является базовым блоком в построении геоинформационных систем. Есть хорошие и эффективные алгоритмы триангуляции Делоне и триангуляции Делоне с ограничениями, предложенные А. С. Скворцовым, А. Л. Фуксом, ІО.Л. Костюком. Именно А. С. Скворцов одним из первых использовал технику кэширования для построения триангуляции Делоне, а А. Л. Фукс предложил специальную технику предобработки входных данных, что позволило получить довольно быстрые алгоритмы триангуляции Делоне, имеющие линейную асимптотическую оценку в среднем. Задача ТПМ в работах российских авторов почти не встречается.
В зарубежных исследованиях ТПМ уделяется время не меньшее, чем триангуляции Делоне, так как применение алгоритмов для ТПМ широко используется в различных прикладных областях. А именно: в системах автоматизированного проектирования и разработки; в графических системах моделирования и компьютерной графики; в космических и биологических системах проектирования. И существует целый ряд задач в вычислительной геометрии, эффективное решение которых требует вычисления ТПМ как шага предобработки, например, геометрическая декомпозиция, задача видимости, вычисление внутреннего расстояния между двумя точками многоугольника, определение видимости многоугольника из точки находящейся внутри
6 многоугольника, решение задачи о кратчайшем пути внутри многоугольника, проверка многоугольников на пересечение.
Одна из основных проблем связана с вычислительной устойчивостью алгоритмов. Алгоритмы ТПМ оперируют с вещественными координатами. Однако в силу особенностей реальных вещественных операций в компьютерах почти всегда существует возможность некорректной работы алгоритмов. При современных объемах обрабатываемых данных такая вероятность очень велика. Именно поэтому в последние годы все большее внимание уделяется созданию вычислительно устойчивых (робастных) алгоритмов.
Важно решить задачу ТПМ асимптотически хорошим алгоритмом в среднем, который бы учитывал вычислительные проблемы, работал быстро и строил правильную структуру триангуляции. При этом актуально поведение известных алгоритмов на очень больших размерах и разных типах входных данных.
Целью диссертационной работы является комплексное исследование и разработка эффективных (быстрых и учитывающих специфику вещественной арифметики) алгоритмов триангуляции простого многоугольника, разработка эффективных алгоритмов генерации простых многоугольников заданного типа с большим количеством вершин для проведения тестирования алгоритмов триангуляции, создание набора программ реализующих алгоритмы ТПМ и сравнительное исследование алгоритмов.
Задачи работы
В рамках поставленной цели требовалось исследовать существующие алгоритмы ТПМ. Предложить эффективные алгоритмы ТПМ с хорошими асимптотическими оценками в среднем. Проанализировать вычислительные проблемы, возникающие в алгоритмах ТПМ и методы их решения. Разработать алгоритмы генерации простых многоугольников различных типов и размеров, обеспечивающих тестирование алгоритмов ТПМ. Провести сравнительный анализ и исследование алгоритмов ТПМ.
Методы исследования
При выполнении диссертационной работы использовались методы вычислительной геометрии, компьютерной графики, аналитической геометрии, теории сложности алгоритмов и теории вероятности.
Научная новизна
Предложены новые алгоритмы построения ТПМ, отличающиеся от известных применением различных методов предобработки входных данных, с использованием индексирования, кэширования и рандомизации, имеющие асимптотически линейную или почти линейную сложность в среднем на равномерном распределении и обладающие лучшими временными характеристиками, чем известные алгоритмы ТПМ.
Предложены эффективные и вычислительно устойчивые алгоритмы ТПМ.
Практическая ценность
Разработан набор программ, реализующих предложенные алгоритмы и структуры данных, которые позволяют эффективно строить ТПМ, а также набор программ для генерации представительного класса простых многоугольников.
Положения, выносимые на защиту
Предложен последовательный рандомизированный алгоритм ТПМ с использованием кэширования и динамической коррекции, который имеет наилучшие временные показатели среди всех исследованных алгоритмов.
Предложена модификация алгоритма Грэхема с использованием индексирования, которая на не очень больших размерах многоугольника (до 20 000 вершин) имеет наилучшие временные показатели.
Предложена модификация алгоритма Сайделя, основанная на кэшировании трапеций в дереве локализации, улучшающая производительность оригинального алгоритма.
Предложен параллельный алгоритм построения псевдотриангуляции простого многоугольника
Предложены алгоритмы генерации простых многоугольников, которые позволяют генерировать представительный класс простых многоугольников.
Разработан набор программ для решения задачи триангуляции (обеспечивающий, на основе рекомендаций, возможность выбора алгоритма для различных типов и размеров исходных данных) и генерации простого многоугольника
Разработаны вычислительно устойчивые алгоритмы с использованием адаптивной вещественной арифметики, корректно работающие на различных многоугольниках с большим количеством вершин. Публикации
По теме диссертации опубликовано 11 научных работ, из них - 7 статей и 4 работы в материалах международных и всероссийских научно-технических конференций.
Структура диссертации
Работа состоит из введения, 6 глав, заключения, списка литературы и приложений.
В первой главе формулируется задача триангуляции, проводится аналитический обзор алгоритмов и методов решения задачи.
Во второй главе приводится классификация алгоритмов триангуляции простого многоугольника, описываются предложенные алгоритмы для триангуляции. Вводятся предложенные автором алгоритмы триангуляции простого многоугольника с асимптотическими оценками в среднем и худшем случае, с использованием кэширования, индексирования, динамической коррекции, параллельной обработки и предобработки.
В третьей главе приводится классификация и ставится задача построения простого многоугольника, описываются известные алгоритмы и вводятся предложенные автором алгоритмы для генерации простого многоугольника. Объясняется необходимость решения и сложность этой задачи. Приводятся
асимптотические оценки в среднем и худшем случаи. Даются примеры сгенерированных многоугольников.
В четвертой главе, обсуждается задача вычислительной устойчивости алгоритмов генерации и триангуляции простого многоугольника, причины возникновения ошибок при внутренних вычислениях, а также различные методы решения проблем, такие как целочисленная арифметика и применение адаптивных алгоритмов точной арифметики. Рассматривается поведение алгоритмов до, и после использования точной арифметики.
В пятой главе описываются особенности реализации и постановки экспериментального исследования.
В шестой главе проводится сравнительный анализ всех реализованных алгоритмов, выявляются особенности поведения алгоритмов, предлагаются рекомендации по использованию.
Известные алгоритмы триангуляции простого многоугольника
Данный алгоритм относится к классу прямых алгоритмов с итеративной обработкой. Это самый известный способ триангуляции простого многоугольника предложенный в 1978 году [48], который впервые позволил осуществить триангуляцию произвольного п -угольника путем выполнения двух операций, а именно декомпозиции простого многоугольника в коллекцию монотонных многоугольников и дальнейшей триангуляции каждого монотонного многоугольника. Используя технологию заметающей прямой, алгоритм выполняет декомпозицию на монотонные многоугольники за время O(nlogn) и триангуляцию монотонных частей за время 0(п).
Алгоритм описывается в работе, так как выбран для реализации и исследования, как базовый алгоритм для решения задачи триангуляции простого многоугольника и в нем описываются основные понятие необходимые для дальнейшего описания предложенных алгоритмов.
Определение: говорят, что цепочка вершин монотонная, если любая вертикальная линия пересекает ее не более одного раза.
Определение: многоугольник называется монотонным, если его граница составлена из двух монотонных цепочек вершин, верхней и нижней цепочек вершин многоугольника.
Пусть р будет монотонный многоугольник и его вершины переименованы в порядке увеличения координаты х, vpv2,...,v„. Алгоритм триангуляции монотонно многоугольника формирует последовательность монотонных многоугольников р р1,р2,,..,ри=0. Многоугольник рп как результат обработки вершины vt, получается путем отсечения нуля или нескольких треугольников от предыдущего многоугольника р1А.
Алгоритм хранит стек s вершин, которые были проверены, но еще не обработаны полностью. Перед началом обработки вершины v, в стеке содержатся некоторые вершины, принадлежащие многоугольнику /?,_,. На рисунке 2 изображены возможные три случая обработки информации в стеке во время триангуляции простого монотонного многоугольника.
Три случая, которые могут возникнуть при триангуляции монотонного многоугольника. Шаг триангуляции монотонного многоугольника занимает 0(п), доказательство можно найти в [20][21].
Алгоритм декомпозиции на монотонные использует сканирование на плоскости для регуляризации п-угольника за время O(n\ogri) [47].
Используемый алгоритм основан на определении понятия излома. Вогнутая вершина - вершина, внутренний угол которой превышает 180 градусов - является изломом, если обе соседние вершины лежат либо слева, либо справа от нее. Легко видеть, что никакой монотонный многоугольник не может содержать излом. Это правило обратимо и выражается следующей теоремой, лежащей в основе алгоритма:
Теорема, (о монотонности многоугольника)[20]: любой многоугольник, не содержащий излома, является монотонным. Доказательство теоремы можно найти в [20][21].
Алгоритм выполняется путем декомпозиции многоугольника Р на многоугольники без изломов. В первой из двух фаз по мере продвижения сканирующей линии слева направо алгоритм удаляет изломы, направленные влево, формируя набор многоугольников Р1,Рг,...,Рт, ни один из которых не содержит изломов, направленных влево. Во время второй фазы алгоритм удаляет изломы, направленные вправо, продвигая сканирующую линию, справа налево по многоугольникам Рг Полученная коллекция многоугольников и будет декомпозицией исходного многоугольника Р на многоугольники, в которых нет ни право, ни лево-направленных изломов и, следовательно, совсем никаких изломов.
Рандомизированный алгоритм триангуляции простого многоугольника с использованием кэширования
Предложенный алгоритм принадлежит к классу итеративных алгоритмов, решающих прямую задачу с использованием кэширования. В отличие от предыдущего алгоритма текущая триангуляция последовательно перестраивается и осуществляется так называемая динамическая коррекция текущей триангуляции [4]. Структура данных и методика кэширования аналогичны предыдущему алгоритму.
Заметим, что ссылки на измененные треугольники из кэша не удаляются, а предполагается, что каждый удаленный треугольник, как запись в памяти компьютера превращается в новый треугольник, и поэтому допустимость ссылок на треугольники не нарушается при работе алгоритма. На один и тот же треугольник кэш-таблица может многократно ссылаться, а на некоторые треугольники ссылки могут вообще отсутствовать. Это позволяет упростить процедуру перестроения кэша.
Алгоритм триангуляции можно описать следующим образом:
Шаг 1. Строим охватывающий многоугольник- четырехугольник (новые четыре точки добавляются в структуру локализации). Берем первую точку многоугольника и соединяем ее с вершинами четырехугольника, полученную триангуляцию из четырех треугольников устанавливаем как начальную Тгй. Далее заполняем весь кэш г ссылками на эти четыре треугольника.
Шаг 2. Берем /-ю (очередную) точку многоугольника и проводим ее локализацию в Тг,.х. Обновляем кэш (присваиваем ячейке кэша ссылку на локализованный треугольник). Перестраиваем 7 м в Тгп применяя первую операцию механизма перестроения (см. ниже).
ШагЗ. Берем ребро многоугольника, соединяющее /-ю и (; -1)-ю точки, и проводим его через триангуляцию Тгп перестраивая ее с помощью второй операции механизма перестроения (см. ниже).
Шаг 4. Если следующая точка уже обрабатывалась, то проводим последнее ребро многоугольника через триангуляцию ТУ,, иначе переходим к шагу 2.
Шаг 5. Обходим многоугольник вдоль границы против часовой стрелки и выбрасываем все треугольники, находящиеся вне многоугольника.
Основные операции механизма перестроения: Операция 1. При локализации новой точки в текущей триангуляции найденный треугольник разбивается на три новых (если точка попадает на отрезок, то оба соседних треугольника разбиваются на два).
Добавлять ребро можно по-разному, в данном алгоритме это делается следующим образом: удаляются все пересекаемые ребра, а для полученных двух многоугольников (по обе стороны от ребра) выполняется простая триангуляция (см. 1.2.3). В качестве простого алгоритма можно использовать алгоритм «Сканирование Грэхема», который для многоугольников небольшого размера работает быстро, либо использовать модифицированный вариант этого алгоритма с индексированием точек, что не сильно влияет на время триангуляции, так как многоугольники для перестроения получаются очень маленьких размеров. Algorithm BEGIN 1 Tr(0) = охватывающий четырехугольник; 2 Добавить в Тг(0), точкур(0), чтобы получить Тг(1); {на выходе четыре треугольника) 3 FORi:=I TOk DO {k - количество ячеек в кэше} 4 Rfi]:— ссылка на треугольник, в который попадает какая-либо точка из і-ой ячейки; 5 FORi:=lTOn DO 6 BEGIN 7 Локализацияp(i) в Tr(i-I); {Tr(i-1).triangle — локализованный треугольник} 8 R[i]: = ссылка на Tr(і-1). triangle; 9 Добавить в Tr(i-I), точкуp(i), чтобы получить Tr(i); 10 Добавить в Tr(i), ребро(р(і-1),р(і)); 11 END; 12 ClearfP, Tr(n)); {Удалить все ребра вне триангуляции многоугольника} END.
Приведем асимптотические оценки для алгоритма. Пусть дана триангуляция на множестве точек, равномерно распределенных в квадрате. Пусть даны два треугольника из этой триангуляции. Тогда для перехода из одного треугольника в другой в направлении, соединяющем некоторые точки этих треугольников, в худшем случае требуется 0(4п) операций перехода по треугольникам в триангуляции [23],
Основные шаги в этом алгоритме - это локализации точки в триангуляции (строка 7) и добавление ребра в многоугольник (строка 10). Итак, в худшем случае локализация каждой точки в триангуляции множества точек, может занимать 0(л/и) операций перехода (что было показано ранее). При использовании рандомизации входных данных можно говорить о математическом ожидании количества операций. Пусть на і-ом шаге построена Тг(і) в ней не более чем Зі-6 ребер, и у нас есть ссылки на локализованные треугольники в кэше. Экспериментально установлено, что количество операций перехода по кэш таблицы при локализации не зависит от /, и количество операций перестроения ребер в текущей триангуляции тоже не зависит от /. Следовательно, оценка алгоритма в среднем 0(п) [6].
Также важно, что можно указать случай, когда количество перестроений при добавлении отрезка многоугольника почти на каждом шаге будет иметь зависимость от и и алгоритм будет квадратичным (рисунок 7). Однако на практике такой случай маловероятен, благодаря рандомизации порядка обработки ребер и специфической формы набора отрезков, что почти не встречается если работать с простыми многоугольниками.
Алгоритм построения монотонных и немонотонных простых многоугольников методом сортировки
Алгоритм относится к классу интуитивных алгоритмов с предобработкой множества точек. Построение простого многоугольника осуществляется с помощью сортировки следующим образом: Для сгенерированного на равномерном распределении случайного множества точек S, осуществляется сортировка в лексикографическом порядке (сначала сортируются по координате х, а потом уже если необходимо по у) и точки последовательно соединяются (рисунок 3).
Исходное множество S Отсортированное соединение После соединения отсортированных точек множества S, получаем многоугольную монотонную цепь. Если создать такую же цепь, но ниже прямой L, и соединить их, то получаем монотонный многоугольник. Для упрощения реализация делается проще: выбираем две крайние точки многоугольной цепи и дублируем их на краю плоскости, таким образом, получится простой монотонный многоугольник (рисунок 4).
Асимптотическая оценка построения такого многоугольника определяется оценкой для задачи сортировки. Таким образом, асимптотическая оценка генерации простого монотонного многоугольника 0(n\ogn). Но ее можно улучшить, если не важно распределение точек на плоскости, и тогда генерация многоугольника будет выполняться за линейное время. Для этого генерируется упорядоченная последовательность точек изначально. Это делается следующим образом: генерируется первая точка s0 случайно, а следующая точка генерируется по принципу sk = sk_1+rand(A). А- некоторый очень маленький интервал, по одной из координат. Таким образом, сразу генерируется последовательность упорядоченных точек и оценка для построения многоугольника - 0{п).
Для построения немонотонного простого многоугольника с помощью сортировки используется следующая схема: пространство разбивается на к квадратов, в каждом из этих квадратов строится монотонный многоугольник размером (п-а)/к (рисунок 5), и они соединяются (рисунок 6). Где а количество точек необходимых для соединения .
Полученный немонотонный многоугольник Этот алгоритм относится к классу рекурсивных с предобработкой исходного множества точек [3]. Время построения подобных многоугольников асимптотически линейно, но такие многоугольники нельзя назвать произвольными, так в их структуре есть определенная регулярность.
Алгоритм также как и предыдущий относится к классу интуитивных алгоритмов с предобработкой множества точек. Основное отличие от алгоритма методом сортировки заключается в том, что сортировка осуществляется по полярному углу (рисунки 7,8).
Исходное множество S Отсортированное множество S по полярному углу относительно одной из точек Рис. 7. Все асимптотические характеристики и предложенные модификации, аналогичны алгоритму генерации методом сортировки.
Рис. 8. Обратим внимание на то что, несмотря на регулярность построения, подобные многоугольники не имеют в себе такое количество монотонных частей, и таким образом образуют другой топологический класс многоугольников, очень привлекательный для исследования и анализа большинства алгоритмов триангуляции простого многоугольника. Алгоритм строит произвольный простой многоугольник за оптимальное количество операций и принадлежит к классу рекурсивных алгоритмов. Рекурсивно делит множество точек пока в подмножестве не окажется всего две точки (или одна), а потом строит отрезок и рекурсивно соединяет отрезки в
Разделение множества 5" Алгоритм рекурсивно разделяет исходное множество точек на подмножества, которые имеют разные выпуклые оболочки. Пусть S будет таким подмножеством S. (Тогда, CH(S ) (выпуклая оболочка S ) не содержит не одной точки из S\S .) Когда генерируется многоугольник Р гарантируется, что пересечение Р с CH(S ) состоит из единственной цепи. Первая точка этой цепи обозначается s f, а ее последняя точка обозначается s]. Заметим, что и s f, и s, находятся на границе CH(S ).
Во время фазы инициализации алгоритма выбирается s f и sj из 5" случайно. Тогда оставшиеся точки разделяются на левое и правое подмножество линией iis s]). Для общего вызова рекурсии алгоритма рассмотрим подмножество S созданное этим рекурсивным разделением и пусть s f будет его первой точкой, a s] будет его последней точкой. Если s f И s] это последние точки в 5", тогда выходом является отрезок соединяющий ЭТИ две точки и рекурсия останавливается. Иначе, 5і расщепляется в два подмножества S" и 5 " следующим образом: 1. Выбирается случайно точка s из S . 2. Проводится случайная линия / через У такая что / пересекает отрезок s f s]. Линия / разделяет 5" в два подмножества S" и 5 ", где S" имеет s f в качестве начала и s в качестве конца. Аналогично, S"" имеет sl в качестве начала и s] в качестве конечной точки (рисунок 9) Procedure CreatePartion(S, size, є) Begin If size 2 then Begin 51 = подмножество S левее e; 52 = подмножество S правее e; eO = отрезок проходящий через середину є; el = (eO, конец точки є); е2 = (начало точки є, еО); CreatePartion(Sl, size(Sl), el); CreatePartion(S2, size(S2), e2); End; If size = 2 then InsertPointlnPolygonQ; конец рекурсии End.
Применение целочисленной арифметики
Как известно, все современные процессоры представляют вещественные числа в форме ±маптимса-2жс"от""" . Например, в четырех битовой арифметике двоичное число 1101 представляется в виде 1.101x2 .
Два вещественных числа х и у называются неналагаемыми, если последний ненулевой бит числа х более значим, чем первый значащий бит числа у, или наоборот. Например, двоичные числа 1100 и -10.1 — неналагаемые, тогда как 101 и 10 являются налагаемыми. Разложение числа является неналагаемым, если все компоненты разложения являются неналагаемыми. Нужно заметить, что число можно представить в виде неналагаемого разложения несколькими способами, например, 1100 + (-10.1) = 1001 + 0.1 = 1000 + 1 + 0.1. Неналагаемое разложение необходимо, например, для того, чтобы быстро определить знак числа (знак компоненты, наибольшей по величине) или для получения грубого приближения числа (оно равно наибольшей по величине компоненте).
Два вещественных числах та.у называются смежными, если они налагаемые и если х налагается с 2у, или наоборот, т.е. 2х налагается с у. Например, 1100 — смежное с 11, но 1000 не является смежным с 11. Разложение числа несмежно, если никакие две из его компонент не являются смежными. Как ни странно, любое вещественное число представимо в виде соответствующего несмежного разложения. Например, 11111 = 100000 + (-1).
Все алгоритмы точной арифметики основываются на допущении, что операции сложения, вычитания, умножения выполняются с точным округлением. Это означает, что если точный результат может быть сохранен в -битной мантиссе, то результат операции будет точным, иначе он округляется до ближайшего р-битного вещественного числа. Например, в четырехбитной арифметике произведение 111x101 = 100011 округляется до числа 1.001 25.
Обозначим символами Ф,0 и вычисление р-битного сложения, вычитания и умножения с точным округлением.
Округление часто характеризуется с помощью величины ulp, которая расшифровывается как units in the last place, т.е. "единицы на последнем месте". ulp является эффективной характеристикой для бита низшего порядка (р-го бита) мантиссы. Например, для четырех битовой арифметики ulp{—1100) 1, іф(І) = 0.001. Обозначим через err{ab) ошибку округления, полученную при выполнении операции с использованием /?-битной арифметики. Нужно заметить, что ulp — беззнаковая величина, тогда как еп{авЬ) имеет знак. Для любой из основных операций (сложение, вычитание, умножение и деление), ab = a b + err(a&b), точная арифметика гарантирует, что \err{ab)\ -ulp{ab).
Адаптивные алгоритмы
Широко известны основные определения операций при работе с точной арифметикой, так что перейдем к самим адаптивным алгоритмам для решения основных задач вычислительной устойчивости [15]-[17].
Все адаптивные алгоритмы, использованные в работе, были заимствованы у Д. Шевчука [70] и потому в работе нет их описания. Но для формализации базы для работы с этими алгоритмами приведем адаптивный алгоритм вычисления квадрат расстояния между двумя точками (ax-bx)2+(ay -by) . На риунке 7 представлен неадаптивный. (а) Формула для квадрата расстояния между двумя точками а и b. (Ь) Нижнее подвыражение в дереве представлено как сумма аппроксимированного значения и ошибки округления, (с) Простой возрастающий адаптивный метод для вычисления выражения. Аппроксимации А} и А2 генерируются и тестируются по очереди. Окончательное расширение As - точное. Каждый At включает все термы размера 0(d }) или больше, и имеет ошибку не больше чем 0(e). (d) Чрезвычайная возрастающая адаптивность. Три дерева подвыражений Т0, Tt и Т2 сами по себе вычисляются адаптивно. Каждый 5, содержит только термы необходимые для уменьшения его ошибки ДО O(f )).
