CGAL: 2D Arrangement 的概念和使用

这篇文章里面我会梳理一下 CGAL 官方文档对于 2D Arrangements 的介绍。源文档地址是：CGAL 5.4.1 - 2D Arrangments。CGAL 的文档一般都具有比较大的体量，直接读不太容易理清楚，故再整理一遍。

---

Arrangments 是对 Geometry Arrangements 的简称，这个词语不太好直接翻译成中文，故下文中我们都直接称英文的原名称。Arrangement 的概念是

Geometric arrangements, or arrangements for short, are subvisions of some space induced by geometry objects.

简而言之，Arrangements 是指由一组元素产生的对空间的分割。下面的图给出了一个例子：

图中给出了平面中的两个曲线 c1 和 c2，这两个曲线产生了两个有界的面 (Faces) f1 和 f2（图中阴影区域）。同时，图中两个曲线还产生了 7 个顶点（包含曲线自身的首尾点）以及 8 个边。Arrangement 的概念可以进一步从平面扩展到更加高维的空间，这时任何元素都可以成为分割元素。

1.1 拓扑与几何

在 CGAL 的时间中分割了拓扑和几何的数据结构。这个思想是设计几何软件的关键。这使得我们可以独立地考虑拓扑算法和几何算法的设计。在 CGAL 中，开发者广泛采用模板来达成。

考虑下面的例子：

template <typename GeometryTraits, typename Dcel>
class Arrangement_2 { ... };

这个模板形式表明，在构建 Arrangement 对象的时候，我们需要在 GeometryTraits 类型参数的位置上提供定义了几何对象类型及相关的 Traits（参见 The Geometry Traits）；Dcel 表示 Doubly-connected edge list 数据结构，这个数据结构是用于拓扑数据的存储，其包含了 Vertice, Edge, Face 等相关类型，以及对这些类型数据的操作方法 (参见 Representation of Arrangements: The Dcel)。

Arrangement_2 的父类是：

template <typename GeometryTraits, typename TopologyTraits>
class Arrangement_on_surface_2 { ... };

该类的一个实例表示三维空间中的一个二维面的 Arrangement。

1.2 Well-behaved Curves

2D Arrangment 中，并非任意曲线都可以参与划分的形成，这一问题在 The Geometry Traits 中有比较详细的讨论。但是基于实现层面的计算复杂度的考虑，我们通常对于输入曲线的形式有更强的假设，这些假设包括：

1. 曲线是非自交的；
2. 每个曲线之间具有有限个交点；

2 Basic Arrangments

这一个章节是对 Arrangments 使用的入门。

2.1 Representation of Arrangements: The Dcel

给定二维平面中的一个曲线几何 C，arrangement A(C) 表示将平面划分成，0 维、1 维 和 2 维元素，分别称为顶点 (Vertices)，边 (Edges) 和面 (Faces)。集合 C 中的边可能是彼此相交的，这些变也不一定符合 x-单调 (x-monotone) 。我们从 C 构造一个集合 C′′，集合 C′′ 中的元素都是 x-monotone 的曲线，且这些曲线彼此的内部不相交（注意这个过程中会对原有单个曲线进行拆解）。注意 x-monotone 的曲线是一定不自交的。C 中也可能包含孤立的点。这样，C′′ 可以构建为平面图。最终 A(C) 和 A(C′′) 觉有同样的面结构，但是后者可能有更多的顶点和边。

A(C′′) 的图结构可以用 DCEL 表示。这个数据结构结构中存储了点、边、面，以及这些元素之间的连接关系。这个数据结构是 Halfedge data structure 数据结构族的一员。

在 DCEL 数据结构中，每个边由一对有向的 Halfedge 表示，这些两个 halfedge 为彼此的孪生 (twin)，方向相反。每个有向的 halfedge 具有一个 source vertex 和一个 target vertex。Halfedge 用于连接顶点，并分隔面。如果一个顶点 v 是一个 halfedge e 的 target，则称 v and e are incident to each other。对于一个顶点，连接到这个顶点上的边以逆时针的顺序给出。孤立的点没有临边。

每个 Halfedge 会存储其相邻的面，这个面位于其左侧。Halfedge 的临边中会有一条边与其具有相同的临面。沿着这个关系从一个边遍历 DCEL 图，最终会回到自身并构成一个闭环，这个闭环被称为一个 connected component of the boundary (CCB)。

CCB 会在平面中构成一个面，此 CCB 被称为这个面的 outer_ccb。我们只考虑如下的情况

1. 每个边都是有限的（Bounded），那么每个 Arrangment 中至多只有一个 unbounded face；
2. Arrangement 固定在一个平面内部，这样每个面最后只有一个 outer CCB；

Unbounded 面没有 outer ccb。面内部的 ccb 构成一个孔，以顺时针绕行的方式给出 inner ccb。注意 inner ccb 不一定形成一个面， 他可能是一个线。一个 inner ccb 也可能包含多面。在实际处理中，内部孤立点不视为孔。

2.2 Arrangement 类模板

2D Arrangement 包的主要组件是 Arrangement_2<Traits, Decl> 类模板；该模板提供了创建，遍历以及维护 Arrangement 数据结构的接口。

2D Arrangement 包的设计主要有以下两个原则：

• 分离 Arrangement 的表示和内部几何算法的实现；
• 分离拓扑和和几何；

后一个元素体现在类模板的两个类型参数上。

• Traits 模板参数应该输入一个 ArrangementBasicTraits_2 概念的模型，这个模型中包含了 x-monotone 范式的线以及二维点，分别是 ArrangementBasicTraits_2::X_monotone_curve_2 以及 ArrangmentBasicTraits_2::Point_2。
• DCEL 模板参数应该输入一个 ArrangmentDcel 概念的模型；其默认参数是 Arr_default_dcel<Traits>，一般就够用了。

看下面的一个基础例子：

#include <CGAL/Cartesian.h>
#include <CGAL/Arr_non_caching_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>
typedef int                                             Number_type;
typedef CGAL::Cartesian<Number_type>                    Kernel;
typedef CGAL::Arr_non_caching_segment_traits_2<Kernel>  Traits;
typedef Traits_2::Point_2                               Point;
typedef Traits_2::X_monotone_curve_2                    Segment;
typedef CGAL::Arrangement_2<Traits_2>                   Arrangement;
int main() {
  Arrangement arr;
  Point p1(1, 1), p2(1, 2), p3(2, 1);
  Segment cv[] = {Segment(p1, p2), Segment(p2, p3), Segment(p3, p1)};
  CGAL::insert(arr, &cv[0], &cv[sizeof(cv)/sizeof(Segment)]);
  return 0;
}