rotating_calipers
Rotating calipers 1.0
Les étriers rotatifs sont le module Python implémentant un algorithme avec le même nom.
L'algorithme a été inventé pour la première fois par Michalel Shamos en 1978 et a gagné son nom "rotation des étriers" grâce à Godfried Toussant qui l'a présenté dans son article en 1983.
La méthode est ainsi nommée parce que l'idée est analogue à la rotation d'un étrier Vernier chargé à ressort autour de l'extérieur d'un polygone convexe. Chaque fois qu'une lame de l'étrier se trouve à plat sur un bord du polygone, il forme une paire antipodale avec le point ou le bord touchant la lame opposée. La «rotation» complète de l'étrier autour du polygone détecte toutes les paires antipodales; L'ensemble de toutes les paires, consultée comme un graphique, forme un barrackle. La méthode de rotation des étriers peut être interprétée comme le double projectif d'un algorithme de ligne de balayage dans lequel le balayage se fait à travers les pentes de lignes plutôt que dans les coordonnées x ou y de points.
Ci-dessus, la description a été adaptée de Wikipedia Page: https://en.wikipedia.org/wiki/Roting_Calipers
L'algorithme "Calipes rotatifs" a été mis en œuvre par moi pour un projet universitaire. Étonnamment, j'ai traversé beaucoup de difficulté à trouver une solution efficace à Python. C'est pourquoi je voulais le partager avec tous ceux qui ont besoin de l'implémentation rapide des "étriers rotatifs" dans Python.
Au fur et à mesure que les étriers rotatifs fonctionnent en temps linéaire, il a besoin d'une coque convexe sur l'entrée qui est calculée ici en utilisant l'algorithme de Graham qui s'exécute dans O (nlogn). Dans l'ensemble, l'algorihm (algorithme de Graham + les étriers rotatifs) est O (nlogn) + o (n) = o (nlogn)
Linux:
Un exemple d'utilisation peut être trouvé ici
