Cuadro delimitador mínimo
En geometría , el cuadro delimitador mínimo o cuadro delimitador más pequeño (también conocido como cuadro delimitador mínimo o cuadro delimitador más pequeño ) para un conjunto de puntos S en N dimensiones es el cuadro con la medida más pequeña ( área , volumen o hipervolumen en dimensiones superiores) dentro del cual se encuentran todos los puntos. Cuando se utilizan otros tipos de medidas, el cuadro mínimo suele denominarse en consecuencia, por ejemplo, "cuadro delimitador de perímetro mínimo".
El cuadro delimitador mínimo de un conjunto de puntos es el mismo que el cuadro delimitador mínimo de su envoltura convexa , un hecho que puede utilizarse heurísticamente para acelerar el cálculo. [1]
En el caso bidimensional se denomina rectángulo delimitador mínimo .
Cuadro delimitador mínimo alineado con el eje
El cuadro delimitador mínimo alineado con el eje (o AABB ) para un conjunto de puntos dado es su cuadro delimitador mínimo sujeto a la restricción de que los bordes del cuadro son paralelos a los ejes de coordenadas (cartesianos). Es el producto cartesiano de N intervalos , cada uno de los cuales está definido por el valor mínimo y máximo de la coordenada correspondiente para los puntos en S.
Los cuadros delimitadores mínimos alineados con los ejes se utilizan como una ubicación aproximada de un objeto en cuestión y como un descriptor muy simple de su forma. Por ejemplo, en geometría computacional y sus aplicaciones, cuando se requiere encontrar intersecciones en el conjunto de objetos, la comprobación inicial son las intersecciones entre sus MBB. Dado que suele ser una operación mucho menos costosa que la comprobación de la intersección real (porque solo requiere comparaciones de coordenadas), permite excluir rápidamente las comprobaciones de los pares que están muy separados.
Cuadro delimitador mínimo orientado arbitrariamente
El cuadro delimitador mínimo de orientación arbitraria es el cuadro delimitador mínimo, calculado sin restricciones en cuanto a la orientación del resultado. Los algoritmos de cuadro delimitador mínimo basados en el método de calibradores rotatorios se pueden utilizar para encontrar el cuadro delimitador de área mínima o de perímetro mínimo de un polígono convexo bidimensional en tiempo lineal, y de un conjunto de puntos tridimensionales en el tiempo que lleva construir su envoltura convexa seguido de un cálculo en tiempo lineal. [1] Un algoritmo de calibradores rotatorios tridimensionales puede encontrar el cuadro delimitador de volumen mínimo de orientación arbitraria de un conjunto de puntos tridimensionales en tiempo cúbico. [2] Hay implementaciones de Matlab de este último, así como el compromiso óptimo entre precisión y tiempo de CPU. [3]
Cuadro delimitador mínimo orientado a objetos
En el caso de que un objeto tenga su propio sistema de coordenadas local , puede ser útil almacenar un cuadro delimitador relativo a estos ejes, que no requiere ninguna transformación a medida que cambia la propia transformación del objeto.
Procesamiento de imágenes digitales
En el procesamiento de imágenes digitales , el cuadro delimitador son simplemente las coordenadas del borde rectangular que encierra completamente una imagen digital cuando se coloca sobre una página, un lienzo, una pantalla u otro fondo bidimensional similar.
Véase también
Referencias
- ^ ab Toussaint, GT (1983). "Resolución de problemas geométricos con calibradores rotatorios" (PDF) . Proc. MELECON '83, Atenas.
- ^ Joseph O'Rourke (1985), "Encontrar cajas envolventes mínimas", Programación paralela , Springer Países Bajos
- ^ Chang, Chia-Tche; Gorissen, Bastien; Melchior, Samuel (2018). "Implementación en Matlab de varios algoritmos de caja delimitadora de volumen mínimo". GitHub ..
