地図エンジンのポリゴン三角形分割ツールである earstrip を、earcut と同じ ISC ライセンスの小さなオープンソースライブラリとして公開しました。単一の C++ ヘッダーと、npm で公開されている WebAssembly ビルドで構成され、earcut と同じ引数を受け付けます。C++ では earcut.hpp より 14% 高速で、ブラウザでは earcut.js の 1.4～2.1 倍 の速さで動作します。
GPU が描画できるのは三角形だけですが、地図の大部分はポリゴンでできています。建物、公園、駐車場、路面電車の線路の間の芝生の帯などです。どのポリゴンを塗りつぶす前にも、その輪郭を三角形に分割する必要があります。ワルシャワ周辺のマゾフシェ県をカバーする当社のオフライン地図では、ズームレベル 13 で 3,740,425 個のポリゴン があります。M4 Pro の 1 コアで、当社エンジンの制約付きドロネー三角形分割ツールがそれらすべてを処理するのに 2.93 秒 かかりました。
今年 10 月、これを耳切り法に置き換えました。ドロネー三角形分割は細長い三角形を避け、補間やシミュレーションには有用ですが、平面の塗りつぶしにはそこまでの品質は必要なく、作業の大半は単純な形状に費やされていました。マゾフシェのポリゴンのほぼ半数、180 万個 は頂点が 4 つ以下ですが、ドロネーのコードはそれらの三角形分割をゼロから作るのに 419 ms を費やしていました。耳切り法は一度に 1 つの角を取り除き、頂点が 3 つを超えるすべての単純ポリゴンには、重なり合わない耳が少なくとも 2 つあるため、常に次に切れる箇所があります。
この作業を記録するため、耳切りの処理を 1 コミットにつき 1 つのアイデアずつ作り直し、同じ 370 万個のポリゴンで各段階の時間を計測しました。最終版は全データセットを 489 ms で処理します。これが見出しの数字です。
出典: Hacker News · 要約：HeadlinesBriefing