关于包围盒，你需要知道的那些事
大家好，我是前端西瓜哥。
本文将讲讲解二维中的包围盒。
三维的包围盒是一脉相承的，理解了二维也就懂了三维。
包围盒（bbox, bounding box）指的是包围图形的一个矩形。
“盒” 通常特指矩形（二维）或是立方体（三维）。
实际上包围形状的图形某些情况下会使用多边形（凸包、凹包）或是圆形或是其他，不仅限于矩形的更泛用的叫法应该是 “包围体”（bounding volume）。
包围盒的作用
- 一种 高效 判断两个图形是否碰撞的方案，以降低精度为代价。退一步说，即使要进行精准的碰撞判定，也可以用包围盒提前发现图形不可能相交，避免后续的高昂运算。
- 在图形界面上，绘制图形的包围盒，让用户感知到拾取图形成功。
- 剔除不在视口内的图形，避免不必要的渲染。
包围盒的表达
我们使用左上角和右下角两个点表达包围盒。
interface Bbox {
minX: number
minY: number
maxX: number
maxY: number
}
这里不再建议使用 x、y、width、height 的写法。
width 和 height 纯属多余，本身不会用到，却要在每次碰撞运算时，通过 x + width 和 y + height 得到 maxX 和 maxY 再运算。
图形的包围盒
下面介绍几种中比较常用到的包围盒。
AABB
这里有一个椭圆，非常朴实的椭圆。
基于 x、y、width、height 属性渲染出来的椭圆。
其 bbox 为：
const bbox = {
minX: attrs.x,
minY: attrs.y,
maxX: attrs.x + attrs.width,
maxY: attrs.y + attrs.height,
}
这种包围盒称为 AABB 包围盒。
AABB 包围盒全称为 axis-aligned bounding box，轴对齐包围盒。
它是一个矩形，且它的边是和轴线（比如 x 轴和 y 轴）对齐的。
这个 AABB 刚好紧密包裹住椭圆，所以这个包围盒同时也是 MBR（最小外接矩形）。
判断两个 AABB 包围盒是否发生碰撞很简单：
const isBboxIntersect = (bbox1, bbox2) => {
return (
bbox1.minX <= bbox2.maxX &&
bbox1.maxX >= bbox2.minX &&
bbox1.minY <= bbox2.maxY &&
bbox1.maxY >= bbox2.minY
);
};
包围盒不一定要是单个图形的包围盒，也可以是多个图形的，做个 merge 即可。
const mergeBbox = (bboxs) => {
let minX = Number.MAX_VALUE;
let minY = Number.MAX_VALUE;
let maxX = Number.MIN_VALUE;
let maxY = Number.MIN_VALUE;
for (const bbox of bboxs) {
minX = Math.min(minX, bbox.minX);
minY = Math.min(minY, bbox.minY);
maxX = Math.max(maxX, bbox.maxX);
maxY = Math.max(maxY, bbox.maxY);
}
return { minX, minY, maxX, maxY };
}
OBB
一天，椭圆说它想要旋转，于是我们引入了 rotate 属性，通常保存弧度值。
于是出现了一个有朝向的包围盒，称之为 OBB。
OBB 包围盒全称 oriented bounding box，即有朝向的包围盒。
该包围盒也是矩形，但是因为有旋转，边不一定和轴线对齐，但能 更紧凑地包围目标图形。
包围盒需要补充一个旋转属性。
const bbox_obb = {
minX: attrs.x,
minY: attrs.y,
maxX: attrs.x + attrs.width,
maxY: attrs.y + attrs.height,
rotate: attrs.rotate, // 或者用旋转矩阵
}
对于 OBB 之间的碰撞判定，需要用复杂一些的 分离轴定理 算法来判断。
分离轴定理专门用来进行凸多边形之间的碰撞检测，矩形也是凸多边形，所以可以用。
虽然有 OBB 了，但我们还是需要图形的 AABB 包围盒，用于更高精度的选区框选、渲染剔除等用途。
一种简单的方式是基于 OBB 的 4 个点重新计算出一个 AABB，如下图。
AABB 并不要求紧密包裹图形，所以并不是一定是最小外接矩形（MBR）。
对此，如果想提高 AABB 的精度，可以用几何算法去求 MBR 作为图形的 AABB。
但涉及到平面几何，不同图形的算法不一样。像是椭圆大概要用到蒙日圆，多边形则求变换后顶点的坐标值的最大最小 x y 值。
还有一种场景，为了支持不局限于旋转的更多形变效果（比如斜切、翻转），我们会选择使用 transform 矩阵。
此时我们需要的是上图这种包围多边形，勉强叫做有 transform 的 box 吧。
因为是线性形变，包围多边形是平行四边形，依旧是凸多边形，所以还是可以分离轴定理 算法来计算碰撞。
渲染下的包围盒
这里有个地方有稍微注意一下，关于描边的。
有些图形的描边比较大，或者画布缩放很大。
此时进行框选，如果框选到描边的部分区域，理论上也算选中图形了，所以要把描边的宽度考虑上，将包围盒子往外扩展描边宽度的二分之一。
const extendBbox = (bbox, padding) => {
return {
minX: bbox.minX - padding,
minY: bbox.minY - padding,
maxX: bbox.maxX + padding,
maxY: bbox.maxY + padding,
};
}
const renderedBbox = extendBbox(bbox, attrs.strokeWidth / 2)
除了在框选用到，也会用在不渲染图形剔除的场景，但可能还要额外考虑投影这些其他渲染因素。
结尾
我是前端西瓜哥，关注我，学习更多图形编辑器开发知识。