Aichholzer et al. [AAAG95] introduced the straight skeleton of simple polygons $P$ by considering a so-called wavefront-propagation process. Each edge $e$ of $P$ sends out a wavefront which moves inwards at unit speed and is parallel to $e$. The wavefront of $P$ can be thought to shrink in a self-parallel manner such that sharp corners at reflex6 vertices of $P$ remain sharp, see Figure 1. During this propagation process topological changes, so-called events, will occur: Edges collapse to zero length and the wavefront may be split into multiple parts. Each wavefront vertex moves along the bisector of two edges of $P$ and, while it moves, it traces out a straight-line segment.

Aichholzer 等人 [AAAG95] 通过考虑所谓的波前传播过程，引入了简单多边形 $P$ 的直线骨架。$P$ 的每条边 $e$ 发出一个波前，该波前以单位速度向内移动，并且平行于 $e$。$P$ 的波前可以被认为是以自平行的方式收缩，使得 $P$ 的凹顶点的尖角保持尖锐，参见图 1。在这个传播过程中，会发生拓扑变化，即所谓的事件：边塌缩到零长度，并且波前可能分裂成多个部分。每个波前顶点沿着 $P$ 的两条边的角平分线移动，并且在移动时，它会描绘出一条直线段。

Definition 1.1 (straight skeleton, arcs, nodes, faces) The straight skeleton S (P) of the polygon $P$ comprises the straight-line segments that are traced out by the wavefront vertices.These straight-line segments and are called the arcs of S (P). The loci of the topological changes of the wavefront are called nodes. To each edge $e$ of $P$ belongs a face f (e), which consists of all points that are swept by the wavefront edge that is sent out by $e$.

定义 1.1（直骨架，弧，节点，面）[NT0]。多边形 $P$ 的直骨架 S (P) 包含由波前顶点描绘出的直线段。这些直线段被称为S(P)的弧。波前拓扑变化的轨迹被称为节点。对于$P$的每条边$e$，都对应一个面f(e)，它由波前边缘扫过的所有点组成，该波前边缘由$e$发出。

We illustrate the straight skeleton $S (P)$ of a simple polygon $P$ in Figure 1. Each node is incident to multiple arcs. The boundary of a face consists of arcs and the vertices of a face are nodes.

我们在图1中展示了一个简单多边形$P$的直骨架$S (P)$。每个节点都与多个弧相关联。一个面的边界由弧组成，一个面的顶点是节点。

Lemma 1.2 ([AAAG95]). The straight skeleton S (P) of a simple polygon $P$ with $n$ vertices is a tree. It consists n − 2 nodes and 2n − 3 arcs and tessellates $P$ into $n$ faces.

引理 1.2 ([AAAG95])[NT1]。简单多边形P的直线骨架S(P)是一棵树。它由n − 2个节点和2n − 3条弧组成，并将P细分为n个面。

For the proof of this lemma we create a single node for each topological change, even if the resulting nodes coincide geometrically. In particular, we assume that each node has degree three.7 For example, if $P$ is a regular n-gon then S (P) has a star form, i. e. all arcs meet in the center point of $P$ and multiple nodes with degree three are geometrically coincident.

为了证明这个引理，我们为每个拓扑变化创建一个单独的节点，即使生成的节点在几何上重合。特别地，我们假设每个节点的度数为三。7 例如，如果 $P$ 是一个正n边形，那么 S (P) 具有星形形式，即所有弧都相交于 P 的中心点，并且多个度数为三的节点在几何上重合。

Proof. The number of faces is n, since $P$ comprises $n$ edges. Next, we note that the face f (e) of an edge $e$ is connected because it is given by the set of points which are swept by a continuously moving wavefront edge. On the other hand, each point within $P$ is reached by the wavefront after some time. Hence, $P$ is tessellated by the faces of S (P) and S (P) consists of the boundaries of the faces. From that it follows that S (P) does not contain a cycle and is therefore a tree. The inner nodes of this tree are of degree 3 and the tree has $n$ leaves. It follows that S (P) has n − 2 nodes and 2n − 3 arcs.

证明。面的数量为n，因为$P$包含$n$条边。接下来，我们注意到边$e$的面f (e)是连通的，因为它是由连续移动的波前边扫过的点集给出的。另一方面，P内的每个点在一段时间后都会被波前到达。因此，$P$被S (P)的面镶嵌，并且S (P)由这些面的边界组成。由此可知，S (P)不包含环，因此是一棵树。这棵树的内部节点度数为3，并且这棵树有n个叶子。由此得出，S (P)有n − 2个节点和2n − 3条弧。

Definition 1.3 (reflex/convex wavefront vertex). A wavefront vertex v is reflex if the angle on the side where $v$ propagates to is at least 180◦. Likewise, we define a convex wavefront vertex.

定义 1.3（反射/凸波前顶点）[NT0]。如果 v 传播侧的角度至少为 180[NT3]◦，则波前顶点 v 是反射的。同样，我们定义一个凸波前顶点。

Let us discuss the different types of topological events that occur for the wavefront in more detail. We follow Aichholzer et al. [AAAG95], who distinguish two types of events, namely edge events and split events.

让我们更详细地讨论波前发生的各种类型的拓扑事件。我们遵循 Aichholzer 等人 [AAAG95] 的方法，他们区分了两种类型的事件，即边事件和分裂事件。

1. Edge event: An edge event occurs when two neighboring convex vertices $u$ and $v$ of the wavefront meet. This event causes the wavefront edge $e$, which connects $u$ and $v$, to collapse to zero length. The wavefront edge

$e$ is removed and the vertices $u$ and $v$ are merged into a new convex vertex with its own velocity, see Figure 2 (a).

1. 边事件：当波前的两个相邻凸顶点 $u$ 和 $v$ 相遇时，会发生边事件。此事件导致连接 $u$ 和 $v$ 的波前边 $e$ 塌陷为零长度。波前边 $e$ 被移除，顶点 $u$ 和 $v$ 合并为一个具有自身速度的新凸顶点，参见图 2 (a)。
2. Split event: A split event occurs when a reflex vertex $u$ of the wavefront meets an edge $e$ of the wavefront. The vertex $u$ splits the entire wavefront into polygonal parts. Each part keeps on propagating for its own, see Figure 2 (b).
3. 分裂事件：当波前的一个反射顶点 $u$ 遇到波前的一条边 $e$ 时，会发生分裂事件。顶点 $u$ 将整个波前分裂成多边形部分。每个部分各自继续传播，参见图 2 (b)。

Split events can occur in interesting variations. In Figure 2 ©, a split event for the reflex vertex $u$ and the edge $e$ occurs, while at the same time the edge between $u$ and $v$ collapses to zero length. Note that in this case only one wavefront part remains after the split event. However, the question arises whether we would like to call this event an edge event as well. For subfigure (a) we observe that a local disk around the

分裂事件可能以有趣的变体形式发生。在图2©中，发生了反射顶点$u$和边$e$的分裂事件，同时$u$和$v$之间的边塌缩为零长度。请注意，在这种情况下，分裂事件后仅保留一个波前部分。然而，问题出现了，我们是否也想将此事件称为边事件。对于子图(a)，我们观察到围绕着一个局部圆盘

Figure 1: The straight skeleton S(P) (blue) of a simple polygon $P$ (bold) is defined by a wavefront propagation process where the edges of $P$ move inwards in a self-parallel manner. Five wavefronts at equally spaced points in time are shown in gray. The blue straight-line segments are called the arcs of S(P) and the common endpoints of arcs are called the nodes of S(P). We shade the face f (e) of one edge $e$ in light gray.

图 1：简单多边形 $P$（粗体）的直骨架 S(P)（蓝色）由波前传播过程定义，其中 $P$ 的边以自平行的方式向内移动。以等间隔的时间点显示的五个波前以灰色显示。蓝色的直线段称为 S(P) 的弧，弧的公共端点称为 S(P) 的节点。我们用浅灰色阴影表示一条边 $e$ 的面 f (e)。

Figure 2: Two types of events occur during the wavefront propagation: edge and split events. (a) illustrates an edge event, (b) a simple split event, © a split event with an edge collapse combined, (d) a split event with two reflex vertices $u1$ and $u2$ involved. The arcs are depicted in blue and the wavefronts in gray.

图 2：波前传播过程中发生两种类型的事件：边缘事件和分裂事件。(a) 说明了一个边缘事件，(b) 一个简单的分裂事件，© 一个边缘塌陷结合的分裂事件，(d) 一个涉及两个反射顶点 $u1$ 和 $u2$ 的分裂事件。弧线用蓝色描绘，波前用灰色描绘。

point $p$, where the event happened, is tessellated into convex slices by the arcs of the straight skeleton. It is easy to see that this holds in general if $u$ and $v$ are convex. On the other hand, in subfigures (b) and ©, a tessellation of a local disk around $p$ also contains a reflex slice. We would like to use this property as an indicator that a split event happened at $p$. For this reason, we call the event illustrated by subfigure © a split event.8 As a consequence, edge events describe edge collapses between two convex vertices. Furthermore, if the straight-skeleton face of an edge — interpreted as a polygon — contains a reflex vertex, it has been generated by a split event.

事件发生的点$p$被直线骨架的弧线分割成凸切片。容易看出，如果$u$和$v$是凸的，则通常情况下这都成立。另一方面，在子图(b)和©中，围绕$p$的局部圆盘的镶嵌也包含一个凹切片。我们希望使用此属性作为在$p$处发生分割事件的指标。因此，我们将子图©所示的事件称为分割事件。因此，边事件描述了两个凸顶点之间的边塌陷。此外，如果一条边的直线骨架面（解释为多边形）包含一个凹顶点，则它是由分割事件生成的。

In subfigures (b) and © only one reflex vertex $u$ was involved in the split event. However, it could happen that two or more reflex wavefront vertices u1, . . . , uk meet each other in a common point $p$ at the same time, see Figure 2 (d). Such situations occur easily for rectilinear9 polygons. As a consequence the wavefront is split into $k$ parts. Note that it is possible that a new reflex vertex emerges, as illustrated in Figure 2 (d). We will call events, where two or more reflex vertices meet simultaneously in a point a multi split event. Multi split events that cause a new reflex vertex to emerge are called vertex events.10

在子图（b）和（c）中，只有一个凹顶点$u$参与了分裂事件。然而，可能会发生两个或多个凹波前顶点u1, . . . , uk在同一点$p$ 同时相遇的情况，参见图2（d）。对于直线9多边形，这种情况很容易发生。因此，波前被分成$k$部分。请注意，可能会出现一个新的凹顶点，如图2（d）所示。我们将两个或多个凹顶点同时在一个点相遇的事件称为多重分裂事件。导致新的凹顶点出现的多重分裂事件称为顶点事件。

We want to remark that the taxonomy of the different classes of events is in flux within the literature of straight skeletons. For example, Tanaseˇ [TA09] pursues a different approach by considering three sub-classes of edge events and three sub-classes of split events. Following this taxonomy, the situation in Figure 2 © would be called reflex edge annihilation.

我们想指出的是，在直线骨架的文献中，不同事件类别的分类正在不断变化。例如，Tanaseˇ [TA09] 采用了一种不同的方法，考虑了边缘事件的三个子类和分裂事件的三个子类。按照这种分类，图 2 © 中的情况将被称作凹边湮灭。

Using the taxonomy we presented above, the propagation of a wavefront always proceeds as follows: Every edge event reduces the number of wavefront edges by one. A split event splits the wavefront into polygonal parts and implies a hierarchy of nested polygons. Further, a split event reduces the number of reflex vertices at least by one. Even if a vertex event happens, at least two reflex vertices must have been involved in this event. Eventually, all nested parts in the hierarchy become convex polygons. The convex polygons are reduced by a series of edge events. Finally, a polygon vanishes by collapsing either to a point or to a straight-line segment. As an example for the first case one could imagine $P$ to be a triangle, and for the second case a non-equilateral rectangle.

使用我们上面提出的分类法，波前的传播总是按照以下方式进行：每个边事件都会使波前边的数量减少一个。分裂事件将波前分裂成多边形部分，并暗示着一个嵌套多边形的层级结构。此外，分裂事件至少会使凹顶点（reflex vertices）的数量减少一个。即使发生顶点事件，至少有两个凹顶点必须参与到此事件中。最终，层级结构中的所有嵌套部分都变成凸多边形。凸多边形通过一系列边事件被简化。最后，一个多边形通过坍缩成一个点或一条直线段而消失。作为第一种情况的例子，可以想象$P$是一个三角形，而对于第二种情况，则是一个非等边矩形。