Trois algorithmes optimisés pour calculer les arêtes des maillages polygonaux

Cet article présente trois algorithmes équivalents pour calculer les arêtes d'un maillage polygonal, représentant des étapes d'optimisation progressive pour obtenir le même résultat avec une efficacité croissante. En commençant par une description de la représentation de la topologie du maillage et des concepts d'arêtes, il détaille trois approches : un algorithme basé sur une map (complexité O(n log n)), un algorithme basé sur le tri (complexité O(n log n)) et un nouvel algorithme de valence mineure (complexité O(n)). L'auteur compare leurs performances, soulignant la nature innovante et les applications potentielles dans le développement de jeux de l'algorithme de valence mineure.