显示页面讨论反向链接回到顶部 本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。 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]] - [[直骨架的研究:Introduction:preliminaries and definitions:The straight skeleton of a planar straight-line graph]] - [[直骨架的研究:Introduction:preliminaries and definitions:Roof and terrain model]] - [[直骨架的研究:Introduction:preliminaries and definitions:The motorcycle graph]] - [[直骨架的研究:Introduction:applications]] - [[直骨架的研究: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]] - [[直骨架的研究:Introduction:applications:Shape reconstruction and contour interpolation]] - [[直骨架的研究:Introduction:applications:Polygon decomposition]] - [[直骨架的研究:Introduction:applications:Area collapsing in geographic maps and centerlines of roads]] - [[直骨架的研究:Introduction:prior work]] - [[直骨架的研究:Introduction:prior work:Runtime bounds for the straight skeleton]] - [[直骨架的研究:Introduction:prior work:Algorithms for computing straight skeletons and motorcycle graphs]] - [[直骨架的研究:Introduction:prior work:Aichholzer et al., 1995]] - [[直骨架的研究:Introduction:prior work:Aichholzer and Aurenhammer, 1996]] - [[直骨架的研究:Introduction:prior work:Eppstein and Erickson, 1999]] - [[直骨架的研究:Introduction:prior work:Cheng and Vigneron, 2002]] - [[直骨架的研究:Introduction:prior work:Felkel and Obdrzalek, 1999]] - [[直骨架的研究:Introduction:prior work:Implementations]] - [[直骨架的研究:Introduction:prior work:Summary]] - [[直骨架的研究:Introduction:generalizations and related problems]] - [[直骨架的研究:Introduction:generalizations and related problems:Linear axis]] - [[直骨架的研究:Introduction:generalizations and related problems:Weighted straight skeleton]] - [[直骨架的研究: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:geometric properties of the straight skeleton]] - [[直骨架的研究:computing the straight skeleton:the triangulation-based approach]] - [[直骨架的研究:computing the straight skeleton:the triangulation-based approach:The number of reappearances of diagonals]] - [[直骨架的研究:computing the straight skeleton:the triangulation-based approach:Good triangulations and bad polygons]] - [[直骨架的研究:computing the straight skeleton:the triangulation-based approach:Steiner triangulations without flip events]] - [[直骨架的研究:computing the straight skeleton:a novel wavefront-type approach]] - [[直骨架的研究:computing the straight skeleton:a novel wavefront-type approach:Motivation]] - [[直骨架的研究:computing the straight skeleton:a novel wavefront-type approach:The extended wavefront and a novel straight-skeleton algorithm]] - [[直骨架的研究:computing the straight skeleton:a novel wavefront-type approach:Runtime analysis and conclusion]] - [[直骨架的研究:computing the straight skeleton:a generalized motorcycle graph]] - [[直骨架的研究:computing the straight skeleton:a generalized motorcycle graph:motivation and definition]] - [[直骨架的研究: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: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:Details of the implementation Bone]] - [[直骨架的研究:computing the straight skeleton:The general wavefront-type algorithm:Experimental results and runtime statistics]] - [[直骨架的研究: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:Prior work]] - [[直骨架的研究: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]] - [[直骨架的研究:Motorcycle graphs:Stochastic considerations of the motorcycle graph:Implications to the motorcycle graph]] - [[直骨架的研究: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: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消失，直接删除相应的边以及顶点即可。该事件不会增加直骨架边。 除了上面七种事件外，其他的点的组合构成的事件不会发生。 [[直骨架的研究:代码分析]] [[直骨架的研究:鞋带公式]] [[直骨架的研究:射线法]] [[直骨架的研究:边事件]] [[直骨架的研究:事件]] 登录 Detach Close 该主题尚不存在 您访问的页面并不存在。如果允许，您可以使用创建该页面按钮来创建它。 直骨架的研究.txt 最后更改: 2025/10/16 11:17由 张叶安 登录
张叶安