earstrip 0.2.0

On npm: earstrip@0.2.0.

New

• A constrained Delaunay triangulation for the polygons the ears cannot cut: rings that cross or touch, a hole that cannot be joined to the boundary, and polygons with more than 128 rings. They come back as Status::Constrained ('constrained' in JavaScript), filled inside the outer ring by non-zero winding and outside every hole. On map polygons with broken rings the triangles differ from an even-odd fill of the rings on 0.15% of the pixels on average; earcut's on 31%.
• Direct JavaScript calls: direct.input() and direct.run() for one polygon, direct.batchInput() and direct.batch() for many. The polygon is written straight into the module's memory and the result is read there, as strips, a triangle list or one restart index buffer for WebGL 2 or WebGPU; nothing is copied or allocated per polygon.
• shrink(), in C++ and JavaScript, frees the buffers kept from the largest polygon.
• C++: setConstrained(), setExtraPoints() and extraPoints(). JavaScript: setConstrained(), and strips() returns the added points as points.

Changed

• Where rings cross, the constrained triangulation adds a point next to the crossing. In C++, strips() and triangles() can then hold index n + k (n input vertices) for point k of extraPoints(); setExtraPoints(false) keeps every index an input vertex. In JavaScript, earstrip(), batch(), direct.batch() and the direct 'triangles' never add points.
• Status has a new value, Constrained.
• The WebAssembly module grows from 56 to 68 KB, 21 to 27 KB with gzip.

Numbers

On 3.7 million map polygons earstrip is 13% faster than earcut.hpp in C++, 1.4 (V8) and 1.6 (JavaScriptCore) times faster than earcut.js through the earcut-compatible call, and 1.7 and 2.1 times through the direct calls; on polygons with thousands of holes, 6 to 7 times. The polygons are in the bench-data-1 release, and Checking the numbers has the command for every row.

Benchmark data 1

The polygons behind the numbers in the README. make data downloads them into data/ and checks them against data/SHA256SUMS; DATA.md describes the format.

File	Polygons	Packed	What
z13.bin	3,740,425	92 MB	zoom level 13 of GLMap's offline map of the Masovian Voivodeship, with the expected results
z9.bin	683,742	11 MB	the same map at zoom level 9, with the expected results
world.bin	56,472	8 MB	GLMap's world map tiles, up to 11,675 holes in one polygon
gom4old.bin	1,212,030	35 MB	an older build of the Masovian map with rings that cross or touch

Map data © OpenStreetMap contributors, available under the Open Database License 1.0. The ISC license of the code does not apply to these files.