Разработка геометрических алгоритмов
Ключевые слова и синонимы
Сертифицированная и эффективная реализация геометрических алгоритмов; геометрические вычисления с сертифицированными численными данными и топологией
Постановка задачи
Преобразование теоретического геометрического алгоритма в эффективную компьютерную программу сопряжено с немалыми трудностями. Преодоление этих трудностей является задачей разработчиков геометрических алгоритмов, которые в более широком смысле занимаются проектированием и реализацией сертифицированных и эффективных решений алгоритмических задач, имеющих геометрическую природу. Типичными задачами этого семейства являются построение диаграмм Вороного, триангуляций, компоновки кривых и поверхностей (а именно – разбиений пространства), двух- и трехмерных поисковых структур, выпуклых оболочек и многого другого.
Геометрические алгоритмы тесно увязывают топологические или комбинаторные структуры (например, графы, описывающие триангуляцию множества точек), с одной стороны, с численной информацией (например, координатами вершин триангуляции) – с другой. Небольшие ошибки в численных вычислениях, допустимые во многих областях науки и техники, могут приводить к значительным изъянам в топологической структуре, способным вызвать сбой компьютерной программы, переход в бесконечный цикл или как минимум получение неверных результатов.
Прямолинейная реализация геометрических алгоритмов, описанная в учебнике, при помощи стандартной машинной арифметики, с огромной вероятностью окажется неудачной. Далее будут рассматриваться только сертифицированные решения – а именно такие решения, которые гарантированно строят точную желаемую структуру или ее хорошую аппроксимацию; такие решения нередко называются надежными.
Задачу разработки геометрических алгоритмов можно переформулировать следующим образом: необходимы проектирование и реализация геометрических алгоритмов, одновременно являющихся надежными и практически эффективными.
Трудности адаптации на практике существующей обширной алгоритмической литературы по вычислительной геометрии вызваны главным образом предположениями, обычными для теоретических исследований геометрических алгоритмов, которые заключаются в следующем: (1) входные данные находятся в общем положении, а именно, вырожденные входные данные исключены из рассмотрения; (2) вычисление выполняется на идеальном компьютере, поддерживающем операции арифметики действительных чисел с бесконечной точностью (так называемой модели «real RAM»); (3) стоимость операций на небольшом числе простых геометрических объектов соответствует «единичному» времени (например, пересечению трех сфер и сравнению двух целых чисел назначается одинаковая стоимость).
Напротив, в реальном мире геометрические входные данные часто являются вырожденными, точность машинных вычислений ограничена, а стоимость операций на небольшом числе простых геометрических объектов при помощи одного и того же алгоритма (исчисляемая по времени выполнения) может различаться в сотни раз и более того (при ориентации на сертифицированные результаты). Обычной внимательной реализации алгоритма может оказаться недостаточно, и часто приходится прибегать к редизайну.
Основные результаты
В последние годы были вложены значительные усилия в разработку и реализацию надежных программ вычислительной геометрии. Можно привести в пример два масштабных проекта – библиотеку CGAL [1] и геометрическую составляющую библиотеки LEDA [14]. Они были рассмотрены совместно в обзоре Кеттнер и Наэр [13]. Множество других релевантных проектов рассмотрены в обзоре Джосвига [12], содержащем обширный список ссылок на статьи и веб-сайты.
Приступая к реализации геометрического алгоритма, необходимо принять фундаментальное решение о том, на какой арифметике он будет базироваться, иначе говоря, следует ли рассчитывать на точное вычисление или использовать машинную арифметику с плавающей запятой. Существуют и другие, менее распространенные подходы. На данный момент библиотеки CGAL и LEDA основываются почти исключительно на точных вычислениях. Одна из причин этого выбора заключается в том, что точные вычисления моделируют идеальный компьютер (для ограниченных задач) и тем самым упрощают адаптацию алгоритмов из теоретической формы к программному продукту. Этому способствовал также значительный прогресс в разработке инструментов для эффективных вычислений с рациональными или алгебраическими числами (GMP [3], LEDA [14], CORE [2] и т. д.). На базе этих инструментов были разработаны продуманные техники сокращения объема точных вычислений, такие как фильтры с плавающей запятой и геометрическая фильтрация более высокого уровня.
Альтернативный подход заключается в использовании машинной арифметики с плавающей запятой, обладающей преимуществом высокой скорости. Однако ему далеко до идеальной арифметики с бесконечной точностью, с которой мы имеем дело при теоретическом исследовании геометрических алгоритмов, из-за чего алгоритмы приходится значительно перерабатывать. С рассуждениями по поводу неточности можно ознакомиться, например, в руководстве по QHULL – программе для нахождения выпуклой оболочки Барбера и др. [5]. За много лет было предложено немало специально адаптированных вариантов алгоритмов с плавающей запятой, среди которых, например, тщательно разработанный пакет VRONI авторства Хелда [11], вычисляющий диаграмму Вороного для точек и отрезков прямых при помощи стандартной арифметики с плавающей запятой, основанной на топологически ориентированном подходу Сугихары и Ири. На практике VRONI работает очень хорошо, однако он не является теоретически сертифицированным. Контролируемое возмущение [9] представляет собой последовательный метод получения сертифицированных аппроксимаций сложных геометрических конструктов с применением арифметики с плавающей запятой: Входные данные подвергаются возмущению таким образом, что все предикаты вычисляются точно даже при помощи машинной арифметики с ограниченной точностью, а используемый метод ограничивает необходимую величину возмущения, гарантируя успешное завершение вычисления.
Еще одно решение, которое необходимо принять, касается представления результата выполнения алгоритма; главная проблема обычно заключается в том, как представлять координаты вершин полученных структур. Любопытно, что этот вопрос остается столь же важным и в случае точных вычислений, поскольку могут получиться координаты, недопустимо большие или просто недоступные для конечного перечисления. (Стоит отметить, что многие геометрические алгоритмы являются только селективными – иначе говоря, они не производят новых геометрических объектов, а только выбирают и упорядочивают подмножества координат из входных данных. Например, результатом работы алгоритма вычисления выпуклой оболочки для множества точек является упорядочение подмножества исходных точек. Вычисления новых точек не производится. В данной статье мы обсуждаем главным образом алгоритмы, дающие на выходе новые геометрические конструкции – такие как точка пересечения двух прямых). Но даже при использовании арифметики с плавающей запятой некоторые могут предпочесть более компактное битовое представление чем, например, числа с двойной точностью. В этом направлении существует эффективное, хорошо изученное решение для случая с многоугольниками на плоскости под названием «выравнивание с привязкой» (snap rounding), которое позволяет привязать вершины и точки пересечения к вершинам сетки, сохраняя при этом определенные топологические свойства требуемой точной структуры. Выравнивание с гарантиями в общем случае представляет собой очень сложную задачу, и уже для многогранников в 3-мерном пространстве текущие попытки обобщения алгоритмы выравнивания с привязкой оказываются исключительно дорогостоящими (повышая сложность выравниваемых объектов до третьего и даже более высокого порядка).
Кроме того, существуют различные проблемы разработки в зависимости от решаемой задачи. Рассмотрим два примера исследований, в которых практический опыт радикально отличался от результата, следовавшего из асимптотических измерений. Эти примеры относятся к фундаментальным этапам многих геометрических алгоритмов – декомпозиции и локализации точек.
Декомпозиция
Базовым этапом многих геометрических алгоритмов является декомпозиция (возможно, сложного) геометрического объекта на более простые подобъекты, каждый из которых обычно имеет константную описательную сложность. Хорошо известным примером является триангуляция многоугольника. Выбор декомпозиции может значительно влиять на практическую эффективность различных алгоритмов, основанных на ней. В пример можно привести сумму Минковского многоугольников на плоскости. Сумма Минковского двух множеств A и B в пространстве Rd представляет собой векторную сумму двух множеств A (В B = fa + bja 2 A; b 2 Bg. Простейший подход вычисления сумм Минковского для двух многоугольников на плоскости содержит три этапа: Выполнить триангуляцию каждого многоугольника, вычислить сумму каждого треугольника одного многоугольника с каждым треугольником второго многоугольника, объединить все подсуммы. Для асимптотических измерений выбор триангуляции (а не альтернативных способов декомпозиции) не имеет определяющего эффекта. Однако на практике триангуляция, вероятно, является худшим вариантом по сравнению с другими выпуклыми декомпозициями, даже относительно простыми эвристическими (не обязательно оптимальными), что подтвердили эксперименты с различными методами декомпозиции [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 [7]. Более того, CGAL предлагает различные варианты триангуляций для разных областей применения. В числе вариантов применения триангуляций CGAL можно упомянуть генерацию сети, моделирование на молекулярном уровне, метеорологию, фотограмметрию и географические информационные системы (geographic information systems, GIS). Более подробную информацию о пакетах для триангуляции можно найти в обзоре Джосвига [12].
Расположение
Расположение кривых на плоскости поддерживается в CGAL [15], также как и огибающие поверхностей в трехмерном пространстве. Запланирована также поддержка расположений кривых на поверхностях. Расположения CGAL используются в алгоритмах планирования движений, системах автоматизированного конструирования и производства, ГИС, компьютерной графике и многих других (см. главу 1 в [6]).