4551
правка
Разработка геометрических алгоритмов: различия между версиями
Перейти к навигации
Перейти к поиску
Разработка геометрических алгоритмов (посмотреть исходный код)
Версия от 13:57, 25 января 2019
, 25 января 2019→Основные результаты
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Сертифицированная и эффективная реализация геометрически…») |
Irina (обсуждение | вклад) |
||
| Строка 21: | Строка 21: | ||
== Основные результаты == | == Основные результаты == | ||
В последние годы были вложены значительные усилия в разработку и реализацию надежных программ вычислительной геометрии. Можно привести в пример два масштабных проекта – библиотеку CGAL [1] и геометрическую составляющую библиотеки LEDA [14]. Они были рассмотрены совместно в обзоре Кеттнер и Наэр [13]. Множество других релевантных проектов рассмотрены в обзоре Джосвига [12], содержащем обширный список ссылок на статьи и веб-сайты. | |||
Приступая к реализации геометрического алгоритма, необходимо принять фундаментальное решение о том, на какой арифметике он будет базироваться, иначе говоря, следует ли рассчитывать на точное вычисление или использовать машинную арифметику с плавающей запятой. Существуют и другие, менее распространенные подходы. На данный момент библиотеки CGAL и LEDA основываются почти исключительно на точных вычислениях. Одна из причин этого выбора заключается в том, что точные вычисления моделируют идеальный компьютер (для ограниченных задач) и тем самым упрощают адаптацию алгоритмов из теоретической формы к программному продукту. Этому способствовал также значительный прогресс в разработке инструментов для эффективных вычислений с рациональными или алгебраическими числами (GMP [3], LEDA [14], CORE [2] и т. д.). На базе этих инструментов были разработаны продуманные техники сокращения объема точных вычислений, такие как фильтры с плавающей запятой и геометрическая фильтрация более высокого уровня. | |||
Альтернативный подход заключается в использовании машинной арифметики с плавающей запятой, обладающей преимуществом высокой скорости. Однако ему далеко до идеальной арифметики с бесконечной точностью, с которой мы имеем дело при теоретическом исследовании геометрических алгоритмов, из-за чего алгоритмы приходится значительно перерабатывать. С рассуждениями по поводу неточности можно ознакомиться, например, в руководстве по QHULL – программе для нахождения выпуклой оболочки Барбера и др. [5]. За много лет было предложено немало специально адаптированных вариантов алгоритмов с плавающей запятой, среди которых, например, тщательно разработанный пакет VRONI авторства Хелда [11], вычисляющий диаграмму Вороного для точек и отрезков прямых при помощи стандартной арифметики с плавающей запятой, основанной на топологически ориентированном подходу Сугихары и Ири. На практике VRONI работает очень хорошо, однако он не является теоретически сертифицированным. Контролируемое возмущение [9] представляет собой последовательный метод получения сертифицированных аппроксимаций сложных геометрических конструктов с применением арифметики с плавающей запятой: Входные данные подвергаются возмущению таким образом, что все предикаты вычисляются точно даже при помощи машинной арифметики с ограниченной точностью, а используемый метод ограничивает необходимую величину возмущения, гарантируя успешное завершение вычисления. | |||
Еще одно решение, которое необходимо принять, касается представления результата выполнения алгоритма; главная проблема обычно заключается в том, как представлять координаты вершин полученных структур. Любопытно, что этот вопрос остается столь же важным и в случае точных вычислений, поскольку могут получиться координаты, недопустимо большие или просто недоступные для конечного перечисления. (Стоит отметить, что многие геометрические алгоритмы являются только селективными – иначе говоря, они не производят новых геометрических объектов, а только выбирают и упорядочивают подмножества координат из входных данных. Например, результатом работы алгоритма вычисления выпуклой оболочки для множества точек является упорядочение подмножества исходных точек. Вычисления новых точек не производится. В данной статье мы обсуждаем главным образом алгоритмы, дающие на выходе новые геометрические конструкции – такие как точка пересечения двух прямых). Но даже при использовании арифметики с плавающей запятой некоторые могут предпочесть более компактное битовое представление чем, например, числа с двойной точностью. В этом направлении существует эффективное, хорошо изученное решение для случая с многоугольниками на плоскости под названием «выравнивание с привязкой» (snap rounding), которое позволяет привязать вершины и точки пересечения к вершинам сетки, сохраняя при этом определенные топологические свойства требуемой точной структуры. Выравнивание с гарантиями в общем случае представляет собой очень сложную задачу, и уже для многогранников в 3-мерном пространстве текущие попытки обобщения алгоритмы выравнивания с привязкой оказываются исключительно дорогостоящими (повышая сложность выравниваемых объектов до третьего и даже более высокого порядка). | |||
Кроме того, существуют различные проблемы разработки в зависимости от решаемой задачи. Рассмотрим два примера исследований, в которых практический опыт радикально отличался от результата, следовавшего из асимптотических измерений. Эти примеры относятся к фундаментальным этапам многих геометрических алгоритмов – декомпозиции и локализации точек. | |||
'''Декомпозиция''' | |||