Community hub
0 subscribers8 pages, 0 posts
Recent from talks
All channels
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Welcome to the community hub built to collect knowledge and have discussions related to Minimum bounding box.
Nothing was collected or created yet.
Minimum bounding box
View on Wikipediafrom Wikipedia
In geometry, the minimum bounding box or smallest bounding box (also known as the minimum enclosing box or smallest enclosing box) for a point set S in N dimensions is the box with the smallest measure (area, volume, or hypervolume in higher dimensions) within which all the points lie. When other kinds of measure are used, the minimum box is usually called accordingly, e.g., "minimum-perimeter bounding box".
The minimum bounding box of a point set is the same as the minimum bounding box of its convex hull, a fact which may be used heuristically to speed up computation.[1]
In the two-dimensional case it is called the minimum bounding rectangle.
Axis-aligned minimum bounding box
[edit]The axis-aligned minimum bounding box (or AABB) for a given point set is its minimum bounding box subject to the constraint that the edges of the box are parallel to the (Cartesian) coordinate axes. It is the Cartesian product of N intervals each of which is defined by the minimal and maximal value of the corresponding coordinate for the points in S.
Axis-aligned minimal bounding boxes are used as an approximate location of an object in question and as a very simple descriptor of its shape. For example, in computational geometry and its applications when it is required to find intersections in the set of objects, the initial check is the intersections between their MBBs. Since it is usually a much less expensive operation than the check of the actual intersection (because it only requires comparisons of coordinates), it allows quickly excluding checks of the pairs that are far apart.
Arbitrarily oriented minimum bounding box
[edit]The arbitrarily oriented minimum bounding box is the minimum bounding box, calculated subject to no constraints as to the orientation of the result. Minimum bounding box algorithms based on the rotating calipers method can be used to find the minimum-area or minimum-perimeter bounding box of a two-dimensional convex polygon in linear time, and of a three-dimensional point set in the time it takes to construct its convex hull followed by a linear-time computation.[1] A three-dimensional rotating calipers algorithm can find the minimum-volume arbitrarily-oriented bounding box of a three-dimensional point set in cubic time.[2] Matlab implementations of the latter as well as the optimal compromise between accuracy and CPU time are available.[3]
Object-oriented minimum bounding box
[edit]In the case where an object has its own local coordinate system, it can be useful to store a bounding box relative to these axes, which requires no transformation as the object's own transformation changes.
Digital image processing
[edit]In digital image processing, the bounding box is merely the coordinates of the rectangular border that fully encloses a digital image when it is placed over a page, a canvas, a screen or other similar bidimensional background.
See also
[edit]References
[edit]- ^ a b Toussaint, G. T. (1983). "Solving geometric problems with the rotating calipers" (PDF). Proc. MELECON '83, Athens.
- ^ Joseph O'Rourke (1985), "Finding minimal enclosing boxes", Parallel Programming, Springer Netherlands
- ^ Chang, Chia-Tche; Gorissen, Bastien; Melchior, Samuel (2018). "Matlab implementation of several minimum-volume bounding box algorithms". GitHub..
Minimum bounding box
View on Grokipediafrom Grokipedia
A minimum bounding box (MBB), also known as the smallest enclosing box, is the parallelepiped of minimal volume in three dimensions (or rectangle of minimal area in two dimensions) that fully contains a given set of points or the boundary of a geometric object, with the orientation of the box's edges chosen to achieve this minimality.[1] This construct is central to computational geometry, where it addresses the smallest enclosing box problem, often requiring algorithms that account for arbitrary rotations to optimize the fit.[1]
There are two primary variants: the axis-aligned minimum bounding box (AABB), which aligns with the coordinate axes and is computed simply from the extrema of the coordinates in each dimension, and the oriented minimum bounding box (OBB), which permits rotation and typically yields a tighter enclosure at the cost of increased computational complexity.[2][1] For instance, in three dimensions, an AABB is defined by the minimum and maximum values along the x, y, and z axes of the point set, forming a rectangular prism that may include empty space if the points are not axis-aligned.[3] Computing an exact OBB, however, often involves techniques like rotating calipers or convex hull analysis, with approximation algorithms achieving near-optimal results in linear time for large point sets.[1][4]
Minimum bounding boxes find extensive use across computer science and engineering fields due to their efficiency in representing spatial extents. In spatial databases and geographic information systems (GIS), MBBs serve as approximations for indexing and querying collections of objects, such as in R-trees where they enclose groups of features to enable fast range searches and overlap tests.[2][5] In computer graphics and robotics, OBBs support collision detection by simplifying intersection checks between complex shapes and accelerate rendering through hierarchical partitioning and culling of invisible elements.[1] Additionally, in manufacturing and rapid prototyping, MBBs optimize material usage and machining paths by determining the compactest enclosure for solid models.[3] In higher dimensions or for polytopes, extensions of these concepts enable efficient partitioning and approximation in data structures for multidimensional data analysis.[5]
This method ensures the box tightly bounds the point set without exceeding the extrema in any dimension.
The time complexity of this algorithm is , where is the number of points, as it requires a single scan with constant-time operations per point and dimension. This linear performance is optimal for static point sets, making AABBs suitable for one-time computations in scenarios like initial scene setup in graphics applications. For dynamic scenarios where points are added or removed incrementally, the extremes can be maintained and updated in amortized time per insertion by comparing the new point's coordinates against the current minima and maxima; removals are similarly efficient if the removed point is not an extreme, though recomputing from scratch may be necessary in the worst case if it is.
Special handling is required for edge cases to avoid undefined behavior. For an empty point set, the algorithm typically returns a null or invalid box, as no enclosing volume exists.[10] For a single point, the resulting box is degenerate with zero area (or volume in higher dimensions), where the minimum and maximum coordinates coincide at the point's location.[10]
In practice, AABB computation is implemented in established libraries for geometric processing. The CGAL library provides the
Fundamentals
Definition
In geometry, the minimum bounding box (MBB), also known as the smallest enclosing box, for a point set in -dimensional Euclidean space is defined as the hyperrectangle with the smallest Lebesgue measure—such as area in 2D or volume in 3D—that contains all points in .[6] This formal definition applies to finite sets of points, where the hyperrectangle is typically specified by its minimum and maximum coordinates along each dimension, adjusted to minimize the overall measure while ensuring containment.[7] The concept presupposes familiarity with Euclidean geometry and point sets, such as the vertices of a convex polygon in 2D (e.g., the four corners of a rectangle or an irregular quadrilateral) or a polyhedron in 3D (e.g., the eight vertices of a cube). In 2D, the MBB is a rectangle enclosing the points; in 3D, it is a rectangular cuboid. Unlike other bounding volumes, such as the minimum enclosing sphere—which is rotationally invariant—or the convex hull—which tightly wraps the points without rectangular constraints—the MBB is constrained to rectangular form, either axis-aligned with the coordinate axes or arbitrarily oriented.[6][8] The MBB has roots in cartography, where rectangular extents have long defined map boundaries, and was first formalized within computational geometry during the 1970s as the field emerged to address algorithmic problems on geometric data. Seminal developments in the 1980s, including rotating calipers techniques, further refined its theoretical foundations for efficient computation in 2D and 3D.[8][9]Properties
The minimum bounding box (MBB) for a point set in dimensions is defined by its optimality in terms of the smallest measure, typically the area in 2D or volume in higher dimensions, where the area is minimized as the product of width and height, and the volume as the product of the side lengths along each dimension.[7][1] This optimality ensures that the MBB encloses all points in while achieving the minimal spatial extent under the chosen measure.[7] Geometrically, the MBB is a convex polytope that fully contains , with its boundaries determined by the extreme points of —specifically, the minimum and maximum coordinates along the relevant axes—which guarantee tight containment without interior voids relative to the box.[7] For the axis-aligned case in 2D, this leads to the area equation , derived by identifying the bounding coordinates from the projections of points onto the x- and y-axes, yielding the width and height as differences between these extrema.[7] However, edge cases such as collinear points result in degenerate boxes with zero area or volume in one or more dimensions.[7] The MBB encloses the convex hull of , and in fact, the MBB of coincides with that of its convex hull, though the box sides may not be supported by hull edges in all directions, preventing it from being arbitrarily tight beyond the extreme projections.[7][1]Types
Axis-Aligned Minimum Bounding Box
The axis-aligned minimum bounding box (AABB), also known as an axis-aligned bounding box, is the smallest rectangular region in two dimensions or rectangular parallelepiped in three dimensions that encloses a given set of points, with all edges parallel to the coordinate axes.[10][11] In 2D, it is defined by the minimum and maximum x- and y-coordinates of the points, forming intervals .[10] This box is computed by scanning the point set once to determine these extrema in each dimension, requiring O(n) time for n points.[10][12] For example, consider the point set ; the AABB is , with width $3, height $2, and area $6\Delta x \cdot \Delta y\Delta x = x_{\max} - x_{\min}\Delta y$.[10] AABBs offer significant computational advantages due to their simplicity: no rotation or orientation adjustments are needed, making them ideal for grid-based spatial indexing and hierarchical structures.[10][12] Overlap tests between AABBs are efficient, involving only constant-time comparisons of interval bounds.[10] However, AABBs can be inefficient for objects that are rotated relative to the axes, as they may include substantial empty space; for instance, a diagonal line segment would yield a square AABB with corners unoccupied.[10] In three dimensions, the AABB extends naturally to , defined by the minima and maxima across all coordinates, with volume .[10][11] This representation remains computationally trivial while supporting efficient spatial queries, though it may enclose more volume than an oriented bounding box for non-axis-aligned geometries.[10]Oriented Minimum Bounding Box
The oriented minimum bounding box (OMBB), also referred to as an arbitrarily oriented or rotated bounding box, is defined as the smallest rectangular enclosure for a set of points in 2D or 3D space, where the box's edges are permitted to rotate freely relative to the coordinate axes to minimize the enclosed area (in 2D) or volume (in 3D).[13] Unlike axis-aligned variants, this rotation allows the box to better conform to the geometric distribution of the points, providing a tighter fit for non-axis-aligned shapes.[7] A fundamental property of the 2D OMBB for a convex polygon is that its optimal orientation aligns such that at least one side is collinear with an edge of the convex hull, as established by the rotating calipers theorem.[9] This theorem underpins efficient methods for identifying candidate orientations by considering only the hull's edges. For illustration, consider a unit square rotated by 45 degrees: its axis-aligned bounding box forms a larger square with side length √2 and area 2, whereas the OMBB aligns with the original square's sides, yielding the minimal area of 1. In general, the OMBB achieves a smaller area than its axis-aligned counterpart, with the worst-case ratio of axis-aligned to oriented area reaching 2 for certain convex shapes like the rotated square. In 3D, determining the exact OMBB is computationally more demanding due to the three rotational degrees of freedom, often parameterized via Euler angles or quaternions, which expand the search space compared to 2D.[14] A widely adopted approximation aligns the box axes with the principal components derived from the point set's covariance matrix via principal component analysis (PCA), which orients the box along the directions of maximum variance and provides a good heuristic for minimal volume, though it may not always yield the global optimum.[15] The axis-aligned minimum bounding box serves as a constrained special case of the OMBB with zero rotation.Object-Oriented Minimum Bounding Box
The object-oriented minimum bounding box (OOBB), also known as an object-aligned bounding box, is a variant of the oriented minimum bounding box where the box's axes are aligned with the intrinsic geometry of the object, such as its principal directions derived from statistical analysis of its shape. This orientation is typically obtained by computing the eigenvectors of the object's covariance matrix, which capture the directions of maximum variance in the point distribution, or by referencing structural features like symmetry lines.[16][17] Unlike fully arbitrary orientations, the OOBB prioritizes the object's natural coordinate system for alignment, providing a geometrically intuitive enclosure.[18] OOBBs are commonly applied to elongated or symmetric objects, such as vehicle models in simulation environments, where the box axes correspond to the object's primary dimensions like length, width, and height to achieve a compact fit.[19] For instance, in a 3D car model, the OOBB would orient along the vehicle's longitudinal axis (from front to rear), lateral axis (side to side), and vertical axis, minimizing the enclosed volume while respecting the model's inherent symmetry and reducing empty space around protrusions like wheels or mirrors.[16] This approach is particularly effective in scenarios involving rigid body dynamics or collision detection, where maintaining alignment with the object's local frame simplifies integration into larger scenes.[17] The computation of an OOBB often serves as an efficient approximation to the more general oriented minimum bounding box, relying on principal component analysis (PCA) applied to the object's vertices or point cloud to determine the principal axes.[18] Once the axes are established, the box extents are calculated by projecting the points onto these directions and taking the minimum and maximum coordinates, resulting in a tight bound without exhaustive search over all possible rotations.[16] Relative to methods seeking the absolute minimal volume through unconstrained optimization, OOBBs offer greater intuitiveness and stability, especially in hierarchical bounding volume structures for rendering or simulation pipelines, as they leverage the object's predefined geometry for consistent performance across transformations.[18][20] Nevertheless, generating an OOBB necessitates preprocessing steps like covariance matrix computation on the object's data, and it does not guarantee the globally smallest volume, potentially leaving more slack than optimal oriented boxes in irregular shapes.[17][18]Algorithms
Computing Axis-Aligned Boxes
The computation of an axis-aligned minimum bounding box (AABB) for a set of points in -dimensional space involves determining the minimum and maximum coordinates along each axis, forming a rectangular box aligned with the coordinate axes that encloses all points with minimal volume. This approach is foundational in computational geometry due to its straightforward implementation and efficiency. The basic algorithm performs a single linear pass over the points, initializing the minimum and maximum values for each dimension to extreme bounds (positive and negative infinity, respectively), and updating them iteratively as each point is processed. The following pseudocode illustrates the process for a 2D point set, which generalizes naturally to higher dimensions:function computeAABB(points):
if points is empty:
return null // or handle as degenerate case
min_x = min_y = +∞
max_x = max_y = -∞
for each point p in points:
min_x = min(min_x, p.x)
max_x = max(max_x, p.x)
min_y = min(min_y, p.y)
max_y = max(max_y, p.y)
return Box((min_x, min_y), (max_x, max_y))
function computeAABB(points):
if points is empty:
return null // or handle as degenerate case
min_x = min_y = +∞
max_x = max_y = -∞
for each point p in points:
min_x = min(min_x, p.x)
max_x = max(max_x, p.x)
min_y = min(min_y, p.y)
max_y = max(max_y, p.y)
return Box((min_x, min_y), (max_x, max_y))
bounding_box function for various geometric types, computing the axis-aligned extents efficiently during construction or query operations. Similarly, the Shapely library in Python offers the bounds attribute for geometries, which returns the (minx, miny, maxx, maxy) tuple representing the AABB, enabling quick extent determination for spatial analysis tasks such as in image processing.
Computing Oriented Boxes
Computing oriented minimum bounding boxes (OMBBs) involves optimizing the orientation to minimize the box's area or volume while enclosing a given set of points or a polygon. In two dimensions, the rotating calipers method provides an efficient solution for convex polygons. This approach first computes the convex hull of the input points in O(n log n) time using algorithms like Graham scan or Jarvis march, where n is the number of points. Then, it applies the rotating calipers technique in O(n) time to evaluate candidate orientations defined by the edges of the convex hull, selecting the one yielding the minimum area box.[7][12] The optimization can be formulated mathematically as minimizing the area function over the rotation angle \theta: where is the width, defined as the extent of the projected points onto the unit vector in direction \theta, and is the corresponding height onto the perpendicular direction \theta + \pi/2. The rotating calipers efficiently computes these projections by maintaining supporting lines that rotate synchronously around the hull, ensuring all antipodal edge pairs are considered without redundant evaluations.[7] The rotating calipers method was introduced by Godfried T. Toussaint in 1983 as a paradigm for solving geometric optimization problems, including the minimum-area enclosing rectangle.[21] One of the early extensions to three dimensions is Joseph O'Rourke's 1985 method, which achieves O(n^3) time complexity by enumerating orientations where at least two adjacent faces of the box align with edges of the convex hull, using a rotating calipers-like approach extended to polyhedral structures.[6] While this provides an exact solution, subsequent research has developed faster exact algorithms, including randomized methods with expected O(n) time complexity. Practical 3D computations often employ approximations for efficiency. Principal component analysis (PCA) aligns the box axes with the principal directions of the point cloud's covariance matrix, yielding an O(n) approximation after hull computation; this method provides a good fit for elongated or symmetric shapes but may deviate significantly from the optimum for irregular distributions.[22] For non-convex sets or when exactness is not required, heuristic techniques such as genetic algorithms evolve populations of rotation matrices to minimize volume, often hybridized with local optimizers like gradient descent for refinement.[23] In 2D and 3D, practical algorithms achieve near-linear or polynomial time, making them feasible for real-world applications.[24]Applications
In Computer Graphics
In computer graphics, minimum bounding boxes (MBBs) serve as fundamental bounding volumes to optimize rendering, collision detection, and scene management by enclosing complex geometries within simpler shapes. Axis-aligned bounding boxes (AABBs) and oriented bounding boxes (OBBs) are particularly prevalent, with AABBs favored for their computational efficiency in static scenes and OBBs preferred for tighter fits around rotated or irregular objects. These structures accelerate ray tracing by enabling quick intersection tests, reducing the need to evaluate intricate mesh details early in the rendering pipeline. A key application lies in bounding volume hierarchies (BVHs), where MBBs form the nodes of tree structures to cull non-visible or non-intersecting elements during ray traversal. For instance, in ray tracing, BVHs using AABBs or OBBs can achieve up to 10-100x speedups in intersection queries by first testing the bounding box before descending to child nodes, as demonstrated in early implementations for animated scenes. OBBs enhance this by aligning with object orientations, minimizing empty space and improving culling accuracy in dynamic environments like simulations. In collision detection, MBBs enable rapid reject tests to avoid expensive primitive-level computations; for OBBs, the separating axis theorem (SAT) projects the boxes onto potential separating axes to determine non-intersection in constant time for convex shapes. This is crucial in real-time applications, such as physics engines, where AABBs provide broad-phase filtering for speed, while OBBs offer precision for narrow-phase checks in scenarios involving articulated bodies. In game engines like Unity, MBBs are automatically generated to enclose imported meshes, facilitating efficient physics simulations and rigid body interactions without manual geometry adjustments. For level-of-detail (LOD) management and frustum culling, the size and position of an MBB determine whether an object enters the viewport, allowing distant or obscured elements to be rendered at lower fidelity or skipped entirely, which conserves GPU resources in large-scale scenes. Performance trade-offs highlight AABBs' simplicity for high-throughput tasks versus OBBs' overhead in dynamic scenes, where rotation updates can increase costs but yield better occlusion. This integration traces back to the 1990s, with AABBs and OBBs becoming standard in APIs like OpenGL and DirectX for hardware-accelerated rendering pipelines.In Digital Image Processing
In digital image processing, minimum bounding boxes (MBBs) are essential for localizing and isolating objects within 2D raster images after segmentation. For object detection, MBBs are computed around contours derived from segmented regions, such as those identified by thresholding or edge detection algorithms. In OpenCV, thefindContours function detects boundaries in binary images, followed by boundingRect to generate an axis-aligned MBB enclosing the contour points, providing coordinates (x, y, width, height) for precise localization. This approach enables efficient tracking of moving objects by combining background subtraction with contour-based bounding boxes.[25][26]
MBBs also facilitate feature extraction by defining tight enclosures around shapes in edge-detected images, allowing subsequent analysis of object properties like aspect ratio or centroid without processing the entire image. Edge detection techniques, such as Canny, identify boundaries, and contours from these edges yield MBBs that isolate features for tasks like shape classification. In practice, this reduces computational overhead by focusing on relevant regions, enhancing accuracy in applications requiring object boundary approximation.[27][25]
For cropping and alignment, MBBs automate the trimming of scanned documents or photos by enclosing detected content and applying perspective transforms. In document scanning pipelines, contours from edge-detected images are used to approximate the document boundary, with an MBB or quadrilateral fitting enabling warp-based alignment to correct skew and crop extraneous borders. This technique processes batches of scanned images efficiently, preserving content integrity while removing noise.[28]
A key application is in medical imaging, where MBBs isolate tumors from MRI slices to aid segmentation and diagnosis. For instance, YOLO-based object detection generates MBBs around glioblastomas in FLAIR-modality MRI, which are then used to mask predictions from U-Net models, improving Dice scores to 0.62 for rare tumors like diffuse intrinsic pontine glioma without retraining.[29] This localization step confines analysis to regions of interest, enhancing segmentation precision on datasets like BRaTS'19.
Common techniques involve thresholding an image to produce binary pixel sets, followed by contour detection and MBB computation. Axis-aligned bounding boxes (AABBs) are derived via boundingRect on contour points for quick, rotation-agnostic enclosures, ideal for aligned objects. For rotated elements like text in scanned documents, oriented MBBs minimize area using minAreaRect, which fits a rotated rectangle to the contour and outputs center, dimensions, and angle for alignment. These methods, rooted in early computer vision for character isolation in OCR, remain foundational in libraries like OpenCV.[25][30]