Caixa delimitadora mínima
Na geometria, a caixa delimitadora mínima (em inglês "minimum bounding box", ou MBB) para um conjunto de pontos (S) em N dimensões é a caixa com a menor medida (área, volume, ou hipervolume em dimensões superiores) possível que englobe todos os pontos. Quando outros tipos de medida são utilizados, a caixa mínima é normalmente chamada pelo nome específico, por exemplo, "caixa delimitadora de perímetro mínimo".
A caixa delimitadora mínima de um conjunto de pontos é a mesma que a caixa delimitadora mínima de seu casco convexo, um fato que pode ser usado de forma heurística para acelerar a computação.[1]
O termo "caixa" / "hiperretângulo" vem do seu uso no sistema de coordenadas cartesiano, onde ela é de fato visualizada como um retângulo (caso bidimensional), paralelepípedo retangular (caso tridimensional), etc.
No caso bidimensional, a caixa também é chamada de retângulo delimitador mínimo.
Caixa mínima delimitadora de eixo alinhado[editar | editar código-fonte]
A caixa delimitadora mínima de eixo alinhado (em inglês "axis-aligned bounding box", ou AABB) para um certo conjunto de pontos é a caixa delimitadora mínima sujeita à restrição de que as bordas da caixa devem ser paralelas aos eixos de coordenadas cartesianos. É, simplesmente, o produto cartesiano de N intervalos, cada um dos quais é definido pelos valores mínimo e máximo das coordenadas correspondentes entre todos os pontos de S.
Caixas delimitadoras mínimas de eixo alinhado são utilizadas para definir a localização aproximada de um objeto, e também como uma forma muito simples de descrever sua forma. Por exemplo, em geometria computacional e suas aplicações, quando é necessário encontrar interseções no conjunto de objetos, a verificação inicial é por intersecções entre suas MBBs. Por ser geralmente uma operação menos dispendiosa do que a verificação da intersecção real (pois só requer comparações de coordenadas), permite excluir pares que estão muito distantes de verificações mais detalhadas.
Caixa delimitadora mínima arbitrariamente orientada[editar | editar código-fonte]
A caixa delimitadora mínima arbitrariamente orientada é a caixa mínima delimitadora calculada sem restrições com relação à orientação do resultado. Algoritmos de caixa delimitadora mínima baseados no método de "rotating calipers" (compassos rodando) podem ser usados para encontrar a caixa delimitadora de área ou perímetro mínimo de um polígono convexo bidimensional em tempo linear, e de um conjunto de pontos no tempo que leva para construir a sua envoltória convexa seguido por uma computação de tempo linear.[1] Um algoritmo de rotating calipers tridimensional pode encontrar a caixa delimitadora de volume mínimo arbitrariamente orientada de um conjunto de pontos tridimensional em tempo cúbico.[2]
Caixa delimitadora mínima orientada ao objeto[editar | editar código-fonte]
No caso em que um objeto tem seu próprio sistema de coordenadas local, pode ser útil armazenar uma caixa delimitadora em relação a estes eixos, pois não requer transformações conforme o próprio objeto é transformado.
Processamento digital de imagem[editar | editar código-fonte]
Em processamento digital de imagem, caixa delimitadora significa meramente as coordenadas da fronteira retangular que totalmente engloba uma imagem digital quando é colocada sobre uma página, uma tela ou outros fundos bidimensionais similares.
Referências[editar | editar código-fonte]
- ↑ a b «Solving Geometric Problems with the Rotating Calipers» (PDF)
- ↑ Joseph O'Rourke (1985), «Finding minimal enclosing boxes», Springer Netherlands, Parallel Programming