by Dan Sunday

It is often useful to have a bounding container (BC), such as a bounding box or sphere, enclosing a finite geometric object. BCs can significantly speed up software for ray tracing, collision avoidance, hidden object detection, etc. Before invoking a computationally expensive intersection or containment algorithms for a complicated object, a simple test with an uncomplicated bounding container can often exclude the possibility of intersection or containment, and no further wasteful computation is needed. If a point is outside the bounding container, then it is also outside the object inside the container. If two bounding containers are disjoint, then so are the objects they contain, and thus they cannot intersect. The usefulness of such containers is sometimes only given passing mention as an obvious preprocessing test to make before attempting other algorithms. However, there are a number of different choices for bounding containers that a programmer should be familiar with.

We will restrict attention to finite linear objects, such as points, segments, triangles, polygons, and polyhedra. These objects, and collections of them, are specified by linear combinations of their vertices, and their complexity can be measured by the total number n of vertices they have. All containers we discuss can be computed directly from the set of vertices, and so we just have to consider algorithms for sets of points. Important characteristics of a good bounding container are:

 Criteria How-to-Achieve If the BC contains the vertices of a linear  object, then it must also contain the whole object. The BC should be convex.  That is, if two points are inside the BC,  then the line segment joining them is also inside the BC. It is easy to test that:1) a point is outside the BC,2) two BC's are disjoint, and3) a line or ray intersects the BC. Have a small number of easy-to-compute inequalities to test inclusion of a  point in the BC. The geometric object is closely  approximated by the BC. Minimize the area or volume of the BC. It is efficient to compute and store the BC. Aim for time, or better, and a small constant space. Bottom Line: Get a significant improvement in runtime speed. Expect a large runtime speed-up in return for extra BC preprocessing time.

We consider two basic types of BC's: linear containers (such as rectangular boxes and convex polygons), and quadratic containers (such as spheres or ellipses). Example of different containers for the same object, a polygon, are shown in the diagram:

## Linear Containers

A linear container is one whose interior is specified by a finite number of linear inequalities. This implies that a bounded linear container is either a convex polygon (2D) or a convex polyhedron (3D). For example, in 2D, a container C could be specified by k inequalities: , all of which would have to be true for a point (x,y) to be in the region. If any one of the inequalities failed, then the test point would be outside C. So, when a point is outside C, this can be discovered on average by testing half of the inequalities. Also, each inequality defines a half-space Hi bounded by the line Li: . The region C is the intersection of all these half-spaces, and this implies that it is convex. When bounded, C is a convex polygon with segments of the lines Li as edges.

Similarly in 3D, k linear inequalities: , specify a linear container D. Each inequality defines a half-space Hi bounded by a plane Pi. The region inside D is now a 3D convex polyhedron with convex polygons Ci (contained in the planes Pi) as faces.

### The Bounding Box

A "box" is a rectangular region whose edges are parallel to the coordinate axes, and is thus defined by its maximum and minimum extents for all axes. So, a 2D box is given by all (x,y) coordinates satisfying and , and is specified by the extreme points and , which are its bottom-left and top-right corners. Similarly, a 3D box is specified by it’s extreme corners and . Inclusion of a point in a box is tested by verifying that all inequalities are true; and if any one of them fails, then the point is outside the box. In 2D there are four (4) inequalities, and in 3D there are six (6). So, on the average, an outside point will be rejected after 2 tests in 2D and 3 tests in 3D. Further, one can test whether two boxes B1 and B2 are disjoint by comparing their minimum and maximum extents. With respect to the x-axis, if either or , then B1 and B2 are disjoint. There are equivalent disjointness tests with respect to the y-axis and z-axis. If any one of these tests is true, then B1 and B2 are disjoint. If all of them are false, then the two boxes intersect, and more tests are needed to find out if objects inside the two boxes also intersect.

The "bounding box" of a finite geometric object is the box with minimal area (in 2D), or minimal volume (in 3D or higher dimensions), that contains a given geometric object. For any collection of linear objects (points, segments, polygons, and polyhedra), their bounding box is given by the minimum and maximum coordinate values for the point set S of all the object’s n vertices. These values are easily computed in time with a single scan of all the vertex points, sometimes while the object's vertices are being read or computed.

The bounding box is the computationally simplest of all linear bounding containers, and the one most frequently used in many applications. At runtime, the inequalities do not involve any arithmetic, and only compare raw coordinates with the precomputed min and max constants.

### The Bounding Diamond

When one introduces some arithmetic, the simplest nontrivial expressions are those that just add and subtract raw coordinates. In 2D, we have the expressions and , which correspond to lines with slopes of (–1) and 1. For a 2D set S of points, we can compute the minimum and maximum over S of each of these two expressions to get pmin, pmax, qmin, qmax. Then, the "bounding diamond" D for the set S is the region given by coordinates satisfying the inequalities: and . Geometrically, it is a rectangle rotated by 45° and resembles a diamond.

The bounding diamond involves a small bit more computation than the bounding box, and a priori they are equivalent approximations of the sets they contain. However, after computing them both, one may be found to be better than the other. All the minimums and maximums involved (8 of them) can be computed in time with a single scan of the set S. Then the areas of the bounding box B and the bounding diamond D can be compared, and the smaller container can be used if one wants. Since everything is rectangular, we have:

Further, one could use both containers, the box and the diamond, to get an even smaller combined “bounding octagon” defined by all 8 inequalities together. In fact, this is probably the preferred usage. If one wants to test a point for inclusion in a polygon , the only overhead is computing the expressions and just before testing the diamond inequalities after P was found to be inside the bounding box. To test disjointness of two polygons, no further expressions need to be evaluated since one only has to test the opposing parallel max and min extremes of the bounding octagon.

In 3D, one can also use the max and min of the four expressions (x ±  y ± z) to get 8 inequalities that define a 3D “bounding octahedron”. Specifically, the inequalities are:

If the coordinates of a point fail to satisfy any of these, then P is outside the bounding octahedron. Also, two bounding octahedrons are disjoint if the max of an expression for one is less than the min of the same expression for the other. This gives 8 inequalities to test for disjointness.

One could further combine the 8 octahedron inequalities with the 6 inequalities for the 3D bounding box, and get a set of 14 inequalities which give a 3D “bounding cuboctahedron”. Whether it is efficient to test this many inequalities depends on the complexity of the geometric object inside the bounding container.

It should be noted though, that in d-dimensions with coordinates , the d-D bounding box is given by 2d inequalities. But, the d-D bounding octahedron is given by 2d inequalities with 2d–1 defining expressions . Thus, the (cube)octahedron box method does not generalize efficiently to high dimensions.

### The Convex Hull

The "convex hull" H of a point set S is the smallest convex region containing the points. Any other convex container for S must contain the convex hull H as a subset. This means that the convex hull is the bounding container that is the smallest and least area approximation for the object it contains. It is easy to show that H is a bounded polygon in 2D or a polyhedron in 3D with vertices from a finite set S. A good way to visualize the 2D convex hull is to imagine that the points of S are pegs stuck in a plane (or nails in a piece of wood), and that H is formed by an elastic band stretched around the outside of all the pegs. The band contracts to enclose the peg set as tightly as possible. This is the boundary of the convex hull. Each edge of the hull’s boundary is a line segment that can be expressed as an implicit linear equation, and the half space containing the hull is given by an inequality: in 2D or in 3D, where are floating point numbers. The region inside the hull is defined by the collection of all these inequalities. For example:

The downside of using the convex hull as a container is that it may have a lot of edges (in 2D) or faces (in 3D), and to check for the inclusion of a point in the hull by testing many independent inequalities takes a lot of computation. However, there are fast methods to test for inclusion of a point in a 2D convex polygon (see Algorithm 3 about Inclusion of a Point in a Convex or Monotone Polygon). Further, it is not straightforward to test that two different noncongruent convex hulls are disjoint. This is because the hulls do not have consistent opposed parallel faces which can be tested for separation. So, although the convex hull gives a lower bound for how small a bounding container can be, it is not usually useful for non-intersection testing.

We will not pursue this topic further here, and will return to convex hulls some other time. We just note that there are many algorithms for computing the convex hull in 2D, 3D, and higher dimensions. The fastest algorithms run in time for the 2D or 3D hull of a set of n points. Many of these algorithms are described by [Preparata & Shamos, 1985, Chaps 3 & 4 ] and [O'Rourke, 1998, Chaps 3 & 4] both of whom have two whole chapters on computing convex hulls. O'Rourke also gives explicit C code (on his web site) for computing both the 2D and 3D convex hull for a set of points.

### The Minimal Rectangle

However, it is useful to find minimal area bounding containers which only involve the evaluation of a few expressions to test for inclusion. The minimal bounding rectangle is such a container. It is the minimum area (or volume in 3D) rectangle (or “minimal bounding cuboid” in 3D), with an arbitrary orientation, that contains the vertex set S of a geometric object. In 2D, it has two pairs of parallel edges, given by the max and min over S of two linear expressions and . In 3D, there are three expressions with , defining 3 pairs of parallel planar faces. Without the restriction of rectangularity, one could define the minimal bounding parallelogram (or “parallelopied” in 3D) which could have an even smaller area than the minimal rectangular box. For such parallelotope regions, it is relatively easy to determine the inclusion of a point . In 2D, the inequality tests are:

Again, if any one inequality fails, then the point is outside the rectangle or parallelogram. Although the more general parallelogram would be a useful container, most work in computational geometry has focused on algorithms for finding the minimal rectangle. This is partly because these algorithms are slightly more efficient.

In 2D, there is a well-known algorithm for finding the minimum rectangle using a technique referred to as the "rotating calipers" ([Toussaint, 1983], [Pirzadeh, 1999]). This technique applies to a convex polygon, and can find the minimal rectangle in time. For a nonconvex object, one must first compute its convex hull, which can be done in time. The caliper method depends on the observation that (in 2D) one side of the minimal rectangle must coincide with one edge of the convex polygon it must contain [Freeman & Shapira, 1975], as shown in the diagram:

Thus, one only has to consider the orientations given by edges of the convex polygon. Further, there is an efficient method to determine the minimal rectangle containing a specific edge as one moves successively around the edges of the polygon. This method can be imagined as having two pairs of parallel caliper lines pivoting about opposed vertices of the polygon until one caliper line meets an edge. Then, the area of the rectangle for that orientation is noted, and the caliper line starts pivoting about the next vertex of that edge. As a result, the algorithm keeps track of the other sides of the rectangle associated with each edge of the polygon. So, a single scan of the polygon edges (actually, a 90° rotation is enough) suffices to find the minimal rectangle.

In 3D, it is considerably more complicated to find the minimum volume bounding cuboid of a convex polyhedron, because the faces of the minimal cuboid may not coincide with any face of the polyhedron. This is illustrated by the example of a regular tetrahedron, where only its edges coincide with the faces of the bounding cuboid.

The current fastest 3D bounding cuboid algorithm is by [O'Rourke, 1985], which runs in time, has several special cases, and is considerably more difficult to implement. O’Rourke’s algoruthm is based on his observation that “A box of minimal volume circumscribing a convex polyhedron must have at least two adjacent faces that contain edges of the polyhedron.” No faster exact algorithm has been found.

Regardless, since algorithms can be very slow in practice for large point sets, there is considerable interest in fast approximations for the minimum cuboid in 3D and higher dimensions. Several methods have been suggested, such as: (1) only consider cuboids that have a face coinciding with a polyhedron face (which is as discussed in [O'Rourke, 1985], and can be 2 times too large), (2) principal component analysis on the point set (which is fast, but often results in a poor solution), (3) brute-force methods that sample many possible orientations for a cuboid, (4) reduce a large point set to a smaller approximate set (e.g., by selecting the cells in a discrete grid that contain set points) [Barequet & Har-Peled, 1999], and others. All these methods have trade-offs between the solution accuracy versus the efficiency of execution.

A recent promising method [Chang, Gorissen & Melchior, 2011] involves optimization on the manifold of 3D rotations. To find the minimum of a cuboid objective function, they use a hybrid of a simplex search and a genetic algorithm. Their Matlab® experimental results are very good, with accurate approximations (less than 1% error in over 98% of the cases), runtimes of less than 5 seconds for convex 3D polyhedra with up to 3000 vertices, and asymptotic speed observed to be for the cases they studied (with up to 10,000 vertices). See their excellant online paper for more details. Theoretical results supporting their observations still need to be developed.

There are also algorithms for the approximate bounding cuboid in higher dimensions. Recent work can be found in Chapter 6 “Cuboids” from [Gartner, Wagner & Welzl, 2008], which is based on work by [Barequet & Har-Peled, 2001]. They show that for an n vertex convex polytope in dimension d, one can compute in time a cuboid C that contains and satisfies , where is the exact smallest bounding cuboid of .

There are two useful bounding containers whose boundary is given by a quadratic expression: the bounding ball (a disk or sphere), and the bounding ellipse or ellipsoid. These are somewhat harder to compute than linear containers, but they are more efficient to apply at runtime, especially in higher dimensions.

### The Bounding Ball

The "bounding ball" (or "bounding disk" or "bounding sphere") of a geometric object is the smallest circle (in 2D space) or sphere (in 3D and d-D space) containing the object. It is also called the "minimal spanning sphere" of the object. In any dimension, the bounding ball of a linear geometric object (defined by the set S of  its vertices set) is unique, and is specified by a center point C and a radius R.

It is easy to test that a point is inside a bounding ball by checking that it is within distance R of the center C. Also, two balls, say B1 and B2, are disjoint if the distance between their centers is greater than the sum of their radii, that is: . These basic tests are very simple and efficient no matter what the dimension of the objects involved. This is not true of linear containers where the number of inequality tests increases with the dimension of the space. On the other hand, it is more difficult to precompute the bounding ball of a point set since quadratic expressions are involved.

There are several algorithms for exactly computing the minimal ball for a set S of n points. Some authors have noted that the minimal ball can be derived directly from the "Furthest-point Voronoi Diagram" which can be computed in time. This is a nice theoretical result, but is not easy to implement in practice. On the other hand, it has been shown ([Welzl, 1991], [de Berg et al, 2000]) that the bounding ball can be computed using a randomized linear programming algorithm that runs in expected time, specifically in expected time for a (d–1)-D space bounding ball.  The algorithm is incremental: it starts with a random permutation of the point set and an initial ball B2 containing the points P1 and P2. It then incrementally adds the other points, constructing increasingly larger balls to contain them as needed. So, Bk is the bounding ball for and then we consider Pk+1. If it is in Bk, then . Otherwise, it is outside Bk and we must expand Bk to get a Bk+1 that includes Pk+1. The trick is to make sure that the Bk+1 we end up with is minimal. To do this, the incremental algorithm is applied recursively to the set with the restriction that Pk+1 must always be on the boundary of all balls constructed. In the process of doing this, there is yet another level of recursion where balls are constrained to have 2 specific points on their boundary. After that, newly constructed balls must go through 3 non-collinear points, but in 2D three points uniquely determine a ball, and this determines Bk+1. So, for a 2D ball, the algorithm has 2 levels of recursion. In 3D, there are 3 levels to get 4 non-planar points that uniquely determine a 3D sphere.

Despite sounding complicated, this algorithm is straightforward to implement (see [de Berg et al, 2000]). Further, clever heuristics can speed it up significantly in practice. An excellent fast implementation by [Bernd Gartner, 1999] is available on the web with downloadable source code. His routine works for 2D, 3D, and higher dimensions up to about 30-D with only about 300 lines of C++ code. It is numerically stable, and is very fast in low dimensions.

### A Fast Approximate Bounding Ball

Another extremely fast algorithm by [Ritter, 1990] computes a good approximation to the bounding ball. Although he presents a 3D algorithm, his method works efficiently in any d-dimensional space. His deterministic incremental algorithm avoids doing any recursion, and just scans the vertex list twice. For a point set S, it works as follows :

1. First, an initial good guess is made for a bounding ball B. This is done by finding two points of S that are far from each other, and using the line between them as an initial diameter. Then, the center of this diameter is the initial ball center, and half the length of the diameter is the initial ball radius. One can find points of S that are far from each other by selecting ones on opposite extremes of the bounding box for S.

2. Next, each point P of S is tested for inclusion in the current ball (by simply checking that its distance from the center is less than or equal to the radius). If the next point Pk+1 is in the current Bk, then and one just proceeds to the next point. But if Pk+1 is outside Bk, then Bk is expanded just enough to include both itself as well as the point Pk+1. This is done by drawing a line from Pk+1 to the current center Ck of Bk and extending it further to intersect the far side of Bk. This segment is then used as the new diameter for an expanded ball Bk+1. As shown in the diagram, it clearly contains the prior ball Bk and (thus) all points of S already considered, and no additional recursion is needed.

Each of the two stages of this algorithm does efficient computations. Ritter estimates that this approximation is within 5% of the actual minimal bounding ball. Below, we give a simplified 2D implementation fastBall().

### The Bounding Ellipsoid

As you might expect, the "bounding ellipsoid" (or "minimal spanning ellipsoid") is the smallest volume ellipsoid (smallest area ellipse in 2D) that contains a vertex point set S. Like the minimal rectangle, it can have any orientation. Thus, it also is a very tight approximation for the object it contains, and is an excellent container. Also, it is not difficult to test inclusion of a point in an ellipse, especially in 2D where the sum of the distances of a point from the two focal points is a constant on the boundary of the ellipse.

For a set of non-collinear points (non-planar in 3D) the bounding ellipsoid exists and is unique. [Welzl, 1991] gives a fast randomized algorithm for computing the bounding ellipsoid in expected time for (d–1) dimensional space. A fast implementation has been developed by [Gartner & Schonherr, 1997]. The Welzl algorithm is basically the same as his randomized incremental bounding ball algorithm. Having constructed the bounding ellipse Ek for the first k points, one then adds the next point Pk+1. If Pk+1 is inside Ek, then . Otherwise the algorithm must inductively construct Ek+1. Again, the algorithm must recursively construct the minimum ellipse for with the restriction that Pk+1 is on the boundary of Ek+1. The recursion stops when there are enough constraints to uniquely define an ellipse. Of course, this is somewhat more difficult to determine than for a spherical ball. See [Gartner & Schonherr, 1997] for details.

Nevertheless, especially in higher dimensions, the bounding ellipsoid is superior to the minimal cuboid in many ways. It is unique, whereas the minimal cuboid is not. There is a reasonable algorithm to implement it. And it is a good approximation of the object it contains, much better than the minimal cuboid. In fact, if E(S) is the bounding ellipsoid for a point set S with convex hull C(S) in dimension d, then:

where scaling is with respect to the center of E(S).

## Implementations

// Copyright 2001 softSurfer, 2012 Dan Sunday
// This code may be freely used and modified for any purpose
// providing that this copyright notice is included with it.
// SoftSurfer makes no warranty for this code, and cannot be held
// liable for any real or imagined damage resulting from its use.
// Users of this code must verify correctness for their application.

// Assume that classes are already given for the objects:
//    Point and Vector with
//        coordinates {float x, y;}
//        operators for:
//            Point  = Point ± Vector
//            Vector = Point - Point
//            Vector = Vector ± Vector
//            Vector = Scalar * Vector    (scalar product)
//            Vector = Vector / Scalar    (scalar division)
//
//===================================================================

// dot product which allows  vector operations in arguments
#define dot(u,v)   ((u).x * (v).x + (u).y * (v).y)
#define norm2(v)   dot(v,v)         // norm2 = squared length of vector
#define norm(v)    sqrt(norm2(v))  // norm = length of  vector
#define d(u,v)     norm(u-v)        // distance = norm of difference

// fastBall(): get a fast approximation for the 2D bounding ball
//              (based on the algorithm given by [Jack Ritter, 1990])
//    Input:  an array P[] of n points (2D xy coords)
//    Output: a bounding ball = {Point center; float radius;}
void
fastBall( Point P[], int n, Ball* B)
{
Point C;                            // Center of ball
float xmin, xmax, ymin, ymax;       // bounding box extremes
int   Pxmin, Pxmax, Pymin, Pymax;   // index of  P[] at box extreme

// first get the bounding box and P[] extreme points for it
xmin = xmax = P[0].x;
ymin = ymax = P[0].y;
Pxmin = Pxmax = Pymin = Pymax = 0;
for (int i=1; i<n; i++) {
if (P[i].x < xmin) {
xmin = P[i].x;
Pxmin = i;
}
else if (P[i].x > xmax) {
xmax = P[i].x;
Pxmax = i;
}
if (P[i].y < ymin) {
ymin = P[i].y;
Pymin = i;
}
else if (P[i].y > ymax) {
ymax = P[i].y;
Pymax = i;
}
}
// select the largest extent as an initial diameter for the  ball
Vector dPx = P[Pxmax] - P[Pxmin]; // diff of Px max and min
Vector dPy = P[Pymax] - P[Pymin]; // diff of Py max and min
float dx2 = norm2(dPx); // Px diff squared
float dy2 = norm2(dPy); // Py diff squared
if (dx2 >= dy2) {                      // x direction is largest extent
C = P[Pxmin] + (dPx / 2.0);          // Center = midpoint of extremes
}
else {                                 // y direction is largest extent
C = P[Pymin] + (dPy / 2.0);          // Center = midpoint of extremes
}

// now check that all points P[i] are in the ball
// and if not, expand the ball just enough to include them
Vector dP;
float dist, dist2;
for (int i=0; i<n; i++) {
dP = P[i] - C;
dist2 = norm2(dP);
continue;
// P[i] not in ball, so expand ball  to include it
dist = sqrt(dist2);
C = C + ((dist-rad)/dist) * dP;    // shift Center toward P[i]
}
B->center = C;
return;
}

## References

Gill Barequet and Sariel Har-Peled, “Efficiently approximating the minimum-volume bounding box of a point set in three dimensions”, Journal of Algorithms 38 91-109 (2001)

Mark de Berg et al, Computational Geometry: Algorithms and Applications (3rd Edition),  Section 4.7 "Smallest Enclosing Disks" (2010)

Chia-Tche Chang, Bastien Gorissen & Samuel Melchior, “Fast oriented bounding box optimization on the rotation group SO(3; R)”, ACM Transactions on Graphics, Vol. 30, No. 5, Article 122, Oct. 2011

H. Freeman & R. Shapira, “Determining the minimum-area encasing rectangle for an arbitrary closed curve”, Comm ACM 18(7) 409-413 (1975)

Bernd Gartner, "Smallest  Enclosing Balls - Fast and Robust in C++" Web Site (1999)

Bernd Gartner & Sven Schonherr, "Smallest Enclosing Ellipses - Fast and Exact", Tech. Report B 97-03, Free Univ.  Berlin, Germany (1997)

Bernd Gartner, Uli Wagner & Emo Welzl, Lecture Notes for Approximate Methods in Geometry (2008); esp Chapter 5 “Approximate Smallest Enclosing Balls” and Chapter 6 “Cuboids”.

Joseph O'Rourke, "Finding Minimal  Enclosing Boxes", Int'l J. Comp. Info. Sci. 14 (1985), 183-199

Joseph O'Rourke, Computational Geometry in C (2nd Edition)  (1998)

Hormoz Pirzadeh, Rotating Calipers Web Site (1999)

Franco Preparata & Michael Shamos, Computational Geometry: An Introduction (1985)

Jack Ritter, "An Efficient Bounding  Sphere" in Graphics Gems (1990)

Godfried Toussaint, "Solving  geometric problems with the rotating calipers" in Proc. IEEE MELECON'83 (1983)

Emo Welzl, "Smallest enclosing disks (balls and ellipsoids)" in New Results and New Trends in Computer Science,  Lecture Notes in Computer Science, Vol. 555 (1991), 359-370