![\"Evgen](\"https://github.com/molind.png\")
October 16, 2026 · 20 min read
\nEvgen Bodunov
\nCEO @ Globus Software
\nWe have published the polygon triangulator of our map engine as a small library,\nearstrip, under the ISC license, the same one\nearcut uses. It is one C++ header, and a WebAssembly build on\nnpm that takes the same arguments as earcut. In C++ it is 14% faster than\nearcut.hpp, in the browser 1.4 to 2.1 times as fast as earcut.js, and the\ncomparison is near the end. This post is about how we got\nthere.
\nA GPU fills triangles and nothing else. A map, on the other hand, is mostly polygons: buildings, parks, parking\nlots, the strip of grass between two tram tracks. Here are a few blocks of Śródmieście in Warsaw the way our\nrenderer reads them from a map file, :
\nBefore any of this gets a fill, every outline has to be cut into\n. Hover over a polygon, or tap it, to see what it turns into.\nThese blocks hold 331 polygons with 5,151 vertices, and they become 4,514 triangles.
\nZoom level 13 of our offline map of the Masovian Voivodeship, the region around Warsaw, has 3,740,425 polygons.\nOn one core of an M4 Pro, the constrained Delaunay triangulator in our engine needs 2.93 seconds to cut all of\nthem. This October I replaced it with ear clipping. To write this post I rebuilt the ear clipper one idea at a\ntime, one commit per idea, and timed every commit on those same 3.7 million polygons, so each section below ends\nwith a number.
\nA triangulation of a set of points is Delaunay when no point lies inside the circle through the three corners of\nany triangle. Two triangles that share an edge are enough to see how the rule works. Drag the point D:
\nSmallest angle 45°; with BD instead it would be 37°
\nWhile D stays outside the dashed circle through A, B and C, the shared edge is AC.\nand the edge flips to BD;\nand it flips back. Each flip is a local repair,\nand a triangulation where no edge wants to flip is Delaunay. Of all the ways to triangulate the same points, it\nhas the largest smallest angle. The orange arc marks the smallest angle of the two\ntriangles, and the line under the figure shows what the other diagonal would give: wherever you put D, the edge\nthe circle rule picks wins.
\n"Constrained" means that the polygon's own edges must stay edges of the triangulation, even where the circle rule\nwould flip them away. Our triangulator inserts the vertices one at a time. For each new point it walks across the\ntriangles built so far until it finds the one the point falls into, splits it, and flips edges around the new\npoint until the circle rule holds again. It also forces the polygon's edges in, and at the end it keeps only the\ntriangles that lie inside the polygon and outside its holes.
\nWell-shaped triangles matter when you interpolate something across them or run a simulation on them. A flat fill\ndoesn't care: a GPU fills a needle-thin triangle as correctly as a fat one. And most of the work is spent on\npolygons that hardly need any. Almost half of the Masovian polygons, 1.8 million, have four vertices or fewer.\nA triangle needs no cutting at all and a convex quad is two triangles, yet the Delaunay code spends 419 ms on\nthem, building each triangulation from scratch.
\nAn ear of a polygon is a corner you can cut off with one straight cut. Take three consecutive vertices a, b and c.\nIf the corner at b is convex and no other part of the polygon reaches into the triangle abc, that triangle is an\near. Cut it off, and what remains is a polygon with one vertex fewer. In 1975 Gary Meisters proved that every\nsimple polygon with more than three vertices has at least two ears that don't overlap. So there is always another\near to cut, and a polygon with n vertices falls apart into n − 2 triangles.
\nHere is one of the buildings from the blocks above. Move the slider\nto cut its ears one at a time, or :
\n0 / 25
\nThe green triangle is the next ear to go. The algorithm needs one test, "is this corner an\near?", and the simplest version of it checks the corner and then every other vertex of the boundary. cross is\nthe 2×2 determinant found in every geometry codebase; it is positive when c lies to the left of the line from a\nto b, so for a boundary that runs counter-clockwise a positive cross(a, b, c) means a convex corner:
static double cross(double ax, double ay, double bx,\n\ndouble by, double cx, double cy)\n\n{\n\nreturn (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);\n\n}\n\nbool isEar(uint32_t v) const\n\n{\n\nconst Node &b = _nodes[v];\n\nconst Node &a = _nodes[b.prev], &c = _nodes[b.next];\n\nif (cross(a, b, c) <= 0)\n\nreturn false; // turns the wrong way, or not at all\n\nfor (uint32_t w = c.next; w != b.prev;\n\nw = _nodes[w].next) {\n\nconst Node &p = _nodes[w];\n\nif (cross(a.x, a.y, b.x, b.y, p.x, p.y) < 0 ||\n\ncross(b.x, b.y, c.x, c.y, p.x, p.y) < 0 ||\n\ncross(c.x, c.y, a.x, a.y, p.x, p.y) < 0)\n\ncontinue; // outside the triangle\n\nif (!samePos(p, a) && !samePos(p, b) &&\n\n!samePos(p, c))\n\nreturn false;\n\n}\n\nreturn true;\n\n}A point on an edge of the triangle counts as inside: if the ear touched the rest of the boundary, cutting it off\nwould leave a polygon that touches itself. The one exception is a point at exactly the position of a, b or c,\nwhich happens where an outline meets itself at a single vertex. Holes make that common.
\nEar clipping works on one closed boundary, and 11,345 of the Masovian polygons have holes, such as courtyards and\nclearings in forests. The way to deal with them is to cut each hole open and stitch it to the outer ring with a\nbridge, an edge from a vertex of the hole to a vertex of the boundary, walked once in each direction. The\nboundary then runs around the outside, crosses the bridge, goes around the hole the other way and comes back.\nThere is no area between the two copies of the bridge, so the polygon is the same, but now it is one ring.
\nThe bridge must not cross anything. David Eberly's write-up of ear\nclipping has a neat way to find\none. Take the rightmost vertex of the hole, m, and cast a ray to the right. The first edge the ray hits, at I,\nhas an end P further to the right. If no boundary vertex lies inside the triangle m, I, P, the bridge m–P is\nsafe. You can drag the hole around:
\nThe tip of the dent lies in the triangle m, I, P. A bridge to P would cross the boundary, so it goes to the dent.
\nthe triangle is empty and the bridge goes to P.\nthe tip of the dent sits\ninside the triangle, and the bridge goes to the dent instead: of the dents in the triangle, Eberly takes the one\nclosest in angle to the ray. Holes are bridged rightmost first, so a hole further left can bridge to one that is\nalready part of the boundary.
\nMap data adds two cases of its own. Our coordinates are integers on a tile grid, so a ray along a grid line runs\nall the time; the crossing test passes\nover such a vertex, and my first version got exactly this case wrong. And mappers often draw a courtyard that\nat one point. Such a hole needs no bridge:\nthe two rings are joined at the shared vertex.
\nWith holes bridged, the first complete version walks around the boundary, tests corners with the isEar above,\ncuts every ear it finds and writes each triangle as three indices. On the Masovian polygons it takes 1.12\nseconds, 2.6 times faster than Delaunay. The chart splits each time by polygon size; hover over a part of a bar\nto see its number, or click a row:
Delaunay2,931 ms
\nup to 4 vertices5–8 vertices9–32 vertices33–256 vertices257 and more vertices
\nis shorter than\nin every size class but the last. The 1,123 largest polygons,\nwith 257 vertices or more, take 199 ms to clip and 90 ms with Delaunay. Each ear test there walks hundreds of\nvertices, and a polygon needs hundreds of tests, so the cost grows with the square of its size. The rest of this\npost is about making the ear test cheaper and needed less often.
\nLook at which vertices can actually stop a convex corner from being an ear. Say some vertices lie inside its\ntriangle, and take the one closest to the corner itself. Its two edges can't cross the sides of the triangle, so\nboth run back, away from the corner, and the polygon wraps around that vertex from the corner's side. That makes\nit a reflex vertex, a dent. So if anything is inside the triangle, a dent is inside it\ntoo, and the test only has to look at the dents.
\nThe engine keeps a list of them. A dent leaves the list when cutting its neighbour makes it convex, and a convex\ncorner never turns into a dent, so the list only shrinks. The test becomes:
\nbool isEar(uint32_t v) const\n\n{\n\nconst Node &b = _nodes[v];\n\nif (b.reflex)\n\nreturn false;\n\nconst Node &a = _nodes[b.prev], &c = _nodes[b.next];\n\nfor (uint32_t i = 0; i < _live; ++i) {\n\nconst Item &p = _items[i]; // a dent\n\nif (p.node == b.prev || p.node == b.next)\n\ncontinue;\n\nif (cross(a.x, a.y, b.x, b.y, p.x, p.y) < 0 ||\n\ncross(b.x, b.y, c.x, c.y, p.x, p.y) < 0 ||\n\ncross(c.x, c.y, a.x, a.y, p.x, p.y) < 0)\n\ncontinue;\n\nif ((p.x != a.x || p.y != a.y) &&\n\n(p.x != b.x || p.y != b.y) &&\n\n(p.x != c.x || p.y != c.y))\n\nreturn false;\n\n}\n\nreturn true;\n\n}The 28.1 million ear tests now look at 185 million points instead of 353 million, and the total drops to\n. That is less than you might expect, because building outlines\nhave a lot of dents.\nThe building with the arch above has 15 of them among its 27 vertices. And the smallest polygons get slower, from\n34 to 54 ms: for a triangle or a quad, sorting the corners into dents and the rest costs more than the walk it\nsaves.
\nA polygon without dents is convex, and every corner of a convex polygon is an ear, so it can be cut without a\nsingle test. Checking for that needs care. "Every corner turns left" is not enough:
\nCorners turning left: 5 of 5. Changes of x direction: 4. Not convex.
\nThe turns left at all five corners, because it goes around its\ncentre twice. The engine adds one more condition. Walking around a convex ring, the edges go right along the\nbottom and left along the top, so their x direction changes exactly twice, at the leftmost and the rightmost\npoint. The passes; the star changes direction four times, at\nthe circled corners, and goes to the ordinary ear tests. Both counts come out of the same\nloop that marks the dents, so the check costs almost nothing. Triangles and quads get their own shortcut before\nthat loop.
\nThe shortcut removes 4.4 million of the 28.1 million ear tests, but those were the cheapest ones: a ring without\ndents has nothing to scan. On its own it barely moves the total, ,\nthough the polygons with four vertices or fewer win back part of what the dents cost them, from 54 to 48 ms. It\nmatters more in the next step, where a convex ring becomes a single strip.
\nSo far every triangle costs three indices. A GPU can also draw a triangle strip, where each new index adds a\ntriangle made of it and the two before. A convex ring makes one strip if you zig-zag across it:
\n0 1 7 2 6 3 5 4
The ear clipper can write strips too. Cutting an ear makes the corners of its two neighbours sharper, so they\nare good candidates for the next ear, and cutting one of them extends the strip by a single index. The engine\ntries them first and keeps alternating between the two ends while the ears last. In its code the neighbours of\nthe cut vertex are a and b:
\n// The next ear alternates between the ends of the cut.\n\nwhile (true) {\n\nif (sideA) {\n\nconst uint32_t z = n[a].prev;\n\n_strips.push_back(n[z].index);\n\nunlink(a);\n\na = z;\n\n} else {\n\nconst uint32_t z = n[b].next;\n\n_strips.push_back(n[z].index);\n\nunlink(b);\n\nb = z;\n\n}\n\ncount--;\n\nsideA = !sideA;\n\nif (count < 3 || !isEar(sideA ? a : b))\n\nbreak;\n\n}When the next corner is not an ear, the strip ends and the walk goes on from where it stopped. The 21.5 million\ntriangles now take 35.8 million indices instead of 64.5 million. The ear tests don't get fewer: the naive walk\nalready went on at the next corner after a cut, and now every strip also ends on a test that fails, 25.0 million\ninstead of 23.7 million. Still, the total falls to , and the\nlargest polygons drop from 146 to 103 ms.
\nA forest or a lake can have thousands of vertices and hundreds of dents, and each ear test still reads every one\nof them. When a polygon has more than 32 dents, the engine sorts them into buckets along the longer side of their\nbounding box, about two dents per bucket. An ear test looks only at the buckets that its triangle spans. As dents\nturn convex and leave, the index is rebuilt once half of it is gone.
\nPoints scanned fall from 181 million to 101 million, almost all of it on the large polygons: the polygons with\n257 vertices or more go from 103 to 57 ms. Total: .
\nThe loop in the dent test exits at the first dent inside the triangle. Most of the time there is none: the test\nreads all the dents and says yes. An early exit then buys nothing, and the three comparisons per point are\nbranches the CPU has to predict. The engine first runs a pass that only counts dents inside the triangle, with no\nbranches at all:
\nconst double abx = b.x - a.x, aby = b.y - a.y;\n\nconst double bcx = c.x - b.x, bcy = c.y - b.y;\n\nconst double cax = a.x - c.x, cay = a.y - c.y;\n\nuint32_t hits = 0;\n\nfor (uint32_t i = begin; i < end; ++i) {\n\nconst Item &p = items[i];\n\nconst double side = std::min(\n\nstd::min(abx * (p.y - a.y) - aby * (p.x - a.x),\n\nbcx * (p.y - b.y) - bcy * (p.x - b.x)),\n\ncax * (p.y - c.y) - cay * (p.x - c.x));\n\nhits += (uint32_t)(side >= 0) & (uint32_t)(p.node != ia)\n\n& (uint32_t)(p.node != ic);\n\n}\n\nif (hits == 0)\n\nreturn true;The smallest of the three determinants is non-negative exactly when the point is inside the closed triangle. Only\nwhen the count is not zero does the exact loop from before run, to rule out dents that sit on a corner. The\nbucket version does the same with a bounding-box test, 64 points at a time into a bit mask. The total falls to\n, and the middle sizes gain the most: polygons with 33 to 256\nvertices go from 327 to 216 ms.
\nWhen the count is not zero, the exact loop reads all the dents again, although the first pass has already seen\nwhich ones were inside. The bucket version keeps that in its bit mask. The short list, up to 32 dents, can do the\nsame: the first pass sets one bit per hit instead of counting, and the exact test looks only at those dents:
\nhits |= ((uint32_t)(side >= 0) & (uint32_t)(p.node != ia)\n\n& (uint32_t)(p.node != ic)) << (i - begin);\n\n}\n\nwhile (hits) {\n\nconst Item &p = items[begin + lowestBit(hits)];\n\nhits &= hits - 1;\n\n// the exact test from before\n\n}Points read fall from 128 million to 120 million. This is the last step, and it is the code of earstrip as\npublished: , 6.0 times less than Delaunay on the same polygons.
\nMeisters' theorem is about simple polygons. Map data is rounded to a tile grid, and rounding can break a simple\npolygon. Here is the outline of Warszawa Śródmieście, a railway\nstation less than a kilometre from the blocks above, rounded to grids of different size. The orange rings mark\nvertices that land on the same point as their neighbour:
\nGrid step 73 cm. 68 of 154 vertices land on their neighbour. 84 triangles.
\nper tile side, the grid our map files use, a grid step is 18\ncm. Even there 31 of the 154 vertices merge with a neighbour, because mappers often place points a few centimetres\napart, and the outline survives. nearly\nhalf of the vertices merge, and the clipper still cuts it.\nthe rounded outline touches itself in a way that leaves no ear\nat all, and at 10 bits it happens to work again.
\nWhen the clipper walks all the way around the boundary without finding an ear, it drops the corners that have no\narea and walks once more. If that fails too, it gives up, and the engine triangulates that polygon with the\nDelaunay code, which still exists for this. In the Masovian data 76 polygons end up there. They come from a map\nbuilt before the last change on the other end: our map generator now rounds every polygon to the final grid with\nGEOS's snap rounding and checks that ear clipping can cut it. In a fresh build of the Masovian map that repaired 273\npolygons, and ear clipping can cut every polygon in the file.
\nDelaunay has one more job. Every hole needs its own bridge, and finding one scans the whole boundary, so a polygon\nwith thousands of holes pays for thousands of scans. Our world map has a polygon with 11,675 holes: ear clipping\ntakes 606 ms on it, Delaunay 17 ms. The engine now sends every polygon with 128 holes or more to Delaunay. In the\nMasovian data that is two polygons.
\nThe library keeps both of these fallbacks inside. earstrip covers a polygon with a constrained Delaunay\ntriangulation of its ring edges when the ears run out, when the triangles they leave cover the wrong area, and when\nit has more than 128 rings; run() in C++ and lastStatus() in JavaScript say which way a polygon went. On the\n56,472 polygons of our world map tiles, with up to 11,675 holes in one, earstrip takes 459 ms and earcut.hpp 2,892\nms. On the zoom 13 polygons that the ears can't cut exactly, earcut's triangles differ from an even-odd fill of the\nrings on 31% of the pixels on average, earstrip's on 0.15%.
Before the new clipper went into the app, I compared it with earcut, the ear\nclipper behind MapLibre and Mapbox GL, in its C++ version earcut.hpp 3.2.4. Natively the two are close, and that\ncould have been the end of it. But we are working on a web renderer that runs the same C++ engine compiled to\nWebAssembly, so I went further and compared the browser side too: both clippers compiled to WebAssembly, and\nearcut.js 3.2.4, the JavaScript original that web maps run today. For that I took the clipper out of the engine\ninto earstrip. On all 5.8 million polygons of our test sets it writes exactly the engine's strips, and its\nrepository has these polygons and the code behind every number in this section. Its native benchmark is the one\nbehind the chart above, and the native row below is the last step run against earcut.hpp. Every WebAssembly build gives exactly the same triangles as its native version on all 4.4\nmillion polygons of zoom levels 13 and 9. Milliseconds for the 3.74 million polygons of zoom 13, best of 7, one\nthread, V8 in Node and JavaScriptCore in Bun:
\n| earstrip | earcut | |
|---|---|---|
| Native C++ | 489 | 557 |
| WebAssembly, loop inside the module, V8 / JSC | 601 / 566 | 930 / 843 |
| WebAssembly, one call from JS per polygon, V8 / JSC | 688 / 688 | 1,007 / 950 |
| npm package, one call per polygon, V8 / JSC | 766 / 807 | 1,103 / 1,290 |
| npm package, direct calls, all polygons in one call, V8 / JSC | 635 / 619 |
Natively earcut.hpp is 14% slower than earstrip. Compiled to WebAssembly and run in V8, earstrip loses 23% and\nearcut.hpp loses 67%, almost all of it in its main loop that searches for ears. It isn't the allocator: builds with\nmimalloc and emmalloc give the same time. I haven't dug further. In V8, earcut.hpp in WebAssembly ends up only 19%\nfaster than plain earcut.js, and 10% once each polygon is a separate call from JavaScript.
\nThe package rows are what a web page gets, and the earcut column there is earcut.js. The call that replaces\nearcut takes the coordinates as JavaScript numbers and returns a new array of triangle indices every time: 1.4\ntimes as fast as earcut.js in V8 and 1.6 times in JavaScriptCore. About half of what it loses against the loop\ninside the module goes into copying the coordinates in and turning the strips into a list, the rest into calling\ninto WebAssembly once per polygon. The direct calls skip all of that: the\npolygons go straight into the module's memory and come back as one index buffer of strips for WebGL 2 or WebGPU,\n1.7 and 2.1 times as fast as earcut.js.
\nSome of the ideas above are in earcut too. It also relies on the fact that only a dent can block an ear, but it\nchecks that last, for every vertex that passes the bounding box and triangle tests, instead of keeping a list of\ndents. Above 80 vertices it links them in z-order and scans only the stretch of that curve the triangle's bounding\nbox covers, which does the job of the buckets. What it doesn't have are the shortcut for convex polygons, the strips\nand the count without branches: it writes three indices per triangle and stops at the first point inside.
\nearstrip is on GitHub and npm, with\nthe polygons from this post and the code to time it against earcut on your own machine.
","headings":[{"level":1,"text":"Faster than earcut: triangulating 3.7M map polygons in 489 ms","id":"faster-than-earcut-triangulating-3-7m-map-polygons-in-489-ms"},{"level":2,"text":"Delaunay","id":"delaunay"},{"level":2,"text":"Ears","id":"ears"},{"level":2,"text":"Holes","id":"holes"},{"level":2,"text":"The naive clipper (−1,812 ms)","id":"the-naive-clipper-1-812-ms"},{"level":2,"text":"Test only the dents (−237 ms)","id":"test-only-the-dents-237-ms"},{"level":2,"text":"Skip tests on convex polygons (−2 ms)","id":"skip-tests-on-convex-polygons-2-ms"},{"level":2,"text":"Write strips (−118 ms)","id":"write-strips-118-ms"},{"level":2,"text":"Sort the dents into buckets (−65 ms)","id":"sort-the-dents-into-buckets-65-ms"},{"level":2,"text":"Count without branches (−178 ms)","id":"count-without-branches-178-ms"},{"level":2,"text":"Test only the marked dents (−30 ms)","id":"test-only-the-marked-dents-30-ms"},{"level":2,"text":"When there are no ears","id":"when-there-are-no-ears"},{"level":2,"text":"In the browser","id":"in-the-browser"}]}}