差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 直骨架的研究 [2025/09/24 23:26] – 张叶安
+++ 直骨架的研究 [2025/10/16 11:17] (当前版本) – 张叶安
@@ 行 1: / 行 1: @@
+https://code.google.com/archive/p/straight-skeleton/source/default/source
+{{ :phdthesis及其翻译_1_.pdf |}}
+  - [[直骨架的研究:ABSTRACT]]
   - [[直骨架的研究:Introduction]]
     - [[直骨架的研究:Introduction:organization]]
     - [[直骨架的研究:Introduction:preliminaries and definitions]]
       - [[直骨架的研究:Introduction:preliminaries and definitions:The straight skeleton of a simple polygon]]
@@ 行 7: / 行 12: @@
       - [[直骨架的研究:Introduction:preliminaries and definitions:The motorcycle graph]]
     - [[直骨架的研究:Introduction:applications]]
-      - [[直骨架的研究:Introduction:applications:Mitered offset curves and NC- machining]]
+      - [[直骨架的研究:Introduction:applications:Mitered offset curves and NC-machining]]
       - [[直骨架的研究:Introduction:applications:Building roofs and generating terrains]]
       - [[直骨架的研究:Introduction:applications:Mathematical origami and the fold-and-cut problem]]
@@ 行 28: / 行 33: @@
       - [[直骨架的研究:Introduction:generalizations and related problems:Straight skeleton of polyhedra in R³]]
       - [[直骨架的研究:Introduction:generalizations and related problems:City Voronoi diagrams]]
-   - [[直骨架的研究:computing the straight skeleton]]
+  - [[直骨架的研究:computing the straight skeleton]]
     - [[直骨架的研究:computing the straight skeleton:geometric properties of the straight skeleton]]
     - [[直骨架的研究:computing the straight skeleton:the triangulation-based approach]]
@@ 行 42: / 行 47: @@
       - [[直骨架的研究:computing the straight skeleton:a generalized motorcycle graph:geometric properties of the generalized motorcycle graph]]
       - [[直骨架的研究:computing the straight skeleton:a generalized motorcycle graph:the lower envelope based on the generalized motorcycle graph]]
-    - [[直骨架的研究:computing the straight skeleton: The general wavefront-type algorithm]]
+    - [[直骨架的研究:computing the straight skeleton:The general wavefront-type algorithm]]
-      - [[直骨架的研究:computing the straight skeleton: The general wavefront-type algorithm:Details of the general algorithm]]
+      - [[直骨架的研究:computing the straight skeleton:The general wavefront-type algorithm:Details of the general algorithm]]
-      - [[直骨架的研究:computing the straight skeleton: The general wavefront-type algorithm:Runtime analysis]]
+      - [[直骨架的研究:computing the straight skeleton:The general wavefront-type algorithm:Runtime analysis]]
-      - [[直骨架的研究:computing the straight skeleton: The general wavefront-type algorithm:Details of the implementation Bone]]
+      - [[直骨架的研究:computing the straight skeleton:The general wavefront-type algorithm:Details of the implementation Bone]]
-      - [[直骨架的研究:computing the straight skeleton: The general wavefront-type algorithm:Experimental results and runtime statistics]]
+      - [[直骨架的研究:computing the straight skeleton:The general wavefront-type algorithm:Experimental results and runtime statistics]]
-    - [[直骨架的研究:computing the straight skeleton: Summary]]
+    - [[直骨架的研究:computing the straight skeleton:Summary]]
   - [[直骨架的研究:Motorcycle graphs]]
     - [[直骨架的研究:Motorcycle graphs:Prior and related work]]
-      - [[直骨架的研究:Motorcycle graphs:Prior and related work: Applications of motorcycle graphs and related problems]]
+      - [[直骨架的研究:Motorcycle graphs:Prior and related work:Applications of motorcycle graphs and related problems]]
-      - [[直骨架的研究:Motorcycle graphs:Prior and related work: Prior work]]
+      - [[直骨架的研究:Motorcycle graphs:Prior and related work:Prior work]]
-      - [[直骨架的研究:Motorcycle graphs:Prior and related work: Geometric properties of the motorcycle graph]]
+      - [[直骨架的研究:Motorcycle graphs:Prior and related work:Geometric properties of the motorcycle graph]]
     - [[直骨架的研究:Motorcycle graphs:Stochastic considerations of the motorcycle graph]]
       - [[直骨架的研究:Motorcycle graphs:Stochastic considerations of the motorcycle graph:Number of intersections of bounded rays]]
@@ 行 58: / 行 63: @@
     - [[直骨架的研究:Motorcycle graphs:A simple and practice-minded implementation]]
       - [[直骨架的研究:Motorcycle graphs:A simple and practice-minded implementation:Details of the algorithm]]
-      - [[直骨架的研究:Motorcycle graphs:A simple and practice-minded implementation: Runtime analysis]]
+      - [[直骨架的研究:Motorcycle graphs:A simple and practice-minded implementation:Runtime analysis]]
       - [[直骨架的研究:Motorcycle graphs:A simple and practice-minded implementation:Experimental results and runtime statistics]]
       - [[直骨架的研究:Motorcycle graphs:A simple and practice-minded implementation:Extending the computation beyond the unit square]]
+    - [[直骨架的研究:Motorcycle graphs:Extracting the motorcycle graph from the straight skeleton]]
+      - [[直骨架的研究:Motorcycle graphs:Extracting the motorcycle graph from the straight skeleton:Approximating the motorcycle graph by the straight skeleton]]
+      - [[直骨架的研究:Motorcycle graphs:Extracting the motorcycle graph from the straight skeleton:Computing the motorcycle graph]]
+      - [[直骨架的研究:Motorcycle graphs:Extracting the motorcycle graph from the straight skeleton: Constructing the straight skeleton is P-complete]]
+    - [[直骨架的研究:Concluding remarks]]
+    - [[直骨架的研究:Notation]]
+    - [[直骨架的研究:Examples]]
+    - [[直骨架的研究:Bibliography]]
+    - [[直骨架的研究:Index]]
+{{pasted:20250925-222154.png}}
+利用原始多边形和由它导出的摩托图，我们构建一个平面图，即为扩展的波前,t 时刻的扩展波前记为$W*(G,t)$。扩展波前中的点进行标记，原多边形的凸点记为 Convex Vertex,原多边形的凹点记为 Reflex Vertex（即为摩托图中摩托的起点），摩托与原多边形的边相撞的点记为 Moving Steiner Vertex，多辆摩托相撞的点记为 Multi Steiner Vertex，其它的点记为 Resting Steiner Vertex（如图 8 所示）。
+在整个算法中，我们对波前中的边进行离散事件模拟，即维护一个最小优先级队列，波前中所有的边构成队列的元素（事件），边的消失时间为对应事件的优秀级。我们从初始的拓展波前$W*(G,t)$开始，将$W*(G,t)$ 中的每一条边 e 插入优先队列 Q 中。Q 按事件发生的时间（边的消失时间）先后顺序排列。
+ 完成初始操作之后，我们从 Q 中一个一个地抽取事件，并对其进行处理，修改拓展波前，并维护优先队列 Q，直到队列为空，算法执行完毕。下面将具体讨论不同的事件类型的处理过程：
+Edge Event: 两个凸点 u，v 间的边 e 消亡，如图 9(a) 所示。我们将 e 从原图中删除，并将 u,v 点合并为一个新的凸点 w。
+与点 w 相连的两条边将决定 w 的速度，因此，我们需要更新与 w 相连的两条边的消亡时间，并在 Q 中修改相应的项。当w 的两条边平行的时候，如果按这两条边来求 w 得速度，w的速度将趋向于无穷大，这将会导致后续的计算出现问题。我们对这种情况做特殊处理，将 w 的速度设为 0。最后，我们需要向直骨架中添加两条边 vw 和 uw。
+Split Event:一个凹点u和一个 moving Steiner 点v之间的边 e消亡，如图9（b）所示。我们可以注意到，v点是凹点u在摩托图中消亡的对应点。我们分别记$u_l$，$v_l$为与u，v相连的且在u左边的点，同样有$u_r$，$v_r$。我们删除边e，并合并点u和点v为一个新的凸点w1。w1的速度由与其相连的两条边决定。此处，我们需要检测三种特殊情况：（1）w相连的两条边平行，此时w的速度将设为0。（2）$u_l$，$v_l$，e构成一个三角形，SplitEvent 事件后，这个三角形消失。（3）e在原来的多边形的某条边上，如果b所示。同样地，我们对u，v做相似的操作。最后，我们需要向直骨架中添加一条边uv，在特殊情况（2）中还需要为凸点增加相应的直骨架。
+Start Event:一个 resting Steiner 点 v和一个凹点或一个 Moving Steiner点u之间的边e消亡，如图9(c)所示。v将成 为一个 Moving Steriner Vertex,而u的类型和速度不变，但是我们需要更新v的速度，并更新v的邻边的消亡时间。此外，有两种特殊情况需要特殊处理：（i）u的邻边、v的一条邻边和边e构成一个三角形，Start Event发生时该三角形消失。（ii）v的邻边中没有另外一条与e平行的边，即u发出的摩托因碰到其他摩托的轨迹而消失，原则上其他摩托会先到达v点，但这时候Start Event发生了，说明这两辆摩托同时到达v点。
+一般情况下 Start Event 不会向直骨架中贡献一条边，特殊情况（1）中三角形消失，其中的凸点会给直骨架增加一条边。
+Switch Event:一个凸点u和一个凹点或一个 moving Steiner 点v之间的边e消亡，如图9（d）所示。v点将从u的一条邻边跳到u的另一条邻边上，u和v的速度都将发生改变，需要更新u、v的邻边的消失时间。有一种特殊情况需要考虑：u的一条邻边、e和v的另一条不在原多边形上的邻边构成一个三角形，Switch Event发生时，该三角形消失。如果 Switch Event 发生在凸点与凹点之间，需要为直骨架增加边，如果Switch Event发生在凸点与Moving Steiner之 间，不需要为直骨架增加边。在特殊情况中消失的三角形会增加直骨架边。
+Multi Start Event:一个 moving Steiner 点 v和一个 multi Steiner 点u之间的边e消亡，如图9（e）所示。设其他与u相邻的顶点为u1，u2，..，u1，相应的u1，u2，..，ul与u形成的边为e1，e2，..，el，并且e1，e2，..，el按逆时针排序。u对应多个摩托相撞点，e边先消失，意味着这多个摩托不可能一起相撞，而是将v的多边形邻边进行分裂，即引入新的Moving Steiner点V2，V2.……，Vl，它们之间形成边viVi+1，（i=1，……，i—1），另外原来与v相邻的两个多边形顶点与v1，v相连，形成两条边。Multi Start Event 不直接产生直骨架边。
+Multi Split Event:连接凹点v1..,v的与一个 multi Steiner点 u的边e1，..，el同时消亡，如图9（f）所示，假设e1，e2，..，el逆时针方向排列。这个事件对应多个摩托同时相撞的情况，有可能发出新的摩托。设v1，..，vr对应的左右多边形邻边为
+l1，r1,...ll,rl....liri+1（i=1，.l—1）将决定一个新的凸点，如果l，r形成的角为凹角，此时这两条边决定一辆新的摩托：否则，它们构成凸角，不产生新的摩托。Multi Split Event中，v1..,vl中的每一个凹点会增加一条 直骨架边。
+Remainning Event:如果两个 Moving Steiner Vertex 构成的边 e消失，直接删除相应的边以及顶点即可。该事件不会增加直骨架边。
+除了上面七种事件外，其他的点的组合构成的事件不会发生。
+[[直骨架的研究:代码分析]]
+[[直骨架的研究:鞋带公式]]
+[[直骨架的研究:射线法]]
+[[直骨架的研究:边事件]]
+[[直骨架的研究:事件]]
-    -  [[直骨架的研究:Motorcycle graphs:Extracting the motorcycle graph from the straight skeleton]]

Detach Close

您访问的页面并不存在。如果允许，您可以使用创建该页面按钮来创建它。

差别

该主题尚不存在

张叶安的博客