地図のレンダリングにおいて、建物、公園、道路などの複雑な形状は、頂点の閉じた輪郭であるポリゴンとして保存されます。しかし、Graphics Processing Units（GPU）は任意のポリゴンではなく、三角形を塗りつぶすように設計されています。このギャップを埋めるために、すべてのポリゴンは「三角形分割」され、一連の三角形に切り分けられる必要があります。このタスクにはいくつかのアルゴリズムが存在しますが、GLOBUSの地図エンジン開発チームは、以前使用していた制約付きDelaunay三角形分割法が大規模なデータに対して非効率であることを発見しました。具体的には、ワルシャワの特定の地域から抽出した370万個のポリゴンを処理するのに、シングルコアで約3秒かかっていました。彼らはこのボトルネックを解消するため、「ear-clipping」法への切り替えを試みました。

Ear-clippingは、「耳（ear）」を特定することで機能します。これはポリゴンの凸の角であり、その2つの隣接する頂点間の線が形状の他の部分と交差しない場所を指します。これらの「耳」を繰り返し「切り取る」ことで、ポリゴンは最終的に一連の三角形へと分解されます。GLOBUSチームは、このプロセスを洗練させるために「earstrip」を開発しました。彼らは、アルゴリズム内で最も頻繁に行われる操作である「is-ear」テストの計算コストを削減するために、いくつかの最適化を実装しました。主な改善点には、探索範囲を狭めるための「くぼみ（凹角）」の特定、すでに凸であるポリゴンのテストスキップ、および「バケット」システムを使用して凹角を空間的にソートする手法が含まれます。これらの洗練により、同じ370万個のポリゴンをわずか489ミリ秒で処理することが可能になり、Delaunay法と比較して大幅な高速化を実現しました。

純粋な速度だけでなく、チームはGPUの効率を向上させるために、生成された三角形の保存方法も最適化しました。ポリゴン内の凸環を特定することで、GPUが前の三角形から2つの頂点を再利用して次の三角形を形成する「triangle strips」を生成することが可能になりました。これにより、テストセットで生成された2,150万個の三角形に必要なインデックスの総数が削減されました。Ear-clipping法はほとんどの地図ポリゴンにおいて高速ですが、チームはトレードオフについても言及しています。非常に大きく複雑なポリゴン（257頂点以上）の場合、Ear-clippingの計算量はポリゴンサイズの2乗で増加するため、Delaunay法の方が依然としてわずかに高速です。それにもかかわらず、「earstrip」は一般的な地図レンダリングタスクに対して、高性能でライセンスに優しい代替手段を提供します。