Globus, earcut'a rakip açık kaynaklı earstrip'i yayımladı: 3,7 milyon harita poligonunu 489 ms'de üçgenlere ayırıyor

Globus harita motorunun arkasındaki ekip, poligon üçgenleştirme kodunu earstrip adıyla, earcut'un da kullandığı ISC lisansıyla yayımladığı açık kaynak bir kütüphane olarak duyurdu. Tek bir C++ header dosyası ve npm üzerinde earcut ile aynı argümanları alan bir WebAssembly build'i olarak geliyor; bu da onu neredeyse doğrudan yerine geçebilen bir alternatif yapıyor. Hacker News'in ön sayfasına çıkan globus.software'deki mühendislik yazısına göre earstrip, C++'ta earcut.hpp'den yaklaşık %14, tarayıcıda ise earcut.js'den 1,4 ile 2,1 kat arası daha hızlı.

Benchmark

Öne çıkan rakamlar sentetik bir test paketinden değil, gerçek bir iş yükünden geliyor: Varşova çevresindeki bölge olan Mazovya Voyvodalığı'nın çevrimdışı haritasının 13. yakınlaştırma seviyesi, 3.740.425 poligon içeriyor. M4 Pro'nun tek bir çekirdeğinde, motondaki kısıtlı Delaunay üçgenleştirici hepsini kesmek için 2,93 saniyeye ihtiyaç duydu. Yazar, yerine geçecek ear clipper'ı fikir fikir yeniden inşa etti ve her commit'i aynı veri kümesiyle zamanladı; son sürüm işi 489 ms'de bitiriyor, yani genel olarak yaklaşık altı kat daha hızlı.

Kazanımın büyük kısmı harita verisinin kendisinin şeklinden geliyor. Poligonların neredeyse yarısı, 1,8 milyonu, dört veya daha az köşeye sahip: bir üçgenin kesilmesine gerek yoktur ve konveks bir dörtgen sadece iki üçgendir. Delaunay kodu yine de bu basit vakalara 419 ms harcadı, çünkü her üçgenleştirmeyi sıfırdan kurdu.

Ear clipping nasıl çalışır

Kulak, bir poligonun tek bir düz kesimle koparılabilecek köşesidir: ardışık üç köşe, ortadaki köşe konvekstir ve sınırın başka hiçbir parçası oluşturdukları üçgenin içine girmez. Gary Meisters'ın 1975'te kanıtladığı bir teorem, üçten fazla köşesi olan her basit poligonun çakışmayan en az iki kulağa sahip olduğunu garanti eder; böylece n köşe n - 2 üçgene dönüşene kadar kesilecek her zaman başka bir kulak vardır.

Her köşeyi ve ardından sınırın diğer her köşesini test eden ilk tam uygulama bile 1,12 saniyede çalıştı; Delaunay'den 2,6 kat daha hızlı. Sonraki her commit daha fazla zaman kazandırdı:

• sadece çukurlar: 882 ms
• konveks kestirme: 880 ms
• zigzag şeritler: 762 ms
• bucket'lar: 697 ms
• branch'sız: 519 ms
• işaretli isabetler: 489 ms

Delikler ve haritaya özgü tuhaflıklar

Ear clipping tek bir kapalı sınır üzerinde çalışır, ama Mazovya poligonlarının 11.345'i, örneğin binaların içindeki avlular ve ormanların içindeki açıklıklar gibi, deliklere sahip. Yazının David Eberly'nin algoritma anlatımına atfettiği çözüm, her deliği dış halkaya köprülemektir: deliğin en sağındaki köşeyi al, sağa bir ışın gönder, ışının çarptığı ilk kenarın bir köşesine bağlan ve aday köprü üçgeninin içinde hiçbir sınır noktası olmadığını doğrula.

Harita verisi, yazarın özel olarak ele alması gereken iki durum daha ekliyor. Koordinatlar tile grid üzerinde tam sayılar olduğundan grid çizgisi boyunca atılan bir ışın bozulur ve kesişim testinin ilk sürümü tam da bu durumu yanlış hesapladı. Haritacılar ayrıca sık sık dış halkaya tek bir noktadan değen bir avlu çizer; böyle bir deliğe hiç köprü gerekmez, çünkü iki halka zaten birleşiktir.

Delaunay'ın hâlâ kazandığı yerler

Ear clipping her yerde daha hızlı değil. 257 veya daha fazla köşeye sahip 1.123 en büyük poligonu kesmek 199 ms sürüyor ama Delaunay ile sadece 90 ms; çünkü her kulak testi yüzlerce köşeyi dolaşıyor ve bir poligon yüzlerce test gerektiriyor, maliyet boyutunun karesiyle büyüyor. Delaunay ayrıca en küçük açıyı maksimize ederek daha iyi şekilli üçgenler üretir; bu da mesh üzerinde enterpolasyon yapacaksanız veya üzerinde simülasyon çalıştıracaksanız önem taşır. Yazıya göre düz GPU dolguları için iğne gibi ince bir üçgen, geniş bir üçgen kadar doğru doldurulur.

Neden önemli

Harita motorlarından vektör grafiklerine ve geometri araçlarına kadar dolgulu poligon render eden herkesin üçgenleştirmeye ihtiyacı var ve earcut bu nişte varsayılan seçim. earstrip aynı API ve lisansı, hem yerel hem web platformlarında daha iyi benchmark rakamlarıyla sunuyor; yani denemesinin maliyeti sıfıra yakın. Yazı aynı zamanda bir optimizasyon vaka çalışması işlevi görüyor: doğru algoritmayı seçmek altı katlık kazanımın çoğunu sağladı, disiplinli, commit commit ayarlama ise kalan süreyi neredeyse yarıya indirdi. Çok büyük poligonların ağır bastığı iş yükleri her iki yaklaşımı da benchmark yapmalı, çünkü Delaunay orada hâlâ üstün.