Polygon Sponsor

BOOST.POLYGON 库

Boost.Polygon 库提供专注于操作平面多边形几何数据的算法。提供的具体算法包括多边形集合运算（交集、并集、差集、异或并集）以及相关算法，例如多边形连通图提取、偏移和地图叠加。图 c 中展示了图 a 和图 b 的异或并集的示例。这些所谓的布尔运算算法在 GIS（地理空间信息系统）、VLSI CAD 以及所有其他 CAD 领域以及许多其他应用领域都具有重要意义，提供这些算法是本库的主要目标。Boost.Polygon 库的范围并不旨在涵盖计算几何的所有方面，而是提供一套用于处理坐标、点、区间和矩形的能力，这些能力是实现和交互多边形数据结构和算法所必需的。

该库的一个重要特性是实现了通用的扫描线算法，用于构建 2D 点和线性段的 Voronoi 图（作为 GSoC 2010 项目的一部分开发）。Voronoi 图数据结构在图像分割、光学字符识别、最近邻查询执行等领域有应用。它与其它计算几何概念密切相关：Delaunay 三角剖分、中轴线、直线骨架、最大的空圆。Boost.Polygon 库提供了构建点（图 a）和线段（图 b，后者可用于离散化任何二维曲线）的 Voronoi 图的接口。图 c 包含非凸多边形的中轴线示例。该实现 性能优于 大多数已知的商业和非商业库，无论是在效率还是数值鲁棒性方面。您可以在 Voronoi 主页 上找到有关该主题的更多详细信息。

坐标数据类型是库提供的所有数据类型和算法的模板参数，并且被期望为整型。由于实现浮点鲁棒性需要一套不同的算法，并且通常需要依赖于平台特定的浮点表示假设，因此库实现的算法不支持浮点坐标数据类型。有关该库及其实现的更详细讨论，包括与其他开源替代品的基准比较，请参阅 2009 年 BoostCon 的 论文 和 演示文稿，以及对库核心算法运行时复杂度的详细 分析。

多边形库的设计理念是创建一个 API，用于在用户几何数据类型上调用其提供的库算法，该 API 应最大程度地直观、最少地出错，并易于集成到预先存在的应用程序中。基于 C++ Concepts 的模板元编程与泛型运算符重载相结合，可以在不牺牲底层算法的运行时或内存效率的情况下实现这些设计目标。该 API 旨在展示基于 C++ Concepts 的库接口可以轻松实现什么，但它是基于当前语言特性实现的。此 API 使以下代码片段（操作非库几何类型）成为可能：

在上面的代码片段中，假设的多边形类型 CPolygon 已映射到库的多边形概念，并与库 API 一起使用，以根据多边形列表 a 的边界框裁剪多边形列表 b，并将结果与由某个整数量收缩的多边形列表 a 进行异或并集。最终结果被累积到一个多边形列表中，并进行并集运算。描述这种 API 用法比编写代码需要更多的输入，而且描述并不比代码本身清晰多少。一图胜千言。

在 Boost.Polygon 中，如上所示的操作是命名清晰的自由函数，或者重载了 C++ 运算符，使得从代码阅读中很容易推断出预期结果。运算符包含在命名空间boost::polygon::operators中，以便它们可以在boost::polygon命名空间之外使用，而无需引入整个boost::polygon命名空间。遵循最小惊讶原则，推断的行为通常应该与实际行为相匹配。诸如参数顺序（输出参数在前）和跨不同函数一致地应用相同语义（累积）之类的约定，可以降低新用户的学习曲线，同时减少高级用户记忆许多不同函数的语义和参数顺序的需要。

虽然实现此 API 的内部库代码通常因大量使用模板元编程而变得复杂且晦涩难懂，但库 API 在用户代码中的应用通常简单明了，因为它没有任何多余的语法。唯一的例外是用户类型到库概念的映射，这需要用户执行一些简单的模板编程并理解库概念类型系统的工作原理。以下示例应有助于用户执行这些编程任务。

• 示例文件
  • point_usage.cpp 使用库提供的点数据类型和函数
  • custom_point.cpp 将用户定义的点类映射到库的 point_concept
  • polygon_usage.cpp 使用库提供的多边形数据类型和函数
  • custom_polygon.cpp 将用户定义的多边形类映射到库的 polygon_concept
  • polygon_set_usage.cpp 使用库提供的多边形集数据类型和函数
  • custom_polygon_set.cpp 将用户定义的类映射到库的 polygon_set_concept
  • connectivity_extraction_usage.cpp 使用连通性提取算法在多边形上构建连通图
  • property_merge_usage.cpp 在多边形数据上使用 n 层地图叠加算法
• 教程
  • 布局与原理图 学习如何应用 Boost.Polygon 功能来实现简化的电路提取应用程序
  • Minkowski 和 学习如何应用 Boost.Polygon 功能来实现多边形集的 Minkowski 和
  • Voronoi 基础教程 学习如何构建、遍历、可视化、将数据与 Voronoi 图关联，而无需深入了解库的细节。
  • Voronoi 高级教程 学习如何使用用户提供的坐标类型配置 Voronoi 构建器和 Voronoi 图数据结构。

我们要感谢：Thomas Klimpel、Frank Mori Hess、Barend Gehrels、Andreas Fabri、Jeffrey Hellrung、Tim Keitt、Markus Werle、Paul A. Bristow、Robert Stewart、Mathias Gaunard、Michael Fawcett、Steven Watanabe、Joachim Faulhaber、John Bytheway、Sebastian Redl、Mika Heiskanen、John Phillips、Kai Benndorf、Hartmut Kaiser、Arash Partow、Maurizio Vitale、Brandon Kohn、David Abrahams、Gordon Woodhull、Daniel James、John Maddock、Tom Brinkman、Bo Persson、Mateusz Loskot、Christian Henning、Jean-Sebastien Stoezel，感谢他们在 Boost 提交过程中为本库提供反馈和/或正式评审，并感谢 Fernando Cacciola 担任评审经理。