差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
| 直骨架的研究:computing_the_straight_skeleton [2025/09/25 15:15] – 张叶安 | 直骨架的研究:computing_the_straight_skeleton [2025/09/25 16:53] (当前版本) – 张叶安 | ||
|---|---|---|---|
| 行 30: | 行 30: | ||
| 这表明我们可以通过在波前传播过程中使用摩托车图来获得计算直线骨架的算法。与前面的章节相反，我们不考虑三角剖分，而是保持M与波前的交点，并称它们为斯坦纳顶点。以下类型的事件会发生，参见图5：（i）边事件：P的凸部分的两个相邻凸顶点相遇；（ii）分裂事件：一个凹顶点与其对应的斯坦纳顶点相遇；（iii）切换事件：一个凸顶点遇到一个斯坦纳事件，因此该凸顶点迁移到P的不同凸部分；（iv）启动事件：一个凹顶点或一个（移动的）斯坦纳顶点遇到一个（静止的）斯坦纳顶点，该顶点是不同轨迹的端点，必须开始移动。请注意，只有相邻的2个顶点在传播过程中相遇，因为摩托车图在任何时候都会将收缩的多边形P分解为凸部分。 | 这表明我们可以通过在波前传播过程中使用摩托车图来获得计算直线骨架的算法。与前面的章节相反，我们不考虑三角剖分，而是保持M与波前的交点，并称它们为斯坦纳顶点。以下类型的事件会发生，参见图5：（i）边事件：P的凸部分的两个相邻凸顶点相遇；（ii）分裂事件：一个凹顶点与其对应的斯坦纳顶点相遇；（iii）切换事件：一个凸顶点遇到一个斯坦纳事件，因此该凸顶点迁移到P的不同凸部分；（iv）启动事件：一个凹顶点或一个（移动的）斯坦纳顶点遇到一个（静止的）斯坦纳顶点，该顶点是不同轨迹的端点，必须开始移动。请注意，只有相邻的2个顶点在传播过程中相遇，因为摩托车图在任何时候都会将收缩的多边形P分解为凸部分。 | ||
| + | |||
| + | This is easy to see since reflex angles at reflex vertices of W(G, t) are split by (parts of) motorcycle traces accordingly. In particular, for t = 0, the lemma implies that G + M(G) induces a tessellation of the plane into (possibly unbounded) convex faces. A consequence of the lemma is that during the propagation of W∗(G, t) only adjacent vertices can meet. | ||
| + | |||
| + | 这很容易理解，因为W(G, | ||
| + | G + M(G)将平面划分为（可能无界的）凸面。该引理的一个结果是，在W∗(G, | ||
| + | |||
| + | |||
张叶安