aabb是游戏中经常用的包围盒。本文提出一种2d空间内自动生成aabb的算法，读者也可在此基础上开发出基于3d的aabb自动生成算法。 本算法可以用来在一个给定区域内进行aabb的自动挖掘产生。如：场景内各建筑的阻挡点包围框；纹理贴图上小图标的包围框…… 算法
   aabb是游戏中经常用的包围盒。本文提出一种2d空间内自动生成aabb的算法，读者也可在此基础上开发出基于3d的aabb自动生成算法。
    本算法可以用来在一个给定区域内进行aabb的自动挖掘产生。如：场景内各建筑的阻挡点包围框；纹理贴图上小图标的包围框……
算法描述：
创建一个aabb空列表aabblist循环给定空间内的每一个点pt    如果pt为不感兴趣的点，则跳转2    如果pt为感兴趣的点        为pt创建一个大小为1的aabb rect        遍历aabblist中每个元素aabb            如果rect和aabb邻接或相交，则表明rect和aabb可以合并                rect = union（rect，aabb），将aabb合并到rect                从aabblist中删除aabb        将rect加入到aabblist返回aabblistc#实现代码如下：
         /// 
        /// 判断是否对给定位置感兴趣并愿意放入aabb
        /// 
        delegate bool interestpredicate(int x, int y);
/// 
        /// 得到给定区域范围内的所有aabb
        /// 
        /// 要搜索的区域，该区域的每个点值将逐一传给
        static listrectangle> generateallaabb(rectangle area, interestpredicate isinterest)
        {
            if (isinterest == null)
                throw new argumentnullexception(isempty);
// 结果包围框集
            listrectangle> aabblist = new listrectangle>();
// 临时变量。一次合并过程中发现的可合并的包围框下标
            listint> intersectlist = new listint>();
for (int y = area.top; y
            {
                for (int x = area.left; x
                {
                    if (isinterest(x, y) == false)
                        continue;
                    intersectlist.clear();
rectangle rect = new rectangle(x, y, 1, 1);
// 对已有的包围框进行遍历合并
                    for (int i = 0; i
                    {
                        rectangle aabb = aabblist[i];
                        // 判断是否邻接，相交或者紧挨着都算邻接
                        if (rect.intersectswith(new rectangle(aabb.x - 1, aabb.y - 1, aabb.width + 2, aabb.height + 2)))
                        {
                            rect = rectangle.union(rect, aabb);
                            intersectlist.add(i);
                        }
                    }
// 倒序遍历，避免对list进行删除时下标失效
                    for (int i = intersectlist.count - 1; i >= 0; i--)
                    {
                        aabblist.removeat(intersectlist[i]);
                    }
// 将合并后的包围框加入结果集
                    aabblist.add(rect);
                }
            }
            return aabblist;
        }
下面的例子给cegui windowslook风格的贴图加上aabb包围框，该工作如果用ceimageseteditor之类的工具手工做的话需要很长的时间和耐心。
        private void form1_load(object sender, eventargs e)
        {
            int backgroundcolor = color.white.toargb();
bitmap bitmap = new bitmap(windowslook.bmp);
// 计算包围框
            listrectangle> list = generateallaabb(
                new rectangle(0, 0, bitmap.width, bitmap.height),
                (x, y) =>
                {
                    color c = bitmap.getpixel(x, y);
                    return c.a != 0 && c.toargb() != backgroundcolor;
                });
// 将得到的包围框绘制出来
            using (graphics g = graphics.fromimage(bitmap))
            {
                pen pen = new pen(color.fromargb(100, color.red));
                g.drawrectangles(pen, list.toarray());
                pen.dispose();
            }
picturebox1.image = bitmap;
        }
    结果为下图中右边的样子，左边是原始的图片：
可以考虑将该算法加入到ceimageseteditor工具中，对新建立的imageset，自动生成小图标的包围盒。在此基础上手工稍作调整即可。
     感谢廖鑫炜、开平等人提供帮助！
扩展阅读：
《数据聚类》算法（英文版的更全面）
2012-2-6
    若性能不满足，可以用bitmap.lockbits替代bitmap.getpixel手工解析像素。