earstrip: triangulasi 3,7 juta poligon peta dalam 489 ms
Judul asli: Faster than earcut: triangulating 3.7M map polygons in 489 ms
Mengapa Ini Penting
Rendering peta real-time bergantung pada kecepatan triangulasi; earstrip menawarkan alternatif OSS yang terukur.
Globus Software merilis earstrip, library C++ header tunggal berlisensi ISC, yang mampu triangulasi 3,74 juta poligon peta 14% lebih cepat dari earcut.hpp dan hingga 2,1x lebih cepat di browser.
Evgen Bodunov, CEO Globus Software, mengumumkan perilisan earstrip — triangulator poligon dari engine peta mereka — sebagai library open source berlisensi ISC. Library ini hadir dalam satu file header C++ dan build WebAssembly di npm dengan antarmuka argumen yang identik dengan earcut.js.
Latar belakangnya konkret: GPU hanya bisa mengisi segitiga, bukan poligon. Peta penuh poligon — gedung, taman, jalur rumput di antara rel trem. Zoom level 13 peta offline Masovian Voivodeship (kawasan sekitar Warsawa) saja memuat 3.740.425 poligon. Triangulator Delaunay lama engine mereka membutuhkan 2,93 detik pada satu core M4 Pro.
Bodunov mengganti pendekatan Constrained Delaunay dengan ear clipping. Metode Delaunay memang menghasilkan segitiga dengan sudut terbesar yang optimal — berguna untuk simulasi atau interpolasi — tetapi tidak relevan untuk fill warna datar di GPU. Hampir separuh poligon Masovian, sekitar 1,8 juta, hanya memiliki empat vertex atau kurang; Delaunay menghabiskan 419 ms hanya untuk kasus-kasus sederhana ini.
earstrip menyelesaikan seluruh 3,7 juta poligon dalam 489 ms pada hardware yang sama. Di browser, kecepatannya 1,4 hingga 2,1 kali lebih cepat dibanding earcut.js. Setiap optimasi dikembangkan satu commit sekaligus, diukur langsung pada dataset Masovian yang sama.