这是本文档旧的修订版！
利用原始多边形和由它导出的摩托图，我们构建一个平面图，即为扩展的波前,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©所示。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消失，直接删除相应的边以及顶点即可。该事件不会增加直骨架边。 除了上面七种事件外，其他的点的组合构成的事件不会发生。
Thanks for the detailed report. I reproduced the core differences against the C++ and found a critical mismatch that explains why concave skeleton lines still fail on a skewed (non-regular) star polygon.
What I changed just now • I updated calcMovingSteinerSpeed in HDSkeleton/Skeleton/Graph.cs to exactly match the C++ formula: ◦ C++: mpv→speed = e1 / 1); ◦ Before: the C# code had a fallback that replaced near-degenerate cases with a “safe” direction (e2 or (1,0)). This suppresses the very large speeds that the C++ logic intentionally creates in near-parallel configurations. ◦ After: C# now computes mpv.Speed = e1 / denom with denom = |e1 - dot(e1, e2) e2| and only guards denom from being zero (set to a tiny EPS). No direction fallback. This aligns with C++ and preserves the intended scheduling of Split/Switch events.
Why this matters for skewed star polygons • Skewed star polygons create many near-parallel interactions between motorcycle edges and polygon edges. The “fallback” in C# often reduced moving-Steiner speeds to a tame unit direction, which: ◦ Inflated edge vanish times (dl ⇐ 0 or very small), so Split events didn’t trigger when they should. ◦ Broke the temporal order of events in the queue, indirectly causing missing concave skeleton spokes. • By removing the fallback and restoring the C++ behavior, moving-Steiner vertices now get the correct (often very large) speed in near-degenerate cases, making the Split/Switch event schedule match the C++ result and restoring the expected concave skeleton lines.
What we had already aligned earlier • Split Event (motorcycle-edge branch) only adds one skeleton edge to the collision point (from the reflex side or the other side), not two. This exactly matches the C++ implementation (even though the high-level doc says “add uv,” the C++ code draws from vertex to collision point, and adds the third leg only for the disappearing triangle special cases). • Switch, Edge, Multi Split: verified to add skeleton edges in the same conditions as C++. • Event type matrix and dispatcher: matches C++ ordering and selection. • POLYGON_EDGE split branch: we perform reconnections and times updates without directly adding a skeleton edge, as per C++.
How to verify on your side • Rebuild is already successful. Please run the Visualizer and test with a skewed star polygon (examples) ◦ Example 1 (CCW order): (0,0) (4,7) (8,0) (0,5) (8,5) (0,0) ◦ Example 2 (more skewed): (0,0) (2,7) (5,0) (-1,4) (6,6) (0,0) • Watch the log: you should see Split/Switch events around the concave spikes; skeleton edges should now emanate from reflex vertices toward internal collision points, consistent with the C++ behavior.
If you still see issues • Orientation: Make sure the polygon is provided consistently (prefer CCW). While the code classifies convex/reflex using determinant at a harmonized start time, inconsistent orientation can flip convex/reflex classification. • Edge vanish times: If any edge shows VanishTime = MaxValue when you expect an event, dump the two endpoint speeds and the normalized edge direction to catch dl ⇐ 0 cases. With the updated moving-Steiner speed, you should see far fewer of these. • Enable targeted debug in handleSplitEvent and handleSwitchEvent: ◦ Log event.Type, edge.Type (POLYGON_EDGE vs MOTORCYCLE_EDGE), Tail/Head vertex types, and the computed collision point. ◦ Log when the “triangle disappears” special cases are hit (where we add the extra spoke). • Compare with C++ using the same star polygon input if possible; now that moving-Steiner speed is identical, the event order and skeleton spokes should match.
Summary • Root cause for skewed star polygons: moving-Steiner speed fallback diverged from the C++ formula, suppressing Split/Switch and hiding concave spokes. • Fixed by matching the C++ calcMovingSteinerSpeed exactly (no direction fallback; only guard zero denominator). • Combined with the earlier Split Event alignment, this should produce the correct concave skeleton lines for your skewed star tests.
If you’d like, I can also add minimal debug prints to the Split and Switch handlers to confirm which branch (polygon-edge vs motorcycle-edge split) is exercised on your star test and list the exact skeleton segments added per event
张叶安