Globus' neuer Polygon-Triangulator schlägt earcut um das Doppelte
Faster than earcut: triangulating 3.7M map polygons in 489 ms
Globus Software hat den Polygon-Triangulator seiner Map-Engine als kleine C++-Header-Bibliothek namens earstrip unter der ISC-Lizenz veröffentlicht, dazu eine WebAssembly-Version auf npm, die dieselben Argumente wie earcut akzeptiert. In C++ ist earstrip 14 % schneller als earcut.hpp, im Browser 1,4- bis 2,1-mal so schnell wie earcut.js. Der Artikel erklärt, wie Ear-Clipping mit Optimierungen wie dem Test nur auf konkaven Ecken und dem Überspringen konvexer Polygone 3,7 Millionen Polygone in 489 ms trianguliert.
Fast die Hälfte der Masowischen Polygone, 1,8 Millionen, haben vier oder weniger Eckpunkte. Ein Dreieck braucht überhaupt keine Zerlegung und ein konvexes Viereck sind zwei Dreiecke, doch der Delaunay-Code verbringt 419 ms damit, für jedes eine Triangulation von Grund auf neu zu bauen.
- morishuz
großartig. die leistungsverbesserungen sehen beeindruckend aus!
ich bin der autor von Delaunay32, einem constrained delaunay triangulator mit polygon- und loch-unterstützung. er verwendet divide-and-conquer statt inkrementellem einfügen, also bin ich neugierig, wie er mit der delaunay-baseline hier abschneiden würde.
https://github.com/morishuz/delaunay32
ich habe noch nicht auf deinem korpus gebenchmarkt, und unsere aktuelle polygon-api erfordert einfache ringe mit sich nicht berührenden löchern. danke fürs veröffentlichen der datasets, sie sehen nützlich für tests und vergleiche aus!
- amelius
Sollte den allerwichtigsten Triangulator erwähnen:
- mistercow
Ich habe mich lange gefragt, warum sich ear clipping + Optimierungen bei der Triangulierung gegenüber Sachen wie Seidels trapezoidaler Methode durchgesetzt hat, die eine Zeitkomplexität von O(nlog*n) hat und Löcher auf natürliche Weise behandelt. Ich weiß, big-O ist nicht alles, aber das ist im Wesentlichen linear versus quadratisch, und es scheint, als ob wir uns um die Triangulierung immer komplexerer Polygone kümmern, je mehr Zeit vergeht.
Ist es nur eine Sache der Dreiecksqualität? Führt Seidel zu zu vielen schwer handhabbaren Slivers?
- mourner
Hey Evgen, hier der Earcut-Autor — danke für den Writeup und eine wirklich coole Bibliothek! Ich muss sehen, ob es irgendwelche Tricks gibt, die ich für die JS-Version von Earcut ausleihen kann. :)
Eine Sache, die ich anmerken sollte: Ich musste bewusst einige der potenziellen Optimierungen ablehnen, um die Bibliothek klein zu halten, damit die Bundle-Größe nicht explodiert — für die meisten praktischen Anwendungen (z. B. Mapbox GL JS) ist sie bereits schnell genug (und 4,1k min/gz). Neugierig, wie groß der WASM-Build von Earstrip ist.
Auf der C++-Seite verwendet Mapbox jetzt einen hybriden Ansatz, bei dem kleine Polygone mit earcut.hpp verarbeitet werden, während große und komplexe Polygone auf einen anderen Algorithmus basierend auf monotoner Zerlegung umschalten, denn obwohl er höhere Konstanten in der algorithmischen Komplexität hat, skaliert er viel besser mit der Eingabegröße.
- stymaar
Ich sehe, dass das Ergebnis viele sehr lange, sehr dünne Dreiecke enthält. Sind das nicht im Allgemeinen die schlechtesten Fälle für den GPU-Rasterizer?