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 generalmente se denomina 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 casco convexo , un hecho que puede usarse heurísticamente para acelerar el cálculo. [1]
En el caso bidimensional se llama rectángulo delimitador mínimo .
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 sean 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 el eje se utilizan como 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 verificació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 propiamente dicha (porque sólo requiere comparaciones de coordenadas), permite excluir rápidamente las comprobaciones de los pares que están alejados.
El cuadro delimitador mínimo orientado arbitrariamente 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 giratorios se pueden utilizar para encontrar el cuadro delimitador de área mínima o perímetro mínimo de un polígono convexo bidimensional en tiempo lineal, y de un punto tridimensional establecido en el tiempo que lleva construya su casco convexo seguido de un cálculo en tiempo lineal. [1] Un algoritmo de calibradores giratorios tridimensionales puede encontrar el cuadro delimitador de volumen mínimo orientado arbitrariamente de un punto tridimensional establecido en tiempo cúbico. [2] Están disponibles implementaciones de Matlab de este último, así como el compromiso óptimo entre precisión y tiempo de CPU. [3]
En el caso de que un objeto tenga su propio sistema de coordenadas local , puede resultar útil almacenar un cuadro delimitador relativo a estos ejes, que no requiere transformación ya que la propia transformación del objeto cambia.
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.