A straight-forward approach to computing the straight skeleton is through the simulation of the propagating wavefront. While edge events can be handled in a relatively efficient way the opposite holds for split events, see Section 1.4.2.1. It turns out to be non-trivial to efficiently determine which reflex wavefront vertex crashes into which wavefront edge. Let us consider for a moment only the simultaneous movement of the reflex wavefront vertices. In order to compute the straight skeleton it is important to know which reflex wavefront vertex is cutting off the trajectory of an other reflex vertex by reaching the common crossing point of their trajectories earlier. In order to extract this sub problem of computing straight skeletons, Eppstein and Erickson [EE99] introduced the so-called motorcycle graph.

计算直线骨架的一个直接方法是通过模拟传播波前。虽然边事件可以以相对有效的方式处理，但分裂事件则相反，见第1.4.2.1节。事实证明，有效确定哪个凹波前顶点撞击哪个波前边并非易事。让我们暂时只考虑凹波前顶点的同时移动。为了计算直线骨架，重要的是要知道哪个凹波前顶点通过更早地到达它们的轨迹的共同交叉点来切断另一个凹顶点的轨迹。为了提取计算直线骨架的这个子问题，Eppstein和Erickson [EE99] 引入了所谓的摩托车图。

A motorcycle is a point moving with constant speed on a straight line. Let us consider $n$ motorcycles $m1, . . . , mn$, where each motorcycle $mi$ has its own constant velocity $v_i ∈ R_2$ and a start point $p_i ∈ R_2$ , with 1 ≤ i ≤ n. The trajectory ${pi + t · v_i : t ≥ 0}$ is called the track of $mi$. While a motorcycle moves it leaves a trace behind. When a motorcycle reaches the trace of another motorcycle then it stops driving — it crashes —, but its trace remains.

摩托车是在直线上匀速移动的点。 让我们考虑 $n$ 辆摩托车 $m_1， . . . ， m_n$，其中每辆摩托车 $m_i$ 都有自己的恒定速度 $v_i ∈ R_2$ 和起点 $p_i ∈ R_2$，用 1 ≤ i ≤ n。 轨迹 ${p_i + t · v_i ： t ≥ 0}$ 称为 $m_i$ 的轨迹 。 摩托车行驶时，会留下痕迹 。 当一辆摩托车到达另一辆摩托车的踪迹时，它就会停止行驶——它撞车—— 但它的痕迹仍然存在。

Note that it is possible that motorcycles never crash. Following the terminology of Eppstein and Erickson [EE99] such motorcycles are said to have escaped. It is easy to see that there can be up to (n^2) intersections among the motorcycle tracks. However, no two motorcycle traces intersect in both interiors, which leads to at most $n$ intersections among the traces.

请注意，摩托车可能永远不会发生碰撞。按照 Eppstein 和 Erickson [EE99] 的术语，这样的摩托车被称为已经逃逸。很容易看出，摩托车轨迹之间最多可能有 (n^2) 个交点。然而，没有两条摩托车轨迹在两个内部相交，这导致轨迹之间最多有 $n$ 个交点。

Definition 1.8 (motorcycle graph). The motorcycle graph M(m1, . . . , mn) of the motorcycles $m1, . . . , mn$ is defined by the arrangement of the motorcycles traces.

定义 1.8 (摩托车图)[NT0]。) 摩托车 $m_1, . . . , m_n$ 的 motorcycle graph $M(m_1, . . . , m_n)$ 定义为摩托车轨迹的排列。

In Figure 5 (a) we illustrate the motorcycle graph $M(m1, . . . , m10)$ of ten motorcycles. Cheng and Vigneron [CV07] presented a straight-skeleton algorithm for simple polygons $P$, which is based on the motorcycle graph, see Section 1.4.2.4. They first define a motorcycle graph induced by a polygon. The idea is that every reflex vertex $v$ of $P$ defines a motorcycle which starts at $v$ and has the same velocity as the wavefront vertex which corresponds to $v$.

在图 5 (a) 中，我们展示了十辆摩托车的摩托车图 $M(m_1, . . . , m_10)$。Cheng 和 Vigneron [CV07] 提出了一个针对简单多边形 $P$ 的直线骨架算法，该算法基于摩托车图，参见第 1.4.2.4 节。他们首先定义了一个由多边形诱导的摩托车图。其思想是，P 的每个凹顶点 $v$ 定义了一辆摩托车，该摩托车从 $v$ 开始，并具有与对应于 $v$ 的波前顶点相同的速度。

non-degeneracy assumption Cheng and Vigneron [CV07] explicitly exclude the case that vertex events appear for the wavefront of $P$. The authors call this the non-degeneracy assumption. Eppstein and Erickson [EE99] remarked that perturbation techniques cannot be applied to transform these “degeneracies” to general cases. A small perturbation would change the straight skeleton drastically, see Section 2.5.3. On the other hand, such situations are very likely to occur, in particular if $P$ contains collinear edges. Figure 1 shows a typical example. (We will be present a generalization of the motorcycle graph to arbitrary planar straight-line graphs in Section 2.5.) For the matter of simplicity we refer by the nondegeneracy assumption to the slightly more general assumption that no two motorcycles crash simultaneously into each other.14

非退化假设 Cheng和Vigneron [CV07] 明确排除了顶点事件出现在$P$的波前的情况。作者称之为非退化假设。Eppstein和Erickson [EE99] 评论说，扰动技术不能应用于将这些“退化”转换为一般情况。一个小的扰动会极大地改变直线骨架，见第2.5.3节。另一方面，这种情况很可能发生，特别是当$P$包含共线边时。图1 显示了一个典型的例子。（我们将在第2.5节中介绍摩托车图到任意平面直线图的推广。）为了简单起见，我们通过非退化假设来指代稍微更一般的假设，即没有两辆摩托车同时相互碰撞。

Figure 5: Left: The motorcycle graph $M(m1, . . . , m10)$ of ten motorcycles. The velocities are represented by red arrows. Right: The motorcycle graph M(P), shown in red, induced by a simple polygon $P$ (bold). Each reflex vertex of $P$ emanates a motorcycle.

图 5： 左图：十辆摩托车的摩托车图 M（m1， . . . ， m10）。 速度由红色箭头表示。右：摩托车图 M（P）， 以红色显示，由简单多边形 P（粗体）诱导。P 的每个反射顶点发出一辆摩托车。

In order to guarantee the correctness of the algorithm of Cheng and Vigneron [CV07], it is necessary to assume that the motorcycles run out of fuel when they reach an edge of $P$. We cover this circumstance by introducing the alternative concept of walls. We assume that the plane contains straight-line segments which model rigid walls. If a motorcycle reaches a wall then it crashes and its trace remains. Following our terminology, we define a motorcycle graph induced by a polygon by specifying the motorcycles and the walls.

为了保证Cheng和Vigneron算法[CV07]的正确性，有必要假设摩托车到达$P$的边缘时耗尽燃料。我们通过引入墙壁的替代概念来涵盖这种情况。我们假设该平面包含模拟刚性墙壁的直线段。如果摩托车到达墙壁，则会坠毁并留下痕迹。按照我们的术语，我们通过指定摩托车和墙壁来定义由多边形引起的摩托车图。

Definition 1.9 (motorcycle graph induced by a simple polygon).

Let $P$ denote a simple nondegenerate polygon. Each reflex vertex $v$ emanates a motorcycle with the start point $v4 and the same velocity as the corresponding wavefront vertex of $v$. Further, we consider the edges of $P$ as walls. We denote by M(P) the resulting motorcycle graph and call M(P) the motorcycle graph induced by $P4.

定义 1.9 (由简单多边形诱导的摩托车图)[NT0]。设 $P$ 表示一个简单的非退化多边形。每个凹顶点 $v$ 发出一个摩托车，其起始点为 v，速度与 $v$ 对应的波前顶点相同。此外，我们将 $P$ 的边视为墙壁。我们将得到的摩托车图表示为 M(P)，并称 M(P) 为由 P 诱导的摩托车图。

Definition 1.10 (arm of a motorcycle).Let $m$ denote a motorcycle of M(P) that emanates from the vertex $v$. We call the two wavefront edges that are incident to the reflex wavefront vertex emanated from $v$, the arms of $m$. The one arm that is left of the track of $m$ is called left arm of $m$ and the other arm is called right arm of $m$.

定义 1.10（摩托车的臂）[NT0]。设 $m$ 表示从顶点 $v$ 发出的 M(P) 的一辆摩托车。我们将与从 $v$ 发出的凹波前顶点相连的两个波前边，称为 $m$ 的臂。位于 $m$ 轨迹左侧的臂称为 $m$ 的左臂，另一个臂称为 $m$ 的右臂。

We illustrate the motorcycle graph M(P) of a sample polygon $P$ in Figure 5 (b). Cheng and Vigneron [CV07] also presented an extension of their algorithm to polygons with holes.

我们在图5（b）中展示了一个示例多边形$P$的摩托车图M(P)。Cheng和Vigneron[CV07]也提出了他们算法到带孔多边形的扩展。

The motorcycle graph has to be extended accordingly: One has to introduce additional motorcycles at the convex vertices of the holes — which emanate reflex wavefront vertices within $P$ — and one has to add the edges of the holes as walls, too.

摩托车图必须进行相应的扩展：必须在孔的凸顶点处引入额外的摩托车——这些顶点会发出$P$内的反射波前顶点——并且还必须将孔的边缘添加为墙壁。