Minimum bounding box
Encyclopedia
The minimum or smallest bounding or enclosing box for a point set 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.
The term "box"/"hyperrectangle" comes from its usage in the Cartesian coordinate system
, where it is indeed visualized as a rectangle (two-dimensional case), rectangular parallelepiped (three-dimensional case), etc.
In the two-dimensional case it is called the minimum bounding rectangle
.
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 to 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 to quickly exclude from checks the pairs that are far apart.
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.(MZA)
Measure (mathematics)
In mathematical analysis, a measure on a set is a systematic way to assign to each suitable subset a number, intuitively interpreted as the size of the subset. In this sense, a measure is a generalization of the concepts of length, area, and volume...
(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
Convex hull
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
, a fact which may be used heuristically to speed up computation.
The term "box"/"hyperrectangle" comes from its usage in the Cartesian coordinate system
Cartesian coordinate system
A Cartesian coordinate system specifies each point uniquely in a plane by a pair of numerical coordinates, which are the signed distances from the point to two fixed perpendicular directed lines, measured in the same unit of length...
, where it is indeed visualized as a rectangle (two-dimensional case), rectangular parallelepiped (three-dimensional case), etc.
In the two-dimensional case it is called the minimum bounding rectangle
Minimum bounding rectangle
The minimum bounding rectangle , also known as bounding box or envelope, is an expression of the maximum extents of a 2-dimensional object within its 2-D coordinate system, in other words min, max, min, max...
.
Axis-aligned minimum bounding box
The axis-aligned minimum bounding box 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 simply the Cartesian productCartesian product
In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...
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 to an approximate location of an object in question and as a very simple descriptor of its shape. For example, in computational geometry
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
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 to quickly exclude from checks the pairs that are far apart.
In digital image processing
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
, the bounding box is merely the coordinates of the rectangular border that fully encloses a digital image
Digital image
A digital image is a numeric representation of a two-dimensional image. Depending on whether or not the image resolution is fixed, it may be of vector or raster type...
when it is placed over a page, a canvas, a screen or other similar bidimensional background.(MZA)