Cuadro delimitador mínimo

En geometría , la caja delimitadora mínima ( o caja delimitadora más pequeña ) para un conjunto de puntos S en N dimensiones es la caja con la menor medida ( área , volumen o hipervolumen en dimensiones superiores) dentro de la cual se encuentran todos los puntos. Cuando se utilizan otros tipos de medidas, la caja mínima suele denominarse de acuerdo con ello, por ejemplo, "caja delimitadora 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 envolvente 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 .

La caja delimitadora mínima alineada con los ejes (o AABB ) para un conjunto de puntos dado es su caja delimitadora mínima sujeta a la restricción de que los bordes de la caja sean paralelos a los ejes de coordenadas (cartesianas). 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.

Las cajas delimitadoras mínimas alineadas con los ejes se utilizan para ubicar de forma aproximada un objeto y como una descripción muy simple de su forma. Por ejemplo, en geometría computacional y sus aplicaciones, cuando se requiere encontrar intersecciones en un conjunto de objetos, la verificación inicial consiste en las intersecciones entre sus cajas delimitadoras mínimas. Dado que suele ser una operación mucho menos costosa que la verificación de la intersección real (porque solo requiere comparaciones de coordenadas), permite descartar rápidamente las verificaciones de pares que están muy separados.

El cuadro delimitador mínimo con 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 giratorios pueden utilizarse 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 conjunto de puntos tridimensional en el tiempo que lleva construir su envolvente convexa seguido de un cálculo en tiempo lineal. ^{[ 1 ]} Un algoritmo de calibradores giratorios tridimensional puede encontrar el cuadro delimitador de volumen mínimo con orientación arbitraria de un conjunto de puntos tridimensional en tiempo cúbico. ^{[ 2 ]} Existen implementaciones en 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 ser útil almacenar un cuadro delimitador relativo a estos ejes, lo que no requiere ninguna transformación a medida que cambia la transformación del propio objeto.

En el procesamiento de imágenes digitales , el cuadro delimitador es 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.

• Esfera delimitadora
• Volumen delimitador
• Rectángulo delimitador mínimo
• Integral de Darboux