CGAL 5.2 - 2D Straight Skeleton and Polygon Offsetting 学习与翻译

本文基于CGAL 5.2 - 2D Straight Skeleton and Polygon Offsetting进行翻译和学习

文章目录

二、 代表（Representation）

一、定义

1.1二维轮廓(2D Contour)

二维轮廓是一个封闭的序列(一个圈)，由3条或更多连通的二维有向直线段组成，称为轮廓边缘。轮廓边缘的端点称为顶点（vertices）。每个轮廓边与至少两个其他轮廓边共享其端点。

若这些边只在顶点相交，而且最多沿一条直线重合，但不相交，则该轮廓线称为简单（simple）。

轮廓拓扑等价于一个磁盘（disk）,如果是简单的（simple）,则可以说是一个约旦曲线（Jordan Curve.）。

轮廓将平面分成两个区域:一个有界和无界。如果轮廓的有界区域仅仅是一个单连通集（singly-connected），则该轮廓称为严格简单轮廓（strictly-simple）。

轮廓线的方向是由其边界区域周围的顶点的顺序给出的。它可以是顺时针(CW)或逆时针(CCW)。

轮廓边缘的有界边是面向轮廓的有界区域的边。如果轮廓是面向CCW的，则边缘有界的一侧是其左侧。

具有零边(由两个连续重合顶点给出的长度为零的段)或边缘不连接有界区域(天线（an antenna）:两条连续的边沿着同一条线来回移动)的轮廓称为退化（degenerate）(共线边不被认为是退化)。
（简单来说：退化：边长度=0，或者轮廓线有断开）

1.2二维带孔多边形（2D Polygon with Holes）

二维多边形是一个轮廓线。

一个有孔的二维多边形是一个外圈是轮廓线，称为外轮廓，在其有界区域内有零个或多个轮廓线，称为内轮廓或孔。

具有孔洞的多边形，如果其内部是单连通集合，则是严格简单的。

带孔多边形的方向为其外轮廓的方向。任何边缘的有界边，无论是外轮廓还是孔，对所有边缘都是相同的。也就是说，如果外轮廓面向CCW，孔为CW，轮廓和孔边缘都面向多边形内部的左边。

在本章剩下的部分中，术语多边形（polygon）将指代带有孔的多边形（polygon with holes）。

图20.1严格简单多边形的例子:一个没有孔且两条边重合(左)，一个有两个孔(右)。

图20.2非简单多边形的例子:一种是可折叠的，即非平面的(左);一种是顶点接触边缘的(中);一种是有孔向外交叉的(右)

本文讨论的是严格简单多边形

1.3非退化并严格简单孔洞多边形的向内偏移（ Inward Offset of a Non-degenerate Strictly-Simple Polygon with Holes）

对于任意非退化的具有孔的二维严格简单多边形(称为源)，在欧几里得距离t >0处，可以存在0、1或更多的带有孔的向偏移多边形（inward offset polygons with holes），或简称为偏移多边形（offset polygons）(每个都是严格简单且非退化的多边形)。该偏移多边形的任意轮廓边，称为偏移边（offset edge ），对应于源多边形的某些轮廓边，称为源边。偏移边平行于它的源边并具有相同的方向。支持偏移边的线与其源边之间的欧氏距离正好是t。

偏移边总是位于它的源边(一个有方向的直线段)的有界一侧。

偏移多边形可以有较少、相等或更多的边作为其源多边形。

如果源多边形没有孔，则偏移多边形没有孔。如果源多边形有孔洞，那么任何偏移多边形本身都可以有孔洞，但它也可以完全没有孔洞(如果距离足够大的话)。

每个偏移多边形具有与源多边形相同的方向。

1.4二维非退化严格简单孔洞多边形的直线骨架（Straight Skeleton of a 2D Non-degenerate Strictly-Simple Polygon with Holes）

非退化严格简单带孔多边形的二维直线骨架是多边形内部的一种特殊划分，它对应于轮廓边缘连续向内偏移所描出的单调区域。每个区域正好对应1条轮廓边缘。

这些区域是由轮廓边缘的支撑线的角等分线所限定的，每个这样的区域本身是一个非凸非退化的严格简单多边形。

其他例子:一个顶点事件(左)，几个共线边(中)的情况，以及一个具有切线边的简单多边形(右)的情况。

1.5角平分线和偏置平分线（Angular Bisecting Lines and Offset Bisectors）

（这块没大看懂）

给定两个点和一条通过这两点的直线，通过中点的垂线就是这两个点的平分线(或平分线)（bisecting line (or bisector) ）。

两条相交于一点的非平行线，被穿过该点的另外两条线平分。（啥意思？）

两条平行线被中间的另一条平行线平分。

只要给出一条直线，任何垂线都可以被认为是平分线(沿这条直线任意两点的平分线)。

两条边的平分线是将两条边的支撑线平分的线(如果两条边平行或共线，则只有一条平分线。（支撑线？）

与支撑轮廓边缘的线有界一侧的半平面称为轮廓边缘偏移区（ offset zone ）。

给定任意数量的轮廓边缘(不一定是连续的)，它们的偏移区相交称为它们的组合偏移区（combined offset zone.）。

任意两条轮廓边缘定义一个偏移等分线，如果两条边缘不平行，则它们的等分线可分解为源自支撑线交点的4条射线。这些光线中只有一条包含在边缘的组合偏移区中(这取决于可能的方向组合)。这条射线是非平行轮廓边缘的偏置平分线。

如果两条边平行(但不共线)且方向相反，则整个且唯一的等分线是它们的偏移等分线。如果两边平行但方向相同，则它们之间没有偏移等分线。

如果两条边共线且方向相同，则它们的偏置平分线由一条从两条边的组合补的中点出发的垂线给出。(一条边/线段的补数（ complement ）是沿其支撑线的两条非线段的射线，N条共线线段的组合补数是每条线段的补数的交点)。如果两边共线但方向相反，则它们之间没有偏移等分线。

1.6 面，边和顶点（Faces, Edges and Vertices）

由直线骨架划分的每个区域称为面。每个面都由称为边的直线段限定。每个面恰好有一条边是轮廓边(对应多边形的一条边)，其余位于多边形内部的边称为骨架边（ skeleton edges），或等分线（bisectors）。

直线骨架的等分线是先前定义的偏移等分线的部分。由于偏移等分线是由两条轮廓边组成的等分线的射线，所以每条骨架边(或等分线)都由两条轮廓边唯一给定。这些边称为等分线的定义轮廓边（defining contour edges）。

这些边的交点称为顶点（ vertices）。虽然在一个简单的多边形中，只有2条边在一个顶点相交，但在一个直线骨架中，3条或更多的边在一个给定的顶点相交。也就是说，直线骨架中的顶点具有>=3度。

一个轮廓顶点（contour vertex）是一个顶点，它的2条入射边是轮廓边。

骨架顶点（ skeleton vertex ）是其关联边都是骨架边的顶点。

轮廓等分线（ contour bisector）是定义轮廓边是连续的等分线。这样的等分线与1个轮廓顶点和1个骨架顶点相关联，并在1个端点与输入多边形相接触。

内等分线（ inner bisector）是定义轮廓边不连续的等分线。这样的等分线偶合在2个骨架顶点上，并且严格包含在多边形的内部。

二、 代表（Representation）

这个CGAL包表示一个直线骨架作为一个专门的 半边缘数据结构(HDS)，其顶点嵌入2D点(详见参考手册中的直线骨架概念)。

它的一半边缘，通过考虑源点和目标点，隐式嵌入二维定向直线段(每个看到的一半边缘不显式嵌入一个段)。

在HDS中，直线骨架的一个面被表示为一个面。轮廓和骨架边用一对相反的HDS半边来表示，轮廓顶点和骨架顶点都用HDS顶点来表示。

在HDS中，边界半边（a border halfedge）是发生在无界面上的半边。在直线骨架HDS的情况下，这样的边界半边朝向是：他们的左边面多边形外侧。因此，这样的边界边沿的对边都是:其左侧面向多边形的内部。

CGAL包要求输入多边形(带孔)是非退化的、严格简单的、逆时针方向的。

骨缘的朝向是：它们的左侧面向它们所结合的区域。也就是说，面的顶点(包括轮廓和骨架)是以逆时针顺序循环的。在任何面上都有且只有一个轮廓线半边。

（这里我理解的半边（halfedge）是指边的一侧，每条边都有两侧）

输入多边形的轮廓由HDS(面向外的)的边沿跟踪，但方向相反。也就是说，轮廓的顶点只能从直线骨架数据结构中通过循环边界半边来跟踪，得到的顶点序列将随输入顶点序列反向。

根据上一节给出的定义，骨架边由2条轮廓边定义。在该表示中，代表骨架边的每一个对边都与对应于其定义轮廓边之一的对边相关联。因此，骨架边上的两个相反的半边（halfedge）连接着定义它的两条轮廓边。

从任何边界轮廓线的半边开始，循环存储边界轮廓线的半边的结构，从而来跟踪多边形轮廓的顶点(以相反的顺序)。

从除边界边外的任一轮廓边开始，绕着轮廓边相应的面逆时针移动结构。面周围的顶点总是描述一个非凸非退化的严格简单多边形。

顶点是轮廓线和/或骨架边的交点。因为一条骨架边是由两条轮廓边定义的，所以任何顶点本身都是由一组独特的轮廓边定义的。这些被称为顶点的定义轮廓边（defining contour edges of the vertex.）。

顶点是由它的一组定义轮廓边缘来识别的。如果两个顶点具有不同的定义轮廓边缘集，则它们是不同的。注意，顶点可以是不同的，即使它们在几何上嵌入在同一点上。

顶点的度数（degree ）是顶点周围入射(指向)顶点的半边数。与任何半边数据结构一样，在一个顶点周围，每个传入(事件)半边都有一个传出的半边。顶点的度数只计算传入(事件)的一半。

在直线骨架中，顶点的度不仅是顶点周围入射的半边的数目，而且是定义轮廓边半边的数目。顶点本身就是所有轮廓边同时碰撞的点。

轮廓顶点有两个明确的轮廓半边，即与顶点相关联的轮廓边，它有3个半边事件。有且只有一个半边是直线骨架。轮廓顶点的度数正好是3。

骨架顶点至少有3个定义轮廓边半边和3个关联骨架半边。如果超过3条边同时在同一点和时间碰撞(就像任何有超过3条边的正多边形)，相应的骨架顶点将有超过3条定义轮廓边和关联骨架边。也就是说，骨架顶点的度>=3(该算法最初产生的节点度为3，但最终所有的重合节点合并成更高度数的节点)。所有在骨架顶点上的半边都是骨架半边（skeleton halfedges）。

顶点类提供的循环器（ circulators provided by the vertex class.）可以跟踪顶点周围的定义轮廓半边和入射半边。

顶点的度数没有被缓存，也不能直接从顶点获得，但是你可以通过手动计算顶点周围的入射半边的数量来计算这个数字

每个顶点存储一个2D点和一个时间（time），这是从顶点的点到支持顶点的每个定义轮廓边缘的线的欧几里得距离(对每条线的距离相同)。（角平分线定理）

除非多边形是凸的,这个距离是不相等的,在中轴的情况下,因此,框架顶点的时间(time)不对应的多边形顶点的距离(所以它不能用于获取深层区域的形状,例如)。

如果多边形为凸形，则直线骨架与该多边形的Voronoi图完全等价，每个顶点时间与定义边的等距。

轮廓顶点的时间为零。