基于VC++6.0 的最小包络图形绘制及其
应用
李远彬，林小凤，赵红芬，韩毅**
作者简介：李远彬，（1987-），男，硕士研究生，新能源汽车与控制技术
通信联系人：韩毅，男，硕士生导师，车辆控制. E-mail: hanhany@gmail.com
5 （长安大学汽车学院，西安 710064）
摘要：最小包络线的计算在计算机图形学中是一个很重要的方面，最小包络矩形、圆、正方
形等等在实际中应用十分广泛。最小包络矩形普遍应用于异形件的布局问题，最小包络圆广
泛应用于信号塔的选址问题等等。本文介绍了最小包络矩形和圆的算法，并给予软件实现，
同时给出了最小包络矩形的非常有前景的应用，即应用于快速恢复布雷区域的道路通行系
10 统。
关键词：计算机图形学；最小包络矩形；最小包络圆；旋转卡壳算法；随即增量算法
中图分类号：P315.69
The Minimum Envelope Rendering and Its Application
15 Based on VC++6.0
LI Yuanbin, LIN Xiaofeng, ZHAO Hongfen, HAN Yi
(School of Automotive Engineering,Chang'an University, Xi'an 710064)
Abstract: The smallest envelope is a very important aspect in computer graphics, the smallest
envelope of rectangular, square and round is very popular. The smallest envelope of rectangular is
20 widely used in the position of shaped pieces and the smallest envelope round is very popular in the
siting of cell towers. The paper introduces the algorithm of the smallest envelope of rectangular,
round and realizes its software part. Also we gives a very promising application of the smallest
rectangular envelope, which is used in fast recovery of mined areas road access system.
Keywords: Computer Graphics; The smallest rectangular envelope; Minimum envelope round;
25 Shamos Algorithm; Randomized incremental algorithm
0 引言
计算机图形学一个主要的目的就是利用计算机产生具有真实感的图形，而最小包络图形
的绘制是计算机图形学在绘制物体的包络轮廓方面的一个重要应用。通常，我们要得到一个
30 物体的实体模型，是比较困难的，它涉及的运算方法较为复杂，精确求解其过程比较困难。
而在很多应用场合，我们没有必要知道物体的准确形状，因此就可以简化模型，用它的最小
轮廓替代。在描述物体轮廓方面，通常可以用其外接最小包络图形（矩形、正方形、圆）近
似描述其形状。例如，最小包络矩形普遍应用于异形件的布局问题，最小包络圆广泛应用于
信号塔的选址问题以及外接矩形近似描述地理形状等等。
35 1 二维坐标系和二维随机点的生成
二维随机点可以代表物体的部件，也可以代表群体中的个体。只要得到一组二维随机点，
我们就可以描述物体的形状和运动。例如，在一定道路区域内，可以把一个人当成一个随即
点，知道每个人的位置，就可以绘制出最小包络矩形，进行车辆避障。
而对于一组随机的二维点，绘制它的最小包络图形，就相当于绘制其外接凸包的最小包
40 络图形。为此，我们需要一个参考坐标系，来确定各个点的位置。
 图1 二维随机点和凸包
1.1 二维坐标系
45 绘图函数都需要制定坐标值，即其所绘图形是在某个具体的坐标系中显示的。经过绘图
函数把图形显示在屏幕坐标系中的过程称为映射。根据需要，我们选用ＶＣ＋＋中的逻辑坐
标MM_LOMETRIC（坐标原点位置可自由设置，X 轴向右，Y 轴向上）[1]，将坐标原点设
为视窗边界宽度的3/20,高度的4/5。
50 图2 二维坐标系
1.2 二维随机点
真正意义上的随机数（或者随机事件）在某次产生过程中是按照实验过程中表现的分布
概率随机产生的，其结果是不可预测的，是不可见的。而计算机中的随机函数是按照一定算
 55 法模拟产生的，其结果是确定的，是可见的。所以用计算机随机函数所产生的“随机数”并
不随机，是伪随机数。
随机数发生器[2]：
d 0 = d ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ ①
dn = b . dn.1 + c ＊＊＊＊＊＊＊＊＊＊＊ ②
60 an = dn /(n . m)+ m ＊＊＊＊＊＊＊＊ ③
根据公式①、②、③就能得到一组数列。但是有一个值得注意的问题，随机数的产生需
要有一个随机的种子，因为用计算机产生的随机数是通过递推的方法得来的，必须有一个初
始值，也就是通常所说的随机种子，如果不对随机种子进行初始化，那么计算机有一个缺省
的随机种子，这样每次递推的结果就完全相同了，因此需要在每次程序运行时对随机种子进
65 行初始化，我们的方法是调用random（int）这个函数，其参数就是随机种子，但是如果给
一个常量，则得到的随机序列就完全相同了，因此可以使用系统的时间作为随机种子，因为
系统时间可以保证它的随机性。
产生二列随机数，组成二维向量，一列相当于x，另一列相当于y，这样就可以在坐标
系上绘制，得到二维随机点。
70
图3 随即二维点
2 随即点簇最小凸包的绘制
Pn 为随机点集，EPn 为外接凸包点集[3]。
75 设凸集中y 坐标最小的点为Pn-1，
 图4 点集中y 坐标最小点
把Pn-1 同凸集中其他各点用连接起来，并计算这些线段与水平线的夹角。然后按夹角大
80 小及到EPn-1 的距离进行词典分类(先按夹角的大小排序，当夹角一样时，按到EPn-1 的距离
进行排序)，得到一个序列P0、P1、P2… , Pn 。
图5 排序后的点（幅角升序）
85 从Pn-1 开始依次连接这些点，凸包顶点判断依据：
Pn-1= EP0，P0 = EP1，连接EP0、EP1，然后遍历其他点，根据构成的三角形顺序确定顶
点。
 图6 逆时针旋转
90
图7 顺时针旋转
由图6 和图7 对比可知，当排序后的点顺序连接后，若构成一个逆时针三角形则认载入
95 点为凸包顶点（新载入的点在凸包外侧）；若构成一个顺时针三角形则该点不为凸包的顶点
（前面载入的点在凸包内侧）。
例如图6 和图7 中的2 点，图6 中EP0、EP1、EP2 三点构成逆时针，则暂且认为EP2
是凸包顶点；图7 中EP1、EP2、EP3 三点构成顺时针，则排出EP2 即不认为是凸包顶点；下
次以 EP1、EP3、EP4 为判断三角形，以此判断下去，直至遍历所有点，就可得到凸包边界
100 点列EPn。
EP0
EP1
EP2
EP3
EP4
EP0
EP1
EP2
EP3
EP4
 图8 外接凸包
3 最小包络图形
105 3.1 最小包络矩形
对于多边形的一个外接矩形，存在一条边与原多边形的边共线[4]。
旋转卡壳算法：
第1 步 选取所得凸包中一条边作为起始边并对该凸包以选中边的左端点为中心旋转使
该边平行于坐标横轴，计算并保存其最小绑定矩形的坐标、该边的编号及旋转角度。
110
图9 EP0 至EP1 变换到水平坐标轴的最小绑定矩形
 图10 EP0 至EP1 的最小绑定矩形
115
第2 步 顺序选择其他边，并按照第2 步的方法计算并保存其最小绑定矩形的坐标、该
边的编号及其旋转角度。
第3 步 比较所得的最小绑定矩形的面积，其中面积最小者按其记录的旋转角度以该边
的左端点为圆心逆向旋转即为所求的最小包络矩形。
120
图11 最小包络矩形
注：由于每次刷新屏幕，随机点都要重新生成；故图9、图10 、图11 并不是对同一组随即点的描述。
3.2 最小包络圆
125 随即增量算法[5]：
第1 步我们从一点开始，不断把凸壳中其他点加入点集中，同时维护新的点集的最小
 覆盖圆，这样就可以求出最小包络圆。
在增量算法求最小圆覆盖的算法中，我们需要确定第i 个点是否在当前i-1 个点的最小
包络圆中：
130 第1 步 如果不在，我们就要更新当前圆，由于第i 个点必在更新后的圆中，因此需从
前i 个点中选择一个点j，由点i 和j 确定一个圆，然后枚举i 前的其他点k；
第2 步 利用遍历法看其它点k 是否在圆中，如果不在则更新j，重复第1 步；
第3 步 这样就可以求出由第i 个点确定的包含前i 个点的圆，但不是每个i 都会去更
新当前圆，只有i 不在当前圆内，才需要更新。
135
图12 最小包络圆
4 最小包络矩形的应用
大规模军作战兵团的快速机动性，可靠快速的补养，取决于现代化的交通工具以及公路、
140 铁路等交通设施。一方面，需要构建合理的现代化交通网络，提升武器装备；另一方面，在
战时需要保障道路的通畅、避免被破坏。如果道路被破坏，则会导致交通不畅、兵团不能执
行战术战役命令，或后勤车队无法保证给养供给。而在破坏道路的武器中，地雷是一种价格
低廉的武器，是埋入地表下或布设于地面的爆炸性火器。它可以大规模布置，且具有不易发
现、难以排出的特点，这对道路具有非常大的破坏性。一旦敌人在我军行进路线上布雷，则
145 会严重影响我军的行进、战术执行和保养供给。因此，一种高效、安全、快速的排除地雷方
法就显得尤为重要。
对此，本文进行了展望，将最小包络线算法与实际相结合，可以开发一套快速恢复布雷
区域的道路通行系统，包括一线车辆、无人飞机、信息处理模块、数据链和地面遥控站，在
无人飞机上搭载有合成孔径雷达，合成孔径雷达发送脉冲电磁波，电磁波在空气和土壤中传
150 播，并产生回波，对地雷区域存在的地雷回波进行校正后，产生图像；雷达图像经信息处理
 模块处理后，通过数据链将信息传回地面遥控站；地面遥控站收到信息后，进行道路通行路
线选择，并把命令传达给一线车辆，规避地雷区域。
图13 系统方框图
155
地面站台通过GPS 导航方式控制无人机的飞行，并在无人飞机上搭载有超宽带的合成
孔径雷达，合成孔径雷达上的天线在一定高度以不同的俯视角和波束角，发送脉冲电磁波，
穿透地表获取埋设地雷二维高分辨雷达图像，完成对一个大区域范围的地雷探测；地雷探测
成像后，进行CFAR 检测，找出雷达图像中的怀疑目标，对提取出的若干怀疑目标，进行
160 进一步鉴别，剔除检测中的虚警；信息处理模块将雷达图像中的地雷坐标按旋转卡壳算法处
理后，得到包含雷区的最小包络矩形，矩形之外的地方便是可通行区域；地雷坐标和可通行
区域等信息，通过数据链传回地面遥控站；地面遥控站收到信息后，进行道路通行路线选择，
并把指挥命令传达给一线车辆，规避地雷。
学术论文网Tag：代写论文 论文发表 代发论文 职称论文发表 图像论文代写