Calibradores giratorios

Secuencia de sondas alrededor de la envoltura convexa de un polígono para determinar su diámetro utilizando el método del calibrador rotatorio.

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

El método se llama así porque la idea es análoga a la rotación de un calibrador vernier con resorte alrededor del exterior de un polígono convexo . ^[1] Cada vez que una hoja del calibrador se apoya plana contra un borde del polígono, forma un par antípoda con la punta o borde tocando la hoja opuesta. La "rotación" completa del calibrador alrededor del polígono detecta todos los pares antípodas; el conjunto de todos los pares, visto como un gráfico, forma un thrackle . El método de rotación de calibradores se puede interpretar como el dual proyectivo de un algoritmo de línea de barrido en el que el barrido se realiza a través de las pendientes de las líneas en lugar de a través de las coordenadas x o y de los puntos.

Historia

Un par de vértices antípodas y sus líneas paralelas de apoyo .

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

Calibradores giratorios, búsqueda de un puente entre dos polígonos convexos

Algoritmo de Shamos

Shamos presentó el siguiente algoritmo en su disertación (pp. 77-82) para el método de calibradores rotatorios, que generaba todos los pares de vértices antípodas en un polígono convexo: ^[2]

/* p[] está en forma estándar, es decir, orden en sentido 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 a medida que rota desde una posición paralela  al segmento dirigido Pm,Pm+1 a 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 ubicando el vértice opuesto a P1 i = 1 j = 2 while angle ( i , j ) < pi j ++ yield i , j                 /* Ahora procede a recorrer el polígono teniendo en cuenta  los posibles bordes paralelos. La línea L pasa por  Pi, Pi+1 y M pasa por Pj, Pj+1  */ // Realizar un bucle en j hasta que se haya escaneado todo P current = i while j != n if angle ( current , i + 1 ) <= angle ( current , j + 1 ) j ++ current = j else i ++ current = i yield i , j                               // Ahora ocúpate de los bordes paralelos si ángulo ( corriente , i + 1 ) = ángulo ( corriente , j + 1 ) resulta i + 1 , j resulta i , j + 1 resulta i + 1 , j + 1 si corriente = i j ++ de lo contrario 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]

ObtenerTodosLosParesAntiPodales ( p [ 1 . . n ]) i0 = n i = 1 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 rendimiento i , j mientras ( Área ( i , i + 1 , j + 1 ) > Área ( i , i + 1 , j )) j = j + 1 si (( i , j ) != ( j0 , i0 )) rendimiento i , j de lo contrario devuelve si ( Área ( j , i + 1 , j + 1 ) = Área ( i , i + 1 , j )) si (( i , j ) != ( j0 , i0 )) rendimiento i , j + 1 de lo contrario rendimiento i + 1 , yo                                                                                                            

Aplicaciones

Pirzadeh ^[5] describe varias aplicaciones del método de calibradores rotatorios.

Distancias

• Diámetro (ancho máximo) de un polígono convexo ^{[6] [7]}
• Ancho (ancho mínimo) de un polígono convexo ^[8]
• Distancia máxima entre dos polígonos convexos ^{[9] [10]}
• Distancia mínima entre dos polígonos convexos ^{[11] [12]}
• Franja vacía (o de separación) más ancha entre dos polígonos convexos (una variante simplificada de baja dimensión de un problema que surge en el aprendizaje automático basado en máquinas de vectores de soporte )
• Distancia de Grenander entre dos polígonos convexos ^[13]
• Separación óptima de tiras (utilizada en imágenes médicas y modelado de sólidos) ^[14]

Cuadros delimitadores

• Cuadro delimitador orientado al área mínima
• Cuadro delimitador orientado al perímetro mínimo

Triangulaciones

• Triangulaciones de cebolla
• Triangulaciones espirales
• Cuadrangulación
• Bonita triangulación
• Problema de la galería de arte
• Problema de optimización de la colocación de cuñas ^[15]

Operaciones con múltiples polígonos

• Unión de dos polígonos convexos
• Tangentes comunes a dos polígonos convexos
• Intersección de dos polígonos convexos ^[16]
• Líneas de apoyo críticas de dos polígonos convexos
• Sumas vectoriales (o suma de Minkowski) de dos polígonos convexos ^[17]
• Envolvente convexa de dos polígonos convexos

Travesías

• Transversales más cortas ^{[18] [19]}
• Transversales de tiras más delgadas ^[20]

Otros

• Reglas de decisión no paramétricas para la clasificación con aprendizaje automático ^[21]
• Optimizaciones del ángulo de apertura para problemas de visibilidad en visión artificial ^[22]
• Encontrar las células más largas entre millones de células biológicas ^[23]
• Comparación de la precisión de dos personas en un campo de tiro
• Clasificar secciones del cerebro a partir de imágenes escaneadas

Véase también

• Polígono convexo
• Casco convexo
• La caja de cierre más pequeña

Referencias

1. "Calibradores giratorios" en la página de inicio de Toussaint
2. Shamos, Michael (1978). "Geometría computacional" (PDF) . Universidad de Yale. págs. 76–81.
3. Toussaint, Godfried T. (1983). "Resolución de problemas geométricos con calibradores rotatorios". En Protonotarios, EN; Stassinopoulos, GI; Civalleri, PP (eds.). Actas de MELECON '83, Conferencia Electrotécnica Mediterránea, Atenas, Grecia, 24-26 de mayo de 1983. IEEE. págs. A10.02/1–4. CiteSeerX 10.1.1.155.5671 . 
4. Shamos, Franco P. Preparata, Michael Ian (1985). Geometría computacional Una introducción . Nueva York, Nueva York: Springer Nueva York. ISBN 978-1-4612-7010-2.{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
5. Pirzadeh, Hormoz (1999). Geometría computacional con calibradores rotatorios (tesis de maestría). Universidad McGill.
6. Binay K. Bhattacharya y Godfried T. Toussaint, "Algoritmos rápidos para calcular el diámetro de un conjunto plano finito", The Visual Computer , vol. 3, núm. 6, mayo de 1988, págs. 379-388.
7. Binay K. Bhattacharya y Godfried T. Toussaint, "Un contraejemplo de un algoritmo de diámetro para polígonos convexos", IEEE Transactions on Pattern Analysis and Machine Intelligence , Vol. PAMI-4, No. 3, mayo de 1982, págs. 306–309.
8. Michael E. Houle y Godfried T. Toussaint, "Cálculo del ancho de un conjunto", IEEE Transactions on Pattern Analysis & Machine Intelligence , vol. 10, núm. 5, septiembre de 1988, págs. 761–765.
9. Godfried T. Toussaint y Jim A. McAlear, "Un algoritmo simple O( n log n ) para encontrar la distancia máxima entre dos conjuntos planares finitos", Pattern Recognition Letters , Vol. 1, 1982, págs. 21–24.
10. Binay K. Bhattacharya y Godfried T. Toussaint, "Algoritmos eficientes para calcular la distancia máxima entre dos conjuntos planares finitos", Journal of Algorithms , vol. 14, 1983, págs. 121-136.
11. Godfried T. Toussaint y Binay K. Bhattacharya, "Algoritmos óptimos para calcular la distancia mínima entre dos conjuntos planares finitos", Pattern Recognition Letters , vol. 2, diciembre de 1983, págs. 79-82.
12. "Calibradores giratorios". 30 de marzo de 2015. Archivado desde el original el 30 de marzo de 2015. Consultado el 22 de marzo de 2017 .{{cite web}}: CS1 maint: bot: estado de URL original desconocido ( enlace )
13. MARTINEZ, HUGO M. (1 de enero de 1978). "Revisión de: "PATTERN SYNTHESIS", por U. Grenander, Springer-Verlag, Nueva York, 1976. 509 pp". Revista Internacional de Sistemas Generales . 4 (2): 126–127. doi :10.1080/03081077808960672. ISSN  0308-1079.
14. Barequet y Wolfers (1998). "Optimización de una franja que separa dos polígonos". Modelos gráficos y procesamiento de imágenes . 60 (3): 214–221. doi : 10.1006/gmip.1998.0470 .
15. Teichmann, Marek (1989). Problemas de optimización de la colocación de cuñas (tesis de maestría). Universidad McGill.
16. Godfried T. Toussaint, "Un algoritmo lineal simple para la intersección de polígonos convexos", The Visual Computer , vol. 1, 1985, págs. 118-123.
17. Tomas Lozano-Pérez, "Planificación espacial: Un enfoque de espacio de configuración", IEEE Transactions on Computers , Vol. 32, No. 2, 1983, pp. 108–120.
18. Binay K. Bhattacharya y Godfried T. Toussaint, "Cálculo de transversales más cortas", Computing , vol. 46, 1991, págs. 93-119.
19. Binay K. Bhattacharya, Jurek Czyzowicz, Peter Egyed, Ivan Stojmenovic, Godfried T. Toussaint y Jorje Urrutia, "Cálculo de las transversales más cortas de conjuntos", International Journal of Computational Geometry and Applications , vol. 2, núm. 4, diciembre de 1992, págs. 417–436.
20. Jean-Marc Robert y Godfried T. Toussaint, "Aproximación lineal de objetos simples", Computational Geometry: Theory and Applications , Vol. 4, 1994, págs. 27–52.
21. Rasson y Granville (1996). "Herramientas geométricas en la clasificación". Computational Statistics & Data Analysis . 23 (1): 105–123. doi :10.1016/S0167-9473(96)00024-2.
22. Bose, P.; Hurtado-Diaz, F.; Omaña-Pulido, E.; Snoeyink, J.; Toussaint, GT (1 de agosto de 2002). "Algunos problemas de optimización del ángulo de apertura". Algorithmica . 33 (4): 411–435. CiteSeerX 10.1.1.16.7118 . doi :10.1007/s00453-001-0112-9. ISSN  0178-4617. S2CID  27455160. 
23. "Algoritmos de diámetro incorrectos para polígonos convexos".