Glonce

earstrip polygon triangulator claims 14% edge over earcut.hpp

toolsThe Glonce editorsHacker News🔥57Glonce rating57Impact40Novelty55Relevance70Surprise40Players10Credibility75

The team behind a map engine at globus.software has published its polygon triangulator as a small open-source library called earstrip. It is released under the ISC license, the same one earcut uses, and ships as one C++ header plus a WebAssembly build on npm that takes the same arguments as earcut. The authors say that in C++ it is 14% faster than earcut.hpp, and in the browser 1.4 to 2.1 times as fast as earcut.js. The post's headline cites 489 ms for 3.7 million map polygons; the comparison with earcut sits near the end of the post, and the rest explains how they got there.

The motivation: a GPU fills triangles and nothing else, while a map is mostly polygons (buildings, parks, parking lots, the strip of grass between two tram tracks). Every outline must be cut into triangles before it can be filled. The demo blocks of Śródmieście in Warsaw hold 331 polygons with 5,151 vertices, which become 4,514 triangles.

The benchmark set is zoom level 13 of the team's offline map of the Masovian Voivodeship, the region around Warsaw: 3,740,425 polygons. On one core of an M4 Pro, the engine's old constrained Delaunay triangulator needed 2.93 seconds to cut all of them. This October the author replaced it with ear clipping. To write the post, the author rebuilt the clipper one idea at a time, one commit per idea, and timed every commit on the same polygons.

Why drop Delaunay: a Delaunay triangulation has the largest smallest angle among all triangulations of the same points, which matters when you interpolate across triangles or run a simulation. A flat fill does not care, since a GPU fills a needle-thin triangle as correctly as a fat one. Meanwhile almost half of the Masovian polygons, 1.8 million, have four vertices or fewer. A triangle needs no cutting and a convex quad is two triangles, yet the Delaunay code spends 419 ms on them, building each triangulation from scratch.

How ear clipping works: an ear is a corner (three consecutive vertices a, b, c) where the corner at b is convex and no other part of the polygon reaches into triangle abc. Cut it off and a polygon with one fewer vertex remains. Gary Meisters proved in 1975 that every simple polygon with more than three vertices has at least two non-overlapping ears, so a polygon with n vertices falls apart into n minus 2 triangles. The simplest ear test checks the corner, then every other boundary vertex. A point on a triangle edge counts as inside, except a point at exactly the position of a, b or c, which happens where an outline meets itself at one vertex.

Holes: 11,345 of the Masovian polygons have holes, such as courtyards and forest clearings. Each hole is stitched to the outer ring with a bridge, an edge from a hole vertex to a boundary vertex, walked once in each direction, so the polygon becomes a single ring. To find a safe bridge the post follows David Eberly's write-up: take the hole's rightmost vertex m, cast a ray to the right, find the first edge hit at I with far end P, and use m to P if no boundary vertex lies inside triangle m, I, P. Otherwise it picks the dent in the triangle closest in angle to the ray. Holes are bridged rightmost first. Map data adds two cases: integer tile-grid coordinates make rays along grid lines common (the author's first version got this wrong), and mappers often draw a courtyard that touches the outer ring at one point, which needs no bridge.

Step 1, the naive clipper (heading: 1,812 ms less than Delaunay). With holes bridged, a first complete version tests each corner against the whole boundary and writes three indices per triangle. It takes 1.12 seconds on the Masovian polygons, 2.6 times faster than Delaunay. But the 1,123 largest polygons, with 257 vertices or more, take 199 ms to clip against 90 ms with Delaunay, because each test walks hundreds of vertices and a polygon needs hundreds of tests, so cost grows with the square of its size.

Step 2, test only the dents (237 ms saved). If any vertex lies inside a convex corner's triangle, the one closest to the corner must be a reflex vertex (a dent), so the test can scan only the dents. The engine keeps a list that only shrinks. The 28.1 million ear tests now look at 185 million points instead of 353 million. The gain is smaller than one might expect because building outlines have many dents: the example building with an arch has 15 among its 27 vertices. The smallest polygons got slower, from 34 to 54 ms, because sorting corners into dents costs more than the walk it saves for a triangle or quad.

Step 3, skip tests on convex polygons (2 ms saved). A polygon without dents is convex and can be cut without any ear tests. Checking for it needs care: all corners turning left is not enough, since a star that goes around its centre twice also does that. The engine also requires that the x direction of the edges changes exactly twice, at the leftmost and rightmost points; both counts come from the loop that marks the dents. The shortcut removes 4.4 million of the 28.1 million ear tests, but those were the cheapest, so the total barely moves. Polygons with four vertices or fewer win back part of the loss, from 54 to 48 ms. Triangles and quads get their own shortcut before that loop.

Step 4, write strips (118 ms saved). A GPU can draw a triangle strip, where each new index adds a triangle made of it and the two before. A convex ring makes one strip if you zig-zag across it. The ear clipper writes strips too: cutting an ear sharpens the corners of its two neighbours, so they are tried first, alternating between the two ends while the ears last. When the next corner is not an ear, the strip ends and the walk continues. The 21.5 million triangles now need 35.8 million indices instead of 64.5 million. Ear tests do not drop; they rise slightly, to 25.0 million from 23.7 million, because every strip ends on a failed test. The available text breaks off in this section, just as it says the total falls further.

Key facts

  • earstrip is an ISC-licensed polygon triangulator: one C++ header plus a WebAssembly build on npm that takes the same arguments as earcut.
  • The authors claim it is 14% faster than earcut.hpp in C++ and 1.4 to 2.1 times as fast as earcut.js in the browser; the post's headline cites 489 ms for 3.7 million polygons.
  • The benchmark is 3,740,425 polygons of the Masovian Voivodeship at zoom level 13, timed on one core of an M4 Pro; the old constrained Delaunay triangulator needed 2.93 seconds.
  • A naive ear clipper took 1.12 s (2.6 times faster than Delaunay); testing only reflex vertices saved 237 ms, a convex-polygon shortcut 2 ms, and triangle strips 118 ms.
  • Strips cut the indices for 21.5 million triangles from 64.5 million to 35.8 million, while ear tests rose slightly from 23.7 million to 25.0 million.

Why it matters

Map renderers spend real time turning building, park and land-use outlines into GPU triangles, and earcut is a widely used reference for it. The authors say their replacement of a constrained Delaunay triangulator with ear clipping cut the cost on a 3.7 million polygon region and that the resulting library beats earcut in both C++ and WebAssembly. The post is also a step-by-step account with a timing after every commit, which makes it useful as a worked example of where the time actually goes: Delaunay quality buys nothing for a flat fill, and the small polygons dominate by count.

Who it affects

Developers of map engines, vector tile renderers and other 2D graphics code that already use earcut.hpp or earcut.js, since earstrip takes the same arguments in its WebAssembly build. It also touches anyone who feeds polygons with holes to a GPU, and readers interested in how ear clipping, hole bridging and triangle strips fit together.

How to use it

earstrip is a single C++ header, and a WebAssembly build is on npm taking the same arguments as earcut. It is under the ISC license, the same one earcut uses. The post's code shows an ear test that scans only reflex vertices and a strip-writing loop that alternates between the two ends of each cut, which can be read as a recipe for the same optimisations in other triangulators.

How solid is it

The numbers come from the authors' own benchmark on one dataset (3,740,425 polygons of the Masovian Voivodeship at zoom level 13) and one machine (a single core of an M4 Pro), with a timing after each commit. The 14% and 1.4 to 2.1 times claims are the authors' own; no third-party benchmark or reaction to earstrip is given. The 489 ms figure appears only in the headline, and the text covered does not say which hardware, language build or output format it refers to. The write-up is detailed and internally consistent: for example, the 2.93 s Delaunay and 1.12 s naive totals match the 1,812 ms step heading.

Risks and caveats

The speed claims are relative to earcut on map polygons dominated by small building outlines; results on other data, such as very large or heavily holed polygons, may differ. The naive clipper was slower than Delaunay on the 1,123 largest polygons (199 ms against 90 ms), and the dents-only step made the smallest polygons slower (34 to 54 ms) before a shortcut recovered part of it (48 ms). Ear clipping also gives up Delaunay's well-shaped triangles, which the authors say matter for interpolation or simulation but not for a flat fill. Strips raise the ear test count slightly, from 23.7 million to 25.0 million.

“A flat fill doesn't care: a GPU fills a needle-thin triangle as correctly as a fat one.”

— globus.software, on why Delaunay triangle quality is not needed for map fills