平面上顶点集合的包围容器
寻找几何物体（点、线段、面与体等）的包围容器（Bounding Container）能加速三维仿真程序中的光线跟踪、碰撞检测和消隐处理等过程，因为在使用这些复杂的处理方法前，采用一个包围容器的预处理能先剔除一些不需参加后续计算的几何物体。包围容器的形状分为矩形、多边形和椭圆等，需注意计算这个容器所消耗的时间应小于希望节省的时间。
以多边形包围容器为例，寻找每条边，划分空间为两部分，最后各个部分的交集为所求容器。
Fi(X, Y) = aiX + biY +ci <=0 (i = 1,2 …k) (二维)
Fi(X, Y, Z) = aiX + biY +ciZ + di <=0 (i = 1,2 …k) (三维)
若容器为一正规的矩形或长方体，即各条边平行于轴，可通过比较顶点的各轴数值大小，求得最小值(Xmin, Ymin, Zmin)和最大值(Xmax, Ymax, Zmax)，以X=Xmin，X= Xmax，Y=Ymin，Y=Ymax，Z=Zmin, Z=Zmax等平面划分空间，最后构成的交集为所求包围容器。
若希望矩形或长方体容器各条边不用平行于轴，可构建X±Y或X±Y±Z表达式来划分空间。
将各顶点数据代入表达式，经比较求得Cmin、Cmax、dmin和dmax等系数。对三维空间数据同样处理，求四个表达式X±Y±Z的8个系数。
顶点集合Q的凸包(Convex Hull)是指存在一个最小凸多边形，使得Q中的点在这个多边形的边上或者在其范围内。
求凸包有很多方法，将在随后章节讲解。
若包围容器的形状为球体（在二维平面上是圆）的话，第一步可通过顶点初始化一个球体，在考虑新顶点加入的时候，如果将新顶点包含在范围内，则球体保持不变。如果新顶点位于范围之外，则考虑如何改变球心和增大半径。许多算法考虑是如何使得这种改变最小化。以下介绍的是一种快速、简单和近似的改变方法，即连接新顶点和原球心，以这两顶点距离加上原半径构成新直径，直径上中点为新圆心。
参考代码：
// 输入: n个顶点的数组V[]
// 输出: 包围圆的圆心和半径
void CDEMAlgorithm::fastBall( Point V[], int n, Ball* B)
{
Point C; // 圆心
double rad; //半径
double radTwo; // 半径的平方
double xmin, xmax,ymin,ymax; // 包围盒的顶点坐标
int Pxmin,Pxmax,Pymin,Pymax; //包围盒的顶点的索引
// 寻找最小和最大数值
xmin = xmax = V[0].x;
ymin = ymax = V[0].y; //赋第一个顶点的数值
Pxmin = Pxmax = Pymin = Pymax = 0;
for (int i=1; i<n; i++) {
if (V[i].x < xmin) {
xmin = V[i].x;
Pxmin = i; //记录索引
}
else if (V[i].x > xmax) {
xmax = V[i].x;
Pxmax = i; //记录索引
}
if (V[i].y < ymin) {
ymin = V[i].y;
Pymin = i; //记录索引
}
else if (V[i].y > ymax) {
ymax = V[i].y;
Pymax = i; //记录索引
}
}
// 以最大数值初始化圆
Vector dVx = V[Pxmax] - V[Pxmin]; // X轴的最大跨度
Vector dVy = V[Pymax] - V[Pymin]; // Y轴的最大跨度
double dx2 = Dot(dVx,dVx); // X轴的最大跨度的平方
double dy2 = Dot(dVy,dVy); // Y轴的最大跨度的平方
if (dx2 >= dy2) { // X轴的最大跨度的平方大于Y轴的最大跨度的平方
C = V[Pxmin] + (dVx / 2.0); // 设置圆心的位置
radTwo = Dot(V[Pxmax] - C,V[Pxmax] - C); //半径的平方
}
else { // Y轴的最大跨度的平方大于X轴的最大跨度的平方
C = V[Pymin] + (dVy / 2.0); //设置圆心的位置
radTwo = Dot(V[Pymax] - C,V[Pymax] - C); //半径的平方
}
rad = sqrt(radTwo); //半径
// 对初始圆扩展
Vector dV;
double dist, dist2;
for (int i=0; i<n; i++) {
dV = V[i] - C; //新顶点与圆心的矢量差
dist2 = Dot(dV,dV);
if (dist2 <= radTwo) // 新顶点位于圆内
continue;
//新顶点不在圆内，需扩展圆
dist = sqrt(dist2); //新顶点和圆心之间的距离
rad = (rad + dist) / 2.0; //改变半径
radTwo = rad * rad;
C = C + ((dist-rad)/dist) * dV; // 新圆心的位置，从原圆心沿矢量差移动
}
B->center = C; //赋圆心
B->radius = rad; //赋半径
return;
}