En geometría , el cuadro delimitador o delimitador mínimo o 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 más altas) dentro de la cual se encuentran todos los puntos. Cuando se utilizan otros tipos de medidas, el cuadro mínimo se suele denominar 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]
El término "caja" / "hiperrectángulo" proviene de su uso en el sistema de coordenadas cartesianas , donde de hecho se visualiza como un rectángulo (caso bidimensional), paralelepípedo rectangular (caso tridimensional), etc.
En el caso bidimensional, se llama 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 de 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 para 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 verificación inicial son las intersecciones entre sus MBB. 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 excluir rápidamente las verificaciones de los pares que están muy separados.
Cuadro delimitador mínimo orientado arbitrariamente
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 bidimensional establecido en el tiempo que lleva construya su casco convexo seguido de un cálculo de tiempo lineal. [1] Un algoritmo de calibradores giratorios tridimensionales puede encontrar el cuadro delimitador de volumen mínimo orientado arbitrariamente de un conjunto de puntos tridimensionales en tiempo cúbico. [2] Están disponibles las 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 resultar útil almacenar un cuadro delimitador en relación con estos ejes, que no requiere transformación, ya que cambia la transformación del propio objeto.
Procesando imagen digital
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.
Ver también
Referencias
- ↑ a b Toussaint, G. T (1983). "Resolver problemas geométricos con los calibradores giratorios" (PDF) . Proc. MELECON '83, Atenas. Cite journal requiere
|journal=
( ayuda ) - ^ Joseph O'Rourke (1985), "Encontrar cajas de cierre mínimas", Programación paralela , Springer Países Bajos
- ^ Chang, Chia-Tche; Gorissen, Bastien; Melchior, Samuel (2018). "Implementación de Matlab de varios algoritmos de cuadro delimitador de volumen mínimo" ..