GUI程序优化算法之矩形覆盖

GUI程序优化算法之矩形覆盖
在一些GUI程序中，需要在一个图形容器中同时绘制若干个矩形区域的图形，而且这些矩形区域可能相互覆盖，这就类似于Windows桌面中各个矩形窗体的相互覆盖，这时程序绘制这些矩形图形时，应当不需要全部绘制(如图1中的矩形B,C)，甚至其中的某些被其他矩形完全覆盖的矩形区域不需要全部绘制(如图1中的矩形A)，这样就需要一个算法来进行判断实际应绘制的区域。

大家知道，在Windows控件的Paint事件中系统会传送一个实际需要的矩形绘制剪切区域，只有这个矩形区域是需要绘制的区域，一些情况下这个区域小于控件全部的显示区域，这样可以利用这个矩形绘制区域可以进行初步的绘制优化。

在绘制某个矩形区域前，首先获得所有可能覆盖该矩形区域的所有其他矩形，然后将其他矩形一个个进行判断，获得没有被覆盖的区域，然后将所有残存的矩形区域处理下一个覆盖的矩形，小弟暂称这种处理方法为矩形覆盖，现在根据图2对矩形覆盖进行详细说明。

首先考虑只有一个覆盖矩形且这个覆盖矩形区域比较小的情况，图2中的大矩形为当前要绘制的矩形图形和剪切区域的交集坐标和大小为(left1 , top1 , width1 , height1 , right1 , bottom1 )，而覆盖矩形坐标和大小为(left2 , top2 , width2 , height2 , right2 , bottom2 ),则覆盖矩形覆盖了大矩形，会形成4个小矩形，这4个小矩形的坐标和大小分别为(left1 , top1 , left2 - left1 , height1 ),( left2 , top1 , right1 - left2 , top2 - top1 ), ( right2 , top2 , right1-right2 , bottom1-top2) , ( left2 , bottom2 , width2 , bottom1 - top2 )。

由于小矩形宽度和高度不可能小于0，因此根据覆盖区域的位置和大小会生成0至4个的小矩形。当出现覆盖矩形完全覆盖原始矩形的极端情况时会生成0个小矩形，此时原始矩形在任何情况下就没有必要进行绘制。若覆盖矩形和原始矩形没有交集则不需要进行覆盖操作。

当有第二个覆盖矩形时，根据已经分出的4个小矩形再跟第二个覆盖矩形进行同样的覆盖矩形，理论上会在生成16个小矩形，同样再处理其他的覆盖矩形，若有n个覆盖矩形，则理论上会生成4的n次方个小矩形，但实际上生成的小矩形数目会远小于这个理论值。

进行覆盖操作时，分解所得的小矩形越多，则根据这些小矩形进行绘制操作越复杂，因此需要控制小矩形的个数，若覆盖矩形相对于原始矩形比较小时，则可以认为不需要进行覆盖操作。因此提出覆盖率的参数，当覆盖矩形的面积和原始矩形的面积的比率小于覆盖率时就可以认为不需要进行覆盖操作。

根据覆盖操作可以减少绘制区域，优化绘图程序，提高速度。

根据这种算法，小弟编制了一个演示程序。程序用户节目如图3,下载地址为
http://files.cnblogs.com/yyf9989/RectOverride.rar