Drei optimierte Algorithmen zur Berechnung der Kanten polygonaler Netze

Dieser Beitrag präsentiert drei äquivalente Algorithmen zur Berechnung der Kanten eines polygonalen Netzes, die progressive Optimierungsschritte darstellen, um dasselbe Ergebnis mit steigender Effizienz zu erzielen. Beginnend mit einer Beschreibung der Darstellung der Netztopologie und der Kantenkonzepte werden drei Ansätze detailliert beschrieben: ein map-basierter Algorithmus (Komplexität O(n log n)), ein sort-basierter Algorithmus (Komplexität O(n log n)) und ein neuartiger Algorithmus mit niedrigerer Valenz (Komplexität O(n)). Der Autor vergleicht deren Leistung und hebt den innovativen Charakter und die potenziellen Anwendungen im Spieleentwicklung des Algorithmus mit niedrigerer Valenz hervor.