Polygon 赞助商

BOOST.POLYGON 库

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

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

坐标数据类型是库提供的所有数据类型和算法的模板参数，并且应为整数类型。由于实现浮点鲁棒性意味着需要一组不同的算法，并且通常需要对浮点表示进行特定于平台的假设，因此库中实现的算法不支持浮点坐标数据类型。有关库及其实现的更多详细讨论，包括与其他开源替代方案的基准比较，请参阅 论文和 演示文稿（来自 boostcon 2009），以及对库核心算法的运行时复杂性的详细分析。

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

在上面的代码片段中，假设的多边形类型 CPolygon 已映射到库多边形概念，并与库 API 一起使用，以将多边形列表 *b* 裁剪到多边形列表 *a* 的边界框，并将其与缩小了某个整数值的多边形列表 *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 功能来实现简化的电路提取应用程序
  • 闵可夫斯基和 了解如何应用 Boost.Polygon 功能来实现多边形集的闵可夫斯基和
  • 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 慷慨地担任审查经理。