En geometría computacional , el método de calibradores giratorios es una técnica de diseño de algoritmos que se puede utilizar para resolver problemas de optimización, incluida la búsqueda del ancho o diámetro de un conjunto de puntos.
El método se llama así porque la idea es análoga a rotar un calibre vernier con resorte alrededor del exterior de un polígono convexo . [1] Cada vez que una hoja de la pinza descansa plana contra un borde del polígono, forma un par antípoda con la punta o el borde tocando la hoja opuesta. La "rotación" completa del calibre alrededor del polígono detecta todos los pares de antípodas; el conjunto de todos los pares, visto como un gráfico, forma una cadena . El método de los calibradores giratorios 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 pendientes de líneas en lugar de a través de x - o y-coordenadas de puntos.
Historia
El método de calibradores giratorios se utilizó por primera vez en la disertación de Michael Shamos en 1978. [2] Shamos utiliza 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 enhora. Godfried Toussaint acuñó la frase "calibradores giratorios" y también demostró que el método era aplicable para resolver muchos otros problemas de geometría computacional. [3]
Algoritmo de Shamos
Shamos dio el siguiente algoritmo en su disertación (págs. 77-82) para el método de calibradores rotativos que generaba todos los pares de vértices antípodas en un polígono convexo: [2]
/ * p [] está en forma estándar, es decir, en sentido contrario a las agujas del reloj, vértices distintos, sin vértices colineales. ANGLE (m, n) es un procedimiento que devuelve el ángulo en el sentido de las agujas del reloj barrido por un rayo cuando gira 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 son reducido a mod 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 proceda alrededor del 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 * / // Hacer 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 = yo cedo i , j // Ahora cuida los bordes paralelos si ángulo ( corriente , i + 1 ) = ángulo ( corriente , j + 1 ) rendimiento i + 1 , j rendimiento i , j + 1 rendimiento i + 1 , j + 1 si corriente = i j ++ más 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]
GetAllAntiPodalPairs ( p [ 1 .. N ]) i0 = n i = 1 j = i + 1 while ( Area ( i , i + 1 , j + 1 ) > Area ( i , i + 1 , j )) j = j + 1 j0 = j while ( j ! = I0 ) i = i + 1 produce i , j while ( Área ( i , i + 1 , j + 1 ) > Área ( i , i + 1 , j ) j = j + 1 si (( i , j ) ! = ( J0 , i0 )) da como resultado i , j en caso contrario devuelve si ( Area ( j , i + 1 , j + 1 ) = Area ( i , i + 1 , j )) if ( ( i , j ) ! = ( j0 , i0 )) rendimiento i , j + 1 de lo contrario, rendimiento i + 1 , j
Aplicaciones
Pirzadeh [5] describe varias aplicaciones del método de calibradores giratorios.
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]
- La tira 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 de tiras óptima (utilizada en imágenes médicas y modelado de sólidos) [14]
Cajas delimitadores
- Cuadro delimitador orientado al área mínima
- Cuadro delimitador orientado al perímetro mínimo
Triangulaciones
- Triangulaciones de cebolla
- Triangulaciones en espiral
- Cuadrangulación
- Bonita triangulación
- Problema de la galería de arte
- Problema de optimización de la ubicación de la cuña [15]
Operaciones de varios 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 soporte críticas de dos polígonos convexos
- Sumas vectoriales (o suma de Minkowski) de dos polígonos convexos [17]
- Casco convexo de dos polígonos convexos
Recorridos
Otros
- Reglas de decisión no paramétricas para la clasificación de aprendizaje automático [21]
- Optimizaciones del ángulo de apertura para problemas de visibilidad en la visión por computadora [22]
- Encontrar las células más largas en millones de células biológicas [23]
- Comparando la precisión de dos personas en el campo de tiro
- Clasifique secciones del cerebro a partir de imágenes escaneadas
Ver también
- Polígono convexo
- Casco convexo
- Caja envolvente más pequeña
Referencias
- ^ "Calibradores giratorios" en la página de inicio de Toussaint
- ↑ a b Shamos, Michael (1978). "Geometría computacional" (PDF) . Universidad de Yale. págs. 76–81.
- ^ Toussaint, Godfried T. (1983). "Resolver problemas geométricos con los calibradores giratorios". Proc. MELECON '83, Atenas. CiteSeerX 10.1.1.155.5671 . Cite journal requiere
|journal=
( ayuda ) - ^ Shamos, Franco P. Preparata, Michael Ian (1985). Introducción a la geometría computacional . Nueva York, NY: Springer New York. ISBN 978-1-4612-7010-2.
- ^ Pirzadeh, Hormoz (1999). "Geometría computacional con los calibradores giratorios" . Biblioteca McGill .
- ^ 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.
- ^ Binay K. Bhattacharya y Godfried T. Toussaint, "Un contraejemplo de un algoritmo de diámetro para polígonos convexos", Transacciones de IEEE sobre análisis de patrones e inteligencia de máquinas , vol. PAMI-4, No. 3, mayo de 1982, págs. 306-309.
- ^ Michael E. Houle y Godfried T. Toussaint, "Cálculo del ancho de un conjunto", Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas , vol. 10, no. 5, septiembre de 1988, págs. 761–765.
- ^ Godfried T. Toussaint y Jim A. McAlear, "Unalgoritmosimple O ( n log n ) para encontrar la distancia máxima entre dos conjuntos planos finitos", Cartas de reconocimiento de patrones , vol. 1, 1982, págs. 21-24.
- ^ Binay K. Bhattacharya y Godfried T. Toussaint, "Algoritmos eficientes para calcular la distancia máxima entre dos conjuntos planos finitos", Journal of Algorithms , vol. 14, 1983, págs. 121-136.
- ^ Godfried T. Toussaint y Binay K. Bhattacharya, "Algoritmos óptimos para calcular la distancia mínima entre dos conjuntos planos finitos", Pattern Recognition Letters , vol. 2, diciembre de 1983, págs. 79–82.
- ^ "Calibradores giratorios" . 2015-03-30. Archivado desde el original el 30 de marzo de 2015 . Consultado el 22 de marzo de 2017 .CS1 maint: bot: estado de URL original desconocido ( enlace )
- ^ 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 .
- ^ Barequet y Wolfers (1998). "Optimización de una tira que separa dos polígonos". Modelos gráficos y procesamiento de imágenes . 60 (3): 214-221. doi : 10.1006 / gmip.1998.0470 .
- ^ Teichmann, Marek (1989). "Problemas de optimización de la colocación de la cuña" . Cite journal requiere
|journal=
( ayuda ) - ^ Godfried T. Toussaint, "Un algoritmo lineal simple para intersecar polígonos convexos, The Visual Computer , Vol. 1, 1985, pp. 118-123".
- ^ Tomas Lozano-Perez, "Planificación espacial: un enfoque de espacio de configuración", IEEE Transactions on Computers , vol. 32, núm. 2, 1983, págs. 108-120.
- ^ Binay K. Bhattacharya y Godfried T. Toussaint, "Computación transversales más cortas", Computación , vol. 46, 1991, págs. 93-119.
- ^ Binay K. Bhattacharya, Jurek Czyzowicz, Peter Egyed, Ivan Stojmenovic, Godfried T. Toussaint y Jorje Urrutia, "Computación de transversales más cortas de conjuntos", Revista internacional de geometría computacional y aplicaciones , vol. 2, núm. 4, diciembre de 1992, págs. 417–436.
- ^ Jean-Marc Robert y Godfried T. Toussaint, "Aproximación lineal de objetos simples", Geometría computacional: teoría y aplicaciones , vol. 4, 1994, págs. 27–52.
- ^ Rasson y Granville (1996). "Herramientas geométricas en clasificación". Estadística computacional y análisis de datos . 23 (1): 105-123. doi : 10.1016 / S0167-9473 (96) 00024-2 .
- ^ Bose, P .; Hurtado-Díaz, F .; Omaña-Pulido, E .; Snoeyink, J .; Toussaint, GT (1 de agosto de 2002). "Algunos problemas de optimización del ángulo de apertura". Algoritmica . 33 (4): 411–435. CiteSeerX 10.1.1.16.7118 . doi : 10.1007 / s00453-001-0112-9 . ISSN 0178-4617 .
- ^ "Algoritmos de diámetro incorrectos para polígonos convexos" .