Faster than earcut: triangulating 3.7M map polygons in 489 ms(globus.software)
227 points by molind 3 days ago | 40 comments
tl;dr: Earstrip is a new C++/WebAssembly polygon triangulation library (ISC-licensed, earcut-compatible API) that triangulates 3.7M map polygons in 489ms—14% faster than earcut.hpp natively and 1.4-2.1x faster than earcut.js in browsers. Key optimizations include only testing reflex ("dent") vertices for ear-blocking, shortcutting convex polygons, emitting triangle strips instead of individual triangles, bucketing dents spatially, and using branchless counting passes. It falls back to constrained Delaunay triangulation for pathological cases like polygons with many holes or no valid ears after grid rounding.
HN Discussion:
  • ↑Praise for the library and performance improvements with interest in cross-pollinating optimizations
  • ~Concern about triangle quality — long thin slivers may be bad for GPU rasterization
  • •Suggestions to compare against other established triangulation libraries/algorithms
  • •Questioning why ear clipping dominates over asymptotically better algorithms like Seidel's
  • •Curiosity about the role of LLM assistance in deriving the optimizations