差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
| 直骨架的研究:introduction:organization [2025/09/25 10:25] – 创建 张叶安 | 直骨架的研究:introduction:organization [2025/09/25 10:39] (当前版本) – 张叶安 | ||
|---|---|---|---|
| 行 9: | 行 9: | ||
| This insight motivates a novel straight-skeleton algorithm for simple non-degenerate5 polygons that is based on the motorcycle graph in Section 2.3. In order to extend this approach to arbitrary planar straight-line graphs, we carefully generalize the motorcycle graph in Section 2.4. Further, we prove two essential geometric properties for this generalization that are important for our algorithmic approach: (i) the input graph and the motorcycle graph tessellate the plane into convex faces and (ii) the generalized motorcycle graph covers the reflex arcs of the straight skeleton. | This insight motivates a novel straight-skeleton algorithm for simple non-degenerate5 polygons that is based on the motorcycle graph in Section 2.3. In order to extend this approach to arbitrary planar straight-line graphs, we carefully generalize the motorcycle graph in Section 2.4. Further, we prove two essential geometric properties for this generalization that are important for our algorithmic approach: (i) the input graph and the motorcycle graph tessellate the plane into convex faces and (ii) the generalized motorcycle graph covers the reflex arcs of the straight skeleton. | ||
| - | 这一观察促使我们提出了一种新的针对简单非退化5多边形的直骨架算法，该算法基于第2.3节中的摩托车图。为了将这种方法扩展到任意平面直线图，我们仔细地推广了第2.4节中的摩托车图。此外，我们证明了这种推广的两个重要的几何性质，这些性质对于我们的算法方法至关重要：（i）输入图和摩托车图将平面镶嵌成凸面，以及（ii）广义摩托车图覆盖了直骨架的凹弧。 | + | 这一观察促使我们提出了一种新的针对简单非退化5多边形的直骨架算法，该算法基于第2.3节中的摩托车图。为了将这种方法扩展到任意平面直线图，我们仔细地推广了第2.4节中的摩托车图。此外，我们证明了这种推广的两个重要的几何性质，这些性质对于我们的算法方法至关重要：**（i）输入图和摩托车图将平面镶嵌成凸面，以及（ii）广义摩托车图覆盖了直骨架的凹弧。** |
| In addition, the generalized motorcycle graph permits an extension of Cheng and Vigneron’s alternative characterization of straight skeletons to arbitrary planar straight-line graphs. Furthermore, | In addition, the generalized motorcycle graph permits an extension of Cheng and Vigneron’s alternative characterization of straight skeletons to arbitrary planar straight-line graphs. Furthermore, | ||
张叶安