Calibradores giratorios

En geometría computacional , el método de los calibradores giratorios es una técnica de diseño de algoritmos que se puede utilizar para resolver problemas de optimización, incluido el cálculo del ancho o el diámetro de un conjunto de puntos.

El método recibe este nombre porque la idea es análoga a rotar un calibrador vernier con resorte alrededor del exterior de un polígono convexo . ^{[ 1 ]} Cada vez que una de las hojas del calibrador se apoya plana contra un borde del polígono, forma un par antipodal con la punta o el borde tocando la hoja 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 grafo, forma un thrackle . El método de rotación de calibradores puede interpretarse como el dual proyectivo de un algoritmo de barrido de línea en el que el barrido se realiza a través de pendientes de líneas en lugar de a través de coordenadas x o y de puntos.

El método de los calibradores giratorios se utilizó por primera vez en la disertación de Michael Shamos en 1978. ^{[ 2 ]} Shamos utilizó este método para generar todos los pares de puntos antipodales en un polígono convexo y para calcular el diámetro de un polígono convexo en${\displaystyle O(n)}$tiempo. Godfried Toussaint acuñó la frase "calibradores giratorios" y demostró que el método era aplicable para resolver muchos otros problemas de geometría computacional. ^{[ 3 ]}

Shamos dio el siguiente algoritmo en su disertación (págs.  77-82) para el método de los calibradores giratorios, que generó todos los pares antipodales de vértices en un polígono convexo: ^{[ 2 ]}

/* p[] está en forma estándar, es decir, en orden antihorario,  vértices distintos, sin vértices colineales.  ANGLE(m, n) es un procedimiento que devuelve el ángulo en sentido horario  barrido por un rayo al girar desde una posición paralela  al segmento dirigido Pm, Pm+1 hasta una posición paralela a Pn, Pn+1.  Suponemos que todos los índices se reducen a módulo N (de modo que N+1 = 1). */ GetAllAntiPodalPairs ( p [ 1. . n ]) // Encuentra el primer par antipodal localizando el vértice opuesto a P1 i = 1 j = 2 mientras angle ( i , j ) < pi j ++ yield i , j/* Ahora procedamos alrededor del polígono teniendo en cuenta los  posibles bordes paralelos. La línea L pasa por  Pi, Pi+1 y la línea M pasa por Pj, Pj+1  */// Bucle en j hasta que se haya escaneado todo P. corriente = i mientras j != n si ángulo ( corriente , i + 1 ) <= ángulo ( corriente , j + 1 ) j ++ corriente = j sino i ++ corriente = i generar i , j// Ahora, ocúpese de los bordes paralelos si ángulo ( actual , i + 1 ) = ángulo ( actual , j + 1 ) produce i + 1 , j produce i , j + 1 produce i + 1 , j + 1 si actual = i j ++ sino i ++

Otra versión de este algoritmo apareció en el texto de Preparata y Shamos en 1985 que evitaba el cálculo de ángulos: ^{[ 4 ]}

ObtenerTodosLosPasosAntipodales ( p [ 1. . n ]) i = n j = i + 1 mientras ( Área ( i , i + 1 , j + 1 ) > Área ( i , i + 1 , j )) j = j + 1 j0 = j mientras ( i != j0 ) i = i + 1 produce i , j mientras ( Área ( i , i + 1 , j + 1 ) > Área ( i , i + 1 , j )) j = j + 1 si (( i , j ) != ( j0 , 1 )) produce i , j si ( Área ( i , i + 1 , j + 1 ) = Área ( i , i + 1 , j )) si (( i , j ) != ( j0 , n )) produce i , j + 1

Pirzadeh ^{[ 5 ]} describe varias aplicaciones del método de los calibradores giratorios.

• Polígono convexo
• Envoltura convexa
• Caja de contención más pequeña