这是本文档旧的修订版！

1. ABSTRACT
2. Introduction
   1. organization
   2. preliminaries and definitions
      1. The straight skeleton of a simple polygon
      2. The straight skeleton of a planar straight-line graph
      3. Roof and terrain model
      4. The motorcycle graph
   3. applications
      1. Mitered offset curves and NC-machining
      2. Building roofs and generating terrains
      3. Mathematical origami and the fold-and-cut problem
      4. Shape reconstruction and contour interpolation
      5. Polygon decomposition
      6. Area collapsing in geographic maps and centerlines of roads
   4. prior work
      1. Runtime bounds for the straight skeleton
      2. Algorithms for computing straight skeletons and motorcycle graphs
      3. Aichholzer et al., 1995
      4. Aichholzer and Aurenhammer, 1996
      5. Eppstein and Erickson, 1999
      6. Cheng and Vigneron, 2002
      7. Felkel and Obdrzalek, 1999
      8. Implementations
      9. Summary
   5. generalizations and related problems
      1. Linear axis
      2. Weighted straight skeleton
      3. Straight skeleton of polyhedra in R³
      4. City Voronoi diagrams
3. computing the straight skeleton
   1. geometric properties of the straight skeleton
   2. the triangulation-based approach
      1. The number of reappearances of diagonals
      2. Good triangulations and bad polygons
      3. Steiner triangulations without flip events
   3. a novel wavefront-type approach
      1. Motivation
      2. The extended wavefront and a novel straight-skeleton algorithm
      3. Runtime analysis and conclusion
   4. a generalized motorcycle graph
      1. motivation and definition
      2. geometric properties of the generalized motorcycle graph
      3. the lower envelope based on the generalized motorcycle graph
   5. The general wavefront-type algorithm
      1. Details of the general algorithm
      2. Runtime analysis
      3. Details of the implementation Bone
      4. Experimental results and runtime statistics
   6. Summary
4. Motorcycle graphs
   1. Prior and related work
      1. Applications of motorcycle graphs and related problems
      2. Prior work
      3. Geometric properties of the motorcycle graph
   2. Stochastic considerations of the motorcycle graph
      1. Number of intersections of bounded rays
      2. Implications to the motorcycle graph
   3. A simple and practice-minded implementation
      1. Details of the algorithm
      2. Runtime analysis
      3. Experimental results and runtime statistics
      4. Extending the computation beyond the unit square
   4. Extracting the motorcycle graph from the straight skeleton
      1. Approximating the motorcycle graph by the straight skeleton
      2. Computing the motorcycle graph
      3. Constructing the straight skeleton is P-complete
   5. Concluding remarks
   6. Notation
   7. Examples
   8. Bibliography
   9. Index

I’m going to do three things to move this forward: • Inspect the tail of your latest debug log to see where time stalls happen and whether our time “kick” is taking effect. • 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: 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.