直骨架的研究

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版		 前一修订版
直骨架的研究 [2025/09/25 21:28] – 张叶安直骨架的研究 [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）中三角形消失，其中的凸点会给直骨架增加一条边。
  
-Run completed on your latest polygon log and diagnostics saved. Here’s the short summary and what I recommend next. 
  
-What I ran +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之 间，不需要为直骨架增加边。在特殊情况中消失的三角形会增加直骨架边。
-•  Executed the harness with your latest available log (selected: C:\Users\11402\Desktop\SkeletonLogs\skeleton_debug_20250925_211825.log). +
-•  Generated full diagnostics (boundary/skeleton CSVs, wavefront times, meta).+
  
-Key results +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 不直接产生直骨架边。
-•  Completed: True +
-•  Boundary vertices parsed: 18 (note: it’s 9 unique points repeated twice) +
-•  Skeleton segments: 12 +
-•  Triangles: 48 +
-•  Wavefront samples: 7 +
-•  Time: 0.343s +
-•  ValleySummary: initReflex=8, written=8, missing=2 +
-◦  Warnings: ValleyMissing for reflex at (319,171) with two different IDs (duplicate entries)+
  
-Why the two “missing” valleys appear +Multi Split Event:连接凹点v1..,v的与一个 multi Steiner点 u的边e1，..，el同时消亡，如图9（f）所示，假设e1，e2，..，el逆时针方向排列。这个事件对应多个摩托同时相撞的情况，有可能发出新的摩托。设v1，..，vr对应的左右多边形邻边为 
-•  Your boundary in the log contains two identical loops (the same 9 vertices repeated). That creates duplicate reflex vertices at the same location with different IDs. The algorithm writes one valley for the “real” instance and then reports the duplicate as “missing.” This is a parsing artifact, not an algorithmic failure.+l1，r1,...ll,rl....liri+1（i=1，.l—1）将决定一个新的凸点，如果l，r形成的角为凹角，此时这两条边决定一辆新的摩托：否则，它们构成凸角，不产生新的摩托。Multi Split Event中，v1..,vl中的每一个凹点会增加一条 直骨架边。
  
-Diagnostics location (most relevant files) +Remainning Event:如果两个 Moving Steiner Vertex 构成的边 e消失，直接删除相应的边以及顶点即可。该事件不会增加直骨架边。 
-•  D:\在家加班\骨架库(最新20250923)\骨架库(最新20250917)(1)\HDSkeleton\Harness\bin\Debug\diag_runs_harness\FROM_LOG\ +除了上面七种事件外，其他的点的组合构成的事件不会发生。
-◦  from_log_boundary.csv (parsed boundary that was fed into the run) +
-◦  from_log_skeleton.csv (aggregated skeleton segments) +
-◦  run_20250925_212154_592\ +
-▪  boundary.csv, skeleton.csv, wavefront_times.txt, meta.txt+
  
-Recommendations +[[直骨架的研究:代码分析]]
-•  Let me add a normalization pass to the log loader so it: +
-◦  Removes consecutive duplicate points +
-◦  If the list is two identical halves, keeps only the first half +
-◦  Drops a final vertex if it equals the first (implicit closure) +
-•  Then rerun. Expected effect: the duplicate (319,171) entries collapse to one, clearing the two ValleyMissing warnings. +
-•  Optional follow-ups: +
-◦  Add a --csv <file> mode to feed raw x,y coordinates directly (bypasses log parsing). +
-◦  If you want to investigate the “calcMovingSteinerSpeed: mv or pv is null” warnings, I can add targeted debug guards/logs, but they didn’t affect completion here.+
  
-How to rerun locally +[[直骨架的研究:鞋带公式]]
-•  Latest log: D:\在家加班\骨架库(最新20250923)\骨架库(最新20250917)(1)\HDSkeleton\Harness\bin\Debug\HDSkeletonHarness.exe --log latest +
-•  Specific log file: HDSkeletonHarness.exe --log "C:\path\to\your\skeleton_debug_YYYYMMDD_HHMMSS.log"+
  
-Would you like me to implement the de-duplication in the log loader now and rerun to verify the ValleyMissing warnings disappear?+[[直骨架的研究:射线法]]
  
 +[[直骨架的研究:边事件]]
  
 +[[直骨架的研究:事件]]
  
  
Detach Close

该主题尚不存在

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

  • 直骨架的研究.1758806895.txt.gz
  • 最后更改: 2025/09/25 21:28
  • 由 张叶安