Monthly Archives: Сентябрь 2011

Библиотека вычислительной геометрии

Пожалуй, среди библиотек алгоритмов вычислительной геометрии на языке C++ наиболее широко известна достаточно развитая библиотека CGAL. В последнее время у меня возникло желание несколько «развернуть» логику построения библиотеки вычислительной геометрии для упрощения формулировки алгоритмов, которые мне приходилось реализовывать.

Базовый блок — вектор.

FixedVector: n-мерный вектор, размерность жёстко фиксирована;
BoundedVector: n-мерный вектор, размерность жёстко ограничена сверху.

Оба варианта не требуют управления памятью в духе std::vector, создавать их разумно в рамках пула (например, boost::pool_allocator) или в стеке.

CGAL различает точку и вектор в рамках аффинной структуры. Это заманчиво (проверка компилятором корректности выражений), но лично мне, скорее, мешало, поэтому пока что ограничимся только понятием вектора и работой с множествами векторов (слово «точка» ниже считается синонимом слова «вектор»).

Набор векторов определяет базис, с которым можно выполнять следующие операции:

  • преобразовать в (минимальную по количеству векторов) ортонормированную форму (для нормирования нужно отдельно задавать способ вычисления нормы или нормирования, непосредственно вектора можно сравнивать только на равенство, они «не умеют» считать свою длину);
  • определить разложимость по векторам базиса некоего вектора или другого базиса (принадлежность подпространству);
  • определить ортогональность базису вектора или другого базиса;
  • сложить с другим базисом (объединить вектора и упростить);
  • построить кобазис (вектора, недостающие базису подпространства до базиса полного пространства);
  • пересечение базисов = кобазис суммы кобазисов;
  • разность базисов = кобазис суммы кобазиса «уменьшаемого» с базисом «вычитаемого».

Система координат — базис и offset-вектор (можно считать точкой начала координат). Система координат задаёт линейное многообразие. Если базис заменить на кобазис (описывает левую часть системы линейных уравнений), а offset-вектор использовать как правую часть СЛУ, то это также можно использовать как описание линейного многообразия. Что удобнее, зависит от ситуации, в частности, гиперплоскость, скорее, удобнее описывать кобазисом, т.к. он состоит из одного уравнения / вектора нормали.

Для двух линейных многообразий можно попробовать построить множество равноудалённых точек. В общем случае это (сдвинутая) квадрика, но может оказаться и линейным многообразием, например, (в интересном для меня с практической точки зрения) случае двух гиперплоскостей. Множества равноудалённых точек имеют отношение к таких структурам как диаграмма Вороного (двойственная триангуляции Делоне, пользуясь которой, в свою очередь, можно построить выпуклую оболочку) и скелет многогранника (разбиение внутренности многогранника на области, связанные с ближайшей гранью). Эти структуры полезны в задачах геометрического поиска, операциях над многогранниками.

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

Алгоритмы: O(N log N + K) пересечение isobox‘ов (построение графа инцидентности), O(N log N) удаление доминируемых элементов.

Выпуклая оболочка множества точек может быть представлена многогранником с полной структурой (например, через триангуляцию Делоне) или просто набором а) опорных вершин или б) опорных гиперплоскостей (в которых лежат грани). Далее — построение алгебраической суммы и геометрической разности выпуклых многогранников, а возможно, и теоретико-множественные операции (впрочем, я сомневаюсь в близкой возможности реализации их для произвольных многогранников, это слишком большая задача).

Реклама