rotating_calipers
Rotating calipers 1.0
Los calibradores giratorios son el módulo de Python que implementa un algoritmo con el mismo nombre.
El algoritmo fue inventado por primera vez por Michalel Shamos en 1978 y ganó su nombre de "pinzas rotativas" gracias a Godfried Toussant, quien lo presentó en su artículo en 1983.
El método se llama así porque la idea es análoga a rotar un pinzas vernier cargadas de resorte alrededor del exterior de un polígono convexo. Cada vez que una cuchilla de la pinza se encuentra plana contra un borde del polígono, forma un par antipodal con el punto o el borde que toca la cuchilla opuesta. La "rotación" completa del calibrador alrededor del polígono detecta todos los pares antipodales; El conjunto de todos los pares, visto como un gráfico, forma un triunfo. El método de las pinzas giratorias puede interpretarse como el dual proyectivo de un algoritmo de línea de barrido en el que el barrido es a través de pendientes de líneas en lugar de a través de coordenadas de puntos X o Y.
La descripción anterior se adaptó de la página de Wikipedia: https://en.wikipedia.org/wiki/rotating_calipers
El algoritmo de "pinzas giratorias" fue implementado por mí para un proyecto universitario. Sorprendentemente, pasé por muchos problemas para encontrar una solución eficiente en Python. Es por eso que quería compartirlo con todos los que necesitan una implementación rápida de "pinzas giratorias" en Python.
Como las pinzas giratorias se ejecutan en tiempo lineal, necesita un casco convexo en la entrada WIHCH se calcula aquí usando el algoritmo de Graham que se ejecuta en O (NLOGN). Todo en todos los algorihm (algoritmo de Graham + calibradores giratorios) La complejidad del tiempo es O (nLogn) + o (n) = o (nLogn)
Linux:
El ejemplo de uso se puede encontrar aquí
