差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
| 直骨架的研究:computing_the_straight_skeleton [2025/09/25 15:08] – 张叶安 | 直骨架的研究:computing_the_straight_skeleton [2025/09/25 16:53] (当前版本) – 张叶安 | ||
|---|---|---|---|
| 行 26: | 行 26: | ||
| [HH11c]S. Huber 和 M. Held。平面直线图直线骨架的理论和实践结果。论文集第 27 年。ACM 研讨会。计算。Geom.，法国巴黎，将于 2011 年出版 | [HH11c]S. Huber 和 M. Held。平面直线图直线骨架的理论和实践结果。论文集第 27 年。ACM 研讨会。计算。Geom.，法国巴黎，将于 2011 年出版 | ||
| + | |||
| + | This suggests that we can obtain an algorithm for computing straight skeletons by by employing the motorcycle graph during the wavefront propagation process. In contrast to the former sections we do not consider a triangulation but maintain the intersection points of M with the wave front and call them Steiner vertices. The following types of events occur, see Fig. 5: (i) edge event: two neighboring convex vertices in a convex part of P meet; (ii) split event: a reflex vertex meets its corresponding Steiner vertex; (iii) switch event: a convex vertex meets a Steiner event and hence the convex vertex migrates to a different convex part of P ; (iv) start event: a reflex vertex or a (moving) Steiner vertex meets a (resting) Steiner vertex, which is the endpoint of a different trace and has to start moving. Note that only neighboring2 vertices meet in the propagation process since the motorcycle graph decomposes the shrinking polygon P at any time into convex parts. | ||
| + | |||
| + | 这表明我们可以通过在波前传播过程中使用摩托车图来获得计算直线骨架的算法。与前面的章节相反，我们不考虑三角剖分，而是保持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, | ||
| + | |||
| + | |||
张叶安