Polygon Sponsor

THE BOOST.POLYGON LIBRARY

Библиотека Boost.Polygon предоставляет алгоритмы, ориентированные на манипулирование плоскими данными геометрии многоугольника.   Предоставляемые конкретные алгоритмы представляют собой операции с множеством многоугольников (пересечение, объединение, различие, разделение) и связанные с ними алгоритмы, такие как извлечение графа связи многоугольника, взаимозачет и наложение карты.   Пример разъединения (XOR) рисунка а и рисунка b показан ниже на рисунке c.  Эти так называемые булевы алгоритмы представляют значительный интерес для ГИС (геопространственных информационных систем), САПР VLSI, а также всех других областей САПР и многих других областей применения, и их обеспечение является основным направлением этой библиотеки.   Начало. Библиотека полигонов не предназначена для охвата всей вычислительной геометрии в ее объеме и предоставляет набор возможностей для работы с координатами, точками, интервалами и прямоугольниками, которые необходимы для поддержки реализации и взаимодействия с многоугольными структурами данных и алгоритмами.  

Одной из важных особенностей библиотеки является реализация общего алгоритма стреловидности для построения диаграмм Вороной точек и линейных сегментов в 2D (разработан в рамках программы GSoC 2010). Структура данных диаграммы Воронои имеет приложения в сегментации изображений, оптическом распознавании символов, выполнении запросов ближайшего соседа. Он тесно связан с другими концепциями вычислительной геометрии: Делаунайская триангуляция, медиальная ось, прямой скелет, самый большой пустой круг. Начало. Библиотека Polygon предоставляет интерфейс для построения диаграммы Voronoi точек фигуры а и сегментов строки фигуры b (последняя может быть использована для дискретизации любой двумерной кривой). Рисунок c содержит пример медиальной оси невыпуклого полигона. Реализация превосходит большинство известных коммерческих и некоммерческих библиотек как по эффективности, так и по численной надежности. Более подробную информацию по теме можно найти на главной странице Вороной.

Координатный тип данных является шаблонным параметром всех типов данных и алгоритмов, предоставляемых библиотекой, и, как ожидается, будет интегральным. Типы данных координат плавающей точки не поддерживаются алгоритмами, реализованными в библиотеке, из-за того, что достижение устойчивости плавающей точки подразумевает другой набор алгоритмов и, как правило, конкретные предположения платформы о представлениях плавающей точки.   Для дополнительного подробного обсуждения библиотеки и ее реализации, включая сравнение с другими альтернативами с открытым исходным кодом paper и presentation из boostcon 2009, а также подробный анализ сложности среды выполнения основных алгоритмов библиотеки.

Философия дизайна полигонной библиотеки заключалась в создании API для вызова библиотечных алгоритмов, которые она предоставляет по типам данных геометрии пользователя, которые максимально интуитивно понятны, минимально подвержены ошибкам и легко интегрируются в существующие приложения. Метапрограммирование на основе шаблонов на основе C++ в сочетании с общей перегрузкой оператора отвечает этим целям проектирования, не жертвуя временем выполнения или эффективностью памяти базовых алгоритмов.   API предназначен для демонстрации того, что может быть легко достигнуто с помощью библиотечного интерфейса на основе C++-концепций, но реализован на основе текущих языковых функций.   Этот API делает возможным следующий фрагмент кода, который работает на типах небиблиотечной геометрии:

В фрагменте кода выше гипотетического полигона тип CPolygon был отображен на концепцию библиотечного полигона и используется с библиотечными API для срезания списка полигонов b против ограничивающей коробки полигонного списка a и применить разъединение этого списка с полигонным списком a с отклонением на некоторое целое число.   Конечный результат накапливается в список полигонов с союзной операцией.   Для описания этого использования API значительно больше набора текста, чем для его кодирования, и описание не намного яснее, чем сам код.   Картина стоит тысячи слов.

В Росте. Операции на полигоне, такие как показанные выше, являются свободными функциями, названными в честь того, что они делают, или представляют собой перегрузки операторов C++, которые позволяют легко сделать вывод из чтения кода, чего ожидать.   Операторы содержатся в пространстве имен boost::polygon::operators, чтобы их можно было использовать за пределами пространства имен boost::polygon без внесения всего пространства имен boost::polygon. Следуя принципу наименьшего удивления, предполагаемое поведение, как правило, должно соответствовать фактическому поведению. Конвенции, такие как упорядочивание аргументов (аргументы выхода на первый план) и последовательное применение одной и той же семантики для различных функций (накопления), уменьшают кривую обучения для новых пользователей, одновременно уменьшая необходимость запоминания семантики и упорядочивания аргументов для многих различных функций для продвинутых пользователей.

В то время как внутренний библиотечный код, реализующий этот API, обычно сложен и зашифрован из-за интенсивного использования метапрограммирования шаблонов, применение библиотечного API в пользовательском коде обычно просто и понятно, потому что он свободен от любого постороннего синтаксиса.   Единственным исключением из этого является сопоставление типов пользователей с библиотечными концепциями, что требует от пользователя выполнения некоторого простого программирования шаблонов и понимания некоторых внутренних элементов работы системы типов библиотечных концепций.   Приведенные ниже примеры должны помочь пользователю в выполнении этих задач программирования.

• Примеры файлов:
  • point_usage.cppИспользуя предоставленные библиотекой точечные данные, тип и функции
  • custom_point.cppСопоставление определенного пользователем класса точек с библиотечной точкой_concept
  • polygon_usage.cppИспользуя библиотеку предоставлены многоугольные типы данных и функции
  • custom_polygon.cppСопоставление класса полигона пользователя с библиотечным полигоном_концепцией
  • polygon_set_usage.cppИспользуя библиотеку, предоставленный многоугольный набор типов данных и функций
  • custom_polygon_set.cppСопоставление класса, определенного пользователем, с библиотечным полигоном_set_concept
  • connectivity_extraction_usage.cppИспользование алгоритма извлечения связи для построения графа связи на полигонах
  • property_merge_usage.cppИспользование n-слойного алгоритма наложения карты на данные полигона
• Оригинальное название:
  • Layout Versus SchematicНаучитесь применять тягу. Возможности полигона для реализации упрощенного приложения извлечения схемы
  • Минковский СуммУзнайте, как применять Boost. Возможности полигона для реализации наборов многоугольников Минковского
  • Основной учебник ВоронойУзнайте, как строить, пересекать, визуализировать, ассоциировать данные с диаграммами Вороной, не копаясь в деталях библиотеки.
  • Voronoi Advanced TutorialУзнайте, как настроить конструктор Voronoi и структуру данных диаграммы Voronoi с помощью предоставленных пользователем типов координат.

Мы хотели бы поблагодарить: Томаса Климпела, Фрэнка Мори Хесса, Баренда Герельса, Андреаса Фабри, Джеффри Хеллрунга, Тима Кейтта, Маркуса Верле, Пола А. Бристоу, Роберта Стюарта, Матиаса Гаунара, Майкла Фосетта, Стивена Ватанабе, Йоахима Фаулхабера, Джона Байтвея, Себастьяна Редла, Мику Хейсканена, Джона Филлипса, Кай Бенндорфа, Хартмута Кайзера, Араша Партоу, Маурицио Витале, Брэндона Кона, Дэвида Абрахамса, Гордона Вудхула, Дэниела Джеймса, Джона Мэддока, Тома Бринкмана, Бо Перссона, Матеуша Лоскота, Кристиана Хеннинга, Жана-Себастьяна Стозеля за предоставление обратной связи и или формального обзора библиотеки в рамках процесса подачи заявок на повышение и Фернандо Каччи.