buildFromPolygon throws std::length_error

[janis-github]

Here is the source:

await SkeletonBuilder.init()

const data = [
  [7481, 274],
  [10509, 115],
  [10555, 964],
  [7481, 1126],
  [7481, 1866],
  [4356, 1866],
  [4356, -1896],
  [7481, -1896],
  [7481, 274],
]

SkeletonBuilder.buildFromPolygon([data])

It produces the following error:

Uncaught P std::length_error: vector
    at __cxa_throw (/Users/janis/react/node_modules/straight-skeleton/dist/index.js:1:1019020)
    at $func147 (wasm/002de27a.wat:35918:1)
    at $func138 (wasm/002de27a.wat:35424:1)
    at $func880 (wasm/002de27a.wat:131102:1)
    at $func903 (wasm/002de27a.wat:136677:1)
    at $func874 (wasm/002de27a.wat:128794:1)
    at $func1307 (wasm/002de27a.wat:190838:1)
    at $func1497 (wasm/002de27a.wat:221464:1)
    at $func41 (wasm/002de27a.wat:20708:1)
    at $create_straight_skeleton (wasm/002de27a.wat:28542:1)

Would it be possible to know why this happens? Maybe there is something specific with the polygon what triggers it that would suggest a workaround?

This polygon works fine:

const data = [
  [7481, 274],
  [10509, 215],  // changing 115 to 215 here fixes the crash!
  [10555, 964],
  [7481, 1126],
  [7481, 1866],
  [4356, 1866],
  [4356, -1896],
  [7481, -1896],
  [7481, 274],
]

[matthewjacobson]

I have been running into the same issue so I ended up creating my own wrapper library: https://github.com/matthewjacobson/str8

The underlying problem is that CGAL's straight skeleton code uses the fast inexact-constructions kernel (EPICK) by default. For most inputs this works well and is significantly faster, but highly symmetric geometries—such as a regular grid of identical, evenly-spaced holes—can create near-simultaneous or degenerate events. Because EPICK relies on floating-point arithmetic, it may not be able to resolve those events consistently, causing the straight skeleton computation to fail.

In str8, this is handled automatically. The library first attempts the computation using EPICK for speed. If that fails, it transparently retries using the exact-constructions kernel (EPECK), which is slower but much more robust for these degenerate and highly symmetric cases.

It seems to be working for your example from above. You can try it out here and paste the following GeoJson:
{"type":"Polygon","coordinates":[[[7481, 274], [10509, 115], [10555, 964], [7481, 1126], [7481, 1866], [4356, 1866], [4356, -1896], [7481, -1896], [7481, 274]]]}