直骨架的研究

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版		 前一修订版
直骨架的研究 [2025/09/25 18:17] – 张叶安直骨架的研究 [2025/10/16 11:17] (当前版本) – 张叶安
行 1: 行 1:
 +https://code.google.com/archive/p/straight-skeleton/source/default/source
 +
 +{{ :phdthesis及其翻译_1_.pdf |}}
 +
   - [[直骨架的研究:ABSTRACT]]   - [[直骨架的研究:ABSTRACT]]
   - [[直骨架的研究:Introduction]]   - [[直骨架的研究:Introduction]]
行 72: 行 76:
     - [[直骨架的研究:Index]]     - [[直骨架的研究: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 不直接产生直骨架边。
  
-I’m going to do three things to move this forward: +Multi Split Event:连接凹点v1..,v的与一个 multi Steiner点 u的边e1，..，el同时消亡，如图9（f）所示，假设e1，e2，..，el逆时针方向排列。这个事件对应多个摩托同时相撞的情况，有可能发出新的摩托。设v1，..，vr对应的左右多边形邻边为 
-•  Inspect the tail of your latest debug log to see where time stalls happen and whether our time “kick” is taking effect. +l1，r1,...ll,rl....liri+1（i=1，.l—1）将决定一个新的凸点，如果l，r形成的角为凹角，此时这两条边决定一辆新的摩托：否则，它们构成凸角，不产生新的摩托。Multi Split Event中，v1..,vl中的每一个凹点会增加一条 直骨架边。
-•  Search the codebase for places that may be re-enqueuing edges with stale/zero times. +
-•  Patch those spots to enforce strictly monotonic event times.+
  
-What I did just now: +Remainning Event:如果两个 Moving Steiner Vertex 构成的边 e消失，直接删除相应的边以及顶点即可。该事件不会增加直骨架边。 
-1) Read the latest log tail +除了上面七种事件外，其他的点的组合构成的事件不会发生。
-•  Observations: the stall-kick worked at the beginning (events at 1e-6 and 2e-6 processed), then a SPLIT_EVENT at t=6.909897 fired. Immediately after, I still see many Vertex.MovedPosition logs at “当前时间: 0”, which suggests some recomputation paths still call MovedPosition with 0 or re-enqueue events near or at the current time.+
  
-2) Searched the code for MovedPosition and direct heap updates +[[直骨架的研究:代码分析]]
-•  I searched all MovedPosition call sites and the event re-queue/update paths. +
-•  I found several direct calls to eventQueue.HeapUpdateKey(...) inside: +
-◦  Skeleton.handleMultiStartEvent.cs +
-◦  Skeleton.handleMultiSplitEvent.cs +
-•  These were re-queueing edges using raw Graph.calcEdgeVanishTime(e) without clamping to the current algorithm time. That can reintroduce near-current or back-in-time events and cause micro-step loops.+
  
-3) Applied patches to enforce monotonic event times in MultiStart/MultiSplit +[[直骨架的研究:鞋带公式]]
-•  Replaced all direct eventQueue.HeapUpdateKey(...) in MultiStart/MultiSplit with our monotonic helper, which clamps event time to be at least _dbgCurTime + 1e-9: +
-◦  __RecomputeAndUpdateEdge(e) +
-•  For new edges inserted during MultiStart, I also clamp the initial vanish time before insertion: +
-◦  t = Graph.calcEdgeVanishTime(e) +
-◦  if (double.IsNaN(t) || t < _dbgCurTime + 1e-9) t = _dbgCurTime + 1e-9 +
-◦  e.VanishTime = t; eventQueue.minHeapInsert(e) +
-•  These changes ensure any event times after MultiStart/MultiSplit strictly advance beyond the current event time, aligning with the stall-kick we already added at extraction time.+
  
-What I propose next +[[直骨架的研究:射线法]]
-•  Please rerun the star/concave polygon case with the updated code. +
-•  If it still appears stuck, share the last ~200 lines of the updated log again so I can confirm whether: +
-◦  Any remaining direct re-queues with stale times exist. +
-◦  The “kick” is firing repeatedly. +
-◦  Any adjacency violations or iteration-cap warnings are printed.+
  
-If the issue persists, my next steps will be: +[[直骨架的研究:边事件]]
-•  Audit any remaining places that compute vanish times (e.g., Graph code that sets initial vanish times when building motorcycle/split edges and then adds them to the queue) to ensure they are clamped appropriately when inserted. +
-•  Consider increasing the stall “kick” magnitude slightly if the geometry scale demands it, but I’d prefer to keep it minimal unless the logs indicate repeated re-kicks at the same time.+
  
-Would you like me to tail the new log once you run it again? If so, I can open the last 200–1000 lines to verify event progression.+[[直骨架的研究:事件]]
  
  
Detach Close

该主题尚不存在

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

  • 直骨架的研究.1758795433.txt.gz
  • 最后更改: 2025/09/25 18:17
  • 由 张叶安