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

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

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

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

Базовым этапом многих геометрических алгоритмов является декомпозиция (возможно, сложного) геометрического объекта на более простые подобъекты, каждый из которых обычно имеет константную описательную сложность. Хорошо известным примером является триангуляция многоугольника. Выбор декомпозиции может значительно влиять на практическую эффективность различных алгоритмов, основанных на ней. В пример можно привести сумму Минковского многоугольников на плоскости. Сумма Минковского двух множеств A и B в пространстве <math>\mathbb{R}^d</math> представляет собой векторную сумму двух множеств <math>A \oplus B = \{a + b | a \in A, b \in B \}</math>. Простейший подход вычисления сумм Минковского для двух многоугольников на плоскости содержит три этапа: Выполнить триангуляцию каждого многоугольника, вычислить сумму каждого треугольника одного многоугольника с каждым треугольником второго многоугольника, объединить все подсуммы. Для асимптотических измерений выбор триангуляции (а не альтернативных способов декомпозиции) не имеет определяющего эффекта. Однако на практике триангуляция, вероятно, является худшим вариантом по сравнению с другими выпуклыми декомпозициями, даже относительно простыми эвристическими (не обязательно оптимальными), что подтвердили эксперименты с различными методами декомпозиции [4]. Причина в том, что триангуляция повышает общую сложность подсумм, что, в свою очередь, усложняет этап объединения – на константный коэффициент, однако на практике этот коэффициент сказывается весьма заметно. Аналогичные феномены наблюдались и в других ситуациях. Например, при использовании преимущественно вертикальной декомпозиции расположений она нередко оказывается слишком дорогостоящей по сравнению с более разреженными декомпозициями (т.е. декомпозициями, добавляющими меньше дополнительных функций).

В геометрических вычислениях часто встречается задача обработки заданного планарного подразбиения (плоской карты), которая позволила бы эффективно отвечать на вопросы о местонахождении точек: пусть дана точка q на плоскости; в какой грани карты содержится q? За много лет в рамках проекта CGAL было реализовано множество алгоритмов локализации точки на плоской карте, в частности, иерархическая структура поиска, гарантирующая логарифмическое время выполнения запроса после предварительной обработки карты с n контурами, выполняемой за ожидаемое время O(n log n). Этот алгоритм в библиотеке CGAL носит название алгоритма локализации точек RIC и выполняется после этапа предобработки, использующего рандомизированный алгоритм с пошаговым построением (randomized incremental construction). Кроме того, было реализовано несколько более простых для программирования алгоритмов локализации точек. Однако ни один из них не превосходит RIC по скорости выполнения запросов. Однако с точки зрения предобработки RIC на сегодняшний день является самым медленным из всех реализованных алгоритмов, что во многих сценариях приводит к неэффективности его использования. Один из более простых разработанных методов представляет собой вариант хорошо известного алгоритма прыжков и переходов (jump-and-walk) для локализации точек. Алгоритм разбрасывает по карте точки, так называемые ориентиры, использует их (вместе с содержащими их гранями) в структуре поиска ближайших соседей. После выдачи запроса о точке q алгоритм находит ближайший к q ориентир I и «переходит» по карте из I в q по соединяющему их отрезку прямой. Подход на основе ориентиров обеспечивает лишь ненамного большее время выполнения запроса по сравнению с RIC, зато очень эффективен на этапе предобработки. Его детальное изложение можно найти в работе [10]. Это еще одно соображение, которое необходимо учитывать при проектировании (геометрических) алгоритмов: стоимость предобработки (и хранения) по сравнению со стоимостью выполнения запроса. Нередко эффективный (на практике) компромисс между этими параметрами приходится находить экспериментальным путем.

Расположение кривых на плоскости поддерживается в CGAL [15], также как и огибающие поверхностей в трехмерном пространстве. Запланирована также поддержка расположений кривых на поверхностях. Расположения CGAL используются в алгоритмах планирования движений, системах автоматизированного конструирования и производства, ГИС, компьютерной графике и многих других (см. главу 1 в [6]).

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

* [[Отказоустойчивые геометрические вычисления]]