Разработка геометрических алгоритмов
Ключевые слова и синонимы
Сертифицированная и эффективная реализация геометрических алгоритмов; геометрические вычисления с сертифицированными численными данными и топологией
Постановка задачи
Преобразование теоретического геометрического алгоритма в эффективную компьютерную программу сопряжено с немалыми трудностями. Преодоление этих трудностей является задачей разработчиков геометрических алгоритмов, которые в широком смысле слова занимаются проектированием и реализацией сертифицированных и эффективных решений алгоритмических задач, имеющих геометрическую природу. Типичными задачами этого семейства являются построение диаграмм Вороного, триангуляций, расположения кривых и поверхностей (а именно – разбиений пространства), двух- и трехмерных поисковых структур, выпуклых оболочек и многого другого.
Геометрические алгоритмы тесно увязывают топологические или комбинаторные структуры (например, графы, описывающие триангуляцию множества точек), с одной стороны, с численной информацией (например, координатами вершин триангуляции) – с другой. Небольшие ошибки в численных вычислениях, допустимые во многих областях науки и техники, могут приводить к значительным изъянам в топологической структуре, способным вызвать сбой компьютерной программы, переход в бесконечный цикл или как минимум получение неверных результатов.
Прямолинейная реализация геометрических алгоритмов, описанная в учебнике, при помощи стандартной машинной арифметики, с огромной вероятностью окажется неудачной. Далее будут рассматриваться только сертифицированные решения – а именно такие решения, которые гарантированно строят точную желаемую структуру или ее хорошую аппроксимацию; такие решения нередко называются надежными.
Задачу разработки геометрических алгоритмов можно переформулировать следующим образом: необходимы проектирование и реализация геометрических алгоритмов, одновременно являющихся надежными и практически эффективными.
Трудности адаптации на практике существующей обширной алгоритмической литературы по вычислительной геометрии вызваны главным образом предположениями, обычными для теоретических исследований геометрических алгоритмов, которые заключаются в следующем: (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 в пространстве [math]\displaystyle{ \mathbb{R}^d }[/math] представляет собой векторную сумму этих множеств [math]\displaystyle{ 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 ориентир l и «переходит» по карте из l в q по соединяющему их отрезку прямой. Подход на основе ориентиров обеспечивает лишь ненамного большее время выполнения запроса по сравнению с RIC, зато очень эффективен на этапе предобработки. Его детальное изложение можно найти в работе [10]. Это еще одно соображение, которое необходимо учитывать при проектировании (геометрических) алгоритмов: стоимость предобработки (и хранения) по сравнению со стоимостью выполнения запроса. Нередко эффективный на практике компромисс между этими параметрами приходится находить экспериментальным путем.
Применение
Геометрические алгоритмы полезны во многих областях. Триангуляции и расположения представляют собой примеры простых конструкций, активно изучавшихся в вычислительной геометрии, продуманно реализованных и прошедших множество экспериментов, а также используемых в самых разных системах.
Триангуляция
Триангуляции в двух и трех измерениях были реализованы в CGAL [7]. Более того, CGAL предлагает различные варианты триангуляций для разных областей применения. В числе вариантов применения триангуляций CGAL можно упомянуть генерацию сети, моделирование на молекулярном уровне, метеорологию, фотограмметрию и географические информационные системы (geographic information systems, GIS). Более подробную информацию о пакетах для триангуляции можно найти в обзоре Джосвига [12].
Расположение
Расположение кривых на плоскости поддерживается в CGAL [15], также как и огибающие поверхностей в трехмерном пространстве. Запланирована также поддержка расположений кривых на поверхностях. Расположения CGAL используются в алгоритмах планирования движений, системах автоматизированного конструирования и производства, ГИС, компьютерной графике и многих других случаях (см. главу 1 в [6]).
Открытые вопросы
Несмотря на значительный прогресс в области сертифицированной реализации эффективных геометрических алгоритмов, существующие теоретические алгоритмические решения для многих задач по-прежнему требуют адаптации или редизайна, чтобы быть достаточно полезными на практике. Одним из примеров ситуации, когда прогресс может иметь значительный резонанс, могла бы стать разработка эффективных декомпозиций для криволинейных геометрических объектов (например, расположений) на плоскости и в более высоких размерностях. Как упоминалось ранее, подходящие способы декомпозиции оказывают значительное влияние на практическую эффективность геометрических алгоритмов.
Сертифицированные геометрические вычисления с фиксированной точностью уступают традиционным точным вычислениям в отношении доступных и надежных программных продуктов, и продвижение в этом направлении представляется серьезной проблемой. К примеру, создание сертифицированного аналога CGAL с плавающей запятой является крайне желанной (и при этом весьма сложной) целью.
Еще одним инструментом, нехватка которого серьезно ощутима, является непротиворечивое и эффективное округление геометрических объектов. Как уже упоминалось ранее, существует достаточно удовлетворительное решение для многоугольных объектов на плоскости. Однако пока не разработано хороших техник для криволинейных объектов на плоскости и для объектов более высоких размерностей (как линейных, так и криволинейных).
Ссылка на код
См. также
Литература
Статьи по данной теме публиковали такие конференции, как симпозиум ACM по вычислительной геометрии (ACM Symposium on Computational Geometry, SoCG), семинар по разработке и экспериментальному выполнению алгоритмов (Workshop on Algorithm Engineering and Experiments, ALENEX), секция разработки и применения приложений Европейского симпозиума по алгоритмам (Engineering and Applications Track of the European Symposium on Algorithms, ESA), его предшественник и семинар по экспериментальным алгоритмам (Workshop on Experimental Algorithms, WEA). Материалы по теме можно найти в следующих журналах: «Журнал ACM по экспериментальной алгоритмике» (ACM Journal on Experimental Algorithmics), «Вычислительная геометрия: теория и применение» (Computational Geometry: Theory and Applications) и «Международный журнал по вычислительной геометрии и ее применению» (International Journal of Computational Geometry and Applications). Широкий спектр важных аспектов геометрических вычислений получил освещение в сборнике под редакцией Буассона и Тейо [6] под названием «Эффективная вычислительная геометрия для кривых и поверхностей».
1. Сайт проекта CGAL. http://www.cgal.org/. По состоянию на 6 апреля 2008 г.
2. Сайт библиотеки CORE. http://www.cs.nyu.edu/exact/core/. По состоянию на 6 апреля 2008 г.
3. Сайт GMP. http://gmplib.org/. По состоянию на 6 апреля 2008 г.
4. Agarwal, P.K., Flato, E., Halperin, D.: Polygon decomposition for efficient construction of Minkowski sums. Comput. Geom. Theor.Appl. 21 (1-2), 39-61 (2002)
5. Barber, C.B., Dobkin, D.P., Huhdanpaa, H.T.: Imprecision in QHULL. http://www.qhull.org/html/qh-impre.htm. Accessed 6 Apr 2008
6. Boissonnat, J.-D., Teillaud, M. (eds.) Effective Computational Geometry for Curves and Surfaces. Springer, Berlin (2006)
7. Boissonat, J.-D., Devillers, O., Pion, S., Teillaud, M., Yvinec, M.: Triangulations in CGAL Comput. Geom. Theor. Appl. 22(1-3), 5-19(2002)
8. Fabri, A., Giezeman, G.-J., Kettner, L., Schirra, S., Schonherr, S.: On the design of CGAL a computational geometry algorithms library. Softw. Pract. Experience 30(11), 1167-1202 (2000)
9. Halperin, D., Leiserowitz, E.: Controlled perturbation for arrangements of circles. Int. J. Comput. Geom. Appl. 14(4-5), 277-310(2004)
10. Haran, I., Halperin, D.: An experimental study of point location in general planar arrangements. In: Proceedings of 8th Workshop on Algorithm Engineering and Experiments, pp. 16-25 (2006)
11. Held, M.: VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments. Comput. Geom. Theor. Appl. 18(2), 95-123 (2001)
12. Joswig, M.: Software. In: Goodman, J.E., O'Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., chap. 64, pp. 1415-1433. Chapman & Hall/CRC, Boca Raton (2004)
13. Kettner, L, Naher, S.: Two computational geometry libraries: LEDA and CGAL. In: Goodman, J.E., O'Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, Chapter 65, pp. 1435-1463, 2nd edn. Chapman & Hall/CRC, Boca Raton (2004)
14. Mehlhorn, K., Naher, S.: LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (2000)
15. Wein, R., Fogel, E., Zukerman, B., Halperin, D.: Advanced programming techniques applied to CGAL'S arrangement package. Comput. Geom. Theor. Appl. 36(1-2), 37-63 (2007)