Разработка геометрических алгоритмов: различия между версиями

Приступая к реализации геометрического алгоритма, необходимо принять фундаментальное решение о том, на какой арифметике он будет базироваться, иначе говоря, следует ли рассчитывать на точное вычисление или использовать машинную арифметику с плавающей запятой. Существуют и другие, менее распространенные подходы. На данный момент библиотеки CGAL и LEDA основываются почти исключительно на точных вычислениях. Одна из причин этого выбора заключается в том, что точные вычисления моделируют идеальный компьютер (для ограниченных задач) и тем самым упрощают адаптацию алгоритмов из теоретической формы к программному продукту. Этому способствовал также значительный прогресс в разработке инструментов для эффективных вычислений с рациональными или алгебраическими числами (GMP [3], LEDA [14], CORE [2] и т. д.). На базе этих инструментов были разработаны продуманные техники сокращения объема точных вычислений, такие как фильтры с плавающей запятой и геометрическая фильтрация более высокого уровня.

Альтернативный подход заключается в использовании машинной арифметики с плавающей запятой, обладающей преимуществом высокой скорости. Однако ему далеко до идеальной арифметики с бесконечной точностью, с которой мы имеем дело при теоретическом исследовании геометрических алгоритмов, из-за чего алгоритмы приходится значительно перерабатывать. С рассуждениями по поводу неточности можно ознакомиться, например, в руководстве по QHULL – программе для нахождения выпуклой оболочки Барбера и др. [5]. За много лет было предложено немало специально адаптированных вариантов алгоритмов с плавающей запятой, среди которых, например, тщательно разработанный пакет VRONI авторства Хелда [11], вычисляющий диаграмму Вороного для точек и отрезков прямых при помощи стандартной арифметики с плавающей запятой, основанной на топологически ориентированном подходу Сугихары и Ири. На практике VRONI работает очень хорошо, однако он не является теоретически сертифицированным. Контролируемое возмущение [9] представляет собой последовательный метод получения сертифицированных аппроксимаций сложных геометрических конструктов с применением арифметики с плавающей запятой: Входные данные подвергаются возмущению таким образом, что все предикаты вычисляются точно даже при помощи машинной арифметики с ограниченной точностью, а используемый метод ограничивает необходимую величину возмущения, гарантируя успешное завершение вычисления.

Еще одно решение, которое необходимо принять, касается представления результата выполнения алгоритма; главная проблема обычно заключается в том, как представлять координаты вершин полученных структур. Любопытно, что этот вопрос остается столь же важным и в случае точных вычислений, поскольку могут получиться координаты, недопустимо большие или просто недоступные для конечного перечисления. (Стоит отметить, что многие геометрические алгоритмы являются только селективными – иначе говоря, они не производят новых геометрических объектов, а только выбирают и упорядочивают подмножества координат из входных данных. Например, результатом работы алгоритма вычисления выпуклой оболочки для множества точек является упорядочение подмножества исходных точек. Вычисления новых точек не производится. В данной статье мы обсуждаем главным образом алгоритмы, дающие на выходе новые геометрические конструкции – такие как точка пересечения двух прямых). Но даже при использовании арифметики с плавающей запятой некоторые могут предпочесть более компактное битовое представление чем, например, числа с двойной точностью. В этом направлении существует эффективное, хорошо изученное решение для случая с многоугольниками на плоскости под названием «выравнивание с привязкой» (snap rounding), которое позволяет привязать вершины и точки пересечения к вершинам сетки, сохраняя при этом определенные топологические свойства требуемой точной структуры. Выравнивание с гарантиями в общем случае представляет собой очень сложную задачу, и уже для многогранников в 3-мерном пространстве текущие попытки обобщения алгоритмы выравнивания с привязкой оказываются исключительно дорогостоящими (повышая сложность выравниваемых объектов до третьего и даже более высокого порядка).