【doc】意匠图的虚树结构
意匠图的虚树结构
锄,,议'叶,毒应因,座树红均
意匠圈的虚树结构.
冯一明
(北京106信箱)
,s,.f
,巴p
意匠图是编织加工中所用的
图纸.它是在一种特殊的格纸上用不同的颜色填入栅格
从而形成意匠图(见图1).
刊编号
行警号
图l意匠圈
匿红色区绿色口黄色
在意匠图的计算机辅助设计中.如果希望以垒屏幕的方式进行图形编辑.就必须对屏幕上
意匠圈的图案指定标记区.本文提出用树结点遍历的
生成图案的标记区.这种方法可
避免产生屏蔽现象.
1术语介绍
为叙述方便,首先介绍一些术语的定义.若意匠图如图1所示,以意匠图的左上角为起始
点,定义栅格的行,列编号:从左向右列数递增,从上到下行数递增,而左上角的栅格则处于第
一
行,第一列.我们用符号g"lj.c)
示位于意匠图第i行,第j剜,颜色为c的栅格.其中0
?c?15.0为黑色.15为白色.
I.1同色连通区
定义1:设有栅格g(il,j1.c1)和g2(i2,j2,c2),如果&,满足下条件.则称g1,g2这二个
栅格同色连通.
?0<cl<15.0<c2<15 且1=c2:
28
?Iil一?1且jh一扎I?1
在以下的叔述中,如不加说明,颜色值c满足1?c?14.即意匠图的图案是由非黑非白的
颜色所组成.如果栅格gl与g2同色连通.栅格g2与gs同色连通.则称栅格g1与gs亦同色连
通.在图2中,gl与勘同色连通,g3与同色连通,因此gz与g'也同色连通.但g4与I"1
非
同色连通.虽然它们相邻(满足?).但颜色不同(不满足?). 定义2:设G为n个栅格gk,k=1,…n所组成的图
形.若其中任意一个栅格与G中另一个栅格同色连通且 与G以外的栅格非同色连通,则称G为一同色连通区. 在连通区的定义中,n可以为l.在图2中,g?-
g3?g.构成绿色连通区.根据定义1.我们就可以判断某 一
栅格是否属于连通区G.因此G为一集合,其元素就
是互相连通的回色橱格.
1.2同色段
定义3:在意匠图第i行上有颜色为c的n个船格gk (i,c),k=1.…n.如果满足以下条件.则称这n个栅
格为同色段:
gi绿g绿
1
黄g绿
bl黑g-绿r.红2红b2黑
图2扭格的连通
?j一j可排成一连续的整数序列,其中最小列为jl:mln(j"j),最大列为J=max (jl'…j):
?gl(j,j1,c)与其左侧栅格gl_1(i.j.l,ci.1)非同色连通:gr(j,j,c)与其右侧栅格gf+l(i. j.+l,cr+1)非同色连通.
在同色段的定义中n可以为1.由以上定义可以看出同段就是在意匠图上同一行中连在
一
起的颜色相同的栅格.同一行中可能有若干种颜色的同色段,也可能有一个以上的同一种
颜色的同色段.我们用符号s(i,j,,j2.c)表示处于第i行,起始列为j,终止列为j2,颜色为C的
同色段.如果同色段s属于同色连通区G,那么s即为G的一个子集.在团2中,gI.&为一
同色段,g3,各自为一同色段.
从定义3我们不加证明就可以得出以下结论:
同色连通区G的各个行均由同色段组成,因此G也是由同色段组成的.同色段互不相
交.设G由同色段Sk,k=1.…n所组成,则G为,k:1.…n的并,口: G:s……………………………
1.3同色段的连通
定义4;设有同色段sI和s2的颜色相同,如果sl中存在一个栅倍g与s2中任何一个栅格
同色连通,则称同色段S与s2同色连通.
设sl的行数为il,s2的行数为_2,若sl与s2连通,则必有!il—i2i:1.即只有在意匠图上
相邻行的同色段才有可能连通.
图3为用同色段表示的意匠图.图中sl和均为同色段.相郐行的同色段均连通 由定义4可知:同色连通区包含一个以上的同色段时,这些同色段均两两连通. 用反证法很容易证明这个结论.假设%为同色连通区G中的同色段.并且与G中的其
它同色段不连通,那么s中的任何栅格与G中的任何其它的同色段不连通(定义4),因此st中
的任何栅格不为G中的元素(定义2),亦即不为G中的同色段.这与假设矛盾,故上述缩
2g
论成立.
1.4有色连通区
定义5:设有栅格g1(i1.j1,c1)和
g2(i2.j2,c2),如果gl,g2菊足以下条
件,则称gl,gz这二个栅格有色连通.
?0<l<15,O<<15:
?1il一2?1且ljj—j2l?I
如果橱格g1与g有色连通,栅
格g2与ga有色连通.则称栅格gl与
g3亦有色违三I丑.在图2中,gl与l
有色连通,yl与有色连通,因此勘
与rl也有色连通.但轧与bl非有
色连通虽然它们相邻(满足?),但
b,为黑色(不满足?).
定义6:设G为n个襁格gk,k:
图3甩同色段表示的意匠圈
1.…I1所组成的图形,若其中任意一个栅格与G中另一个l扭格有色连通且与G以外的栅格非
有色连通.则称G为一有色连通区.
在连通区的定义中,n可以为1.在图2中.gl,,g3.g..Yl,rl,r2构成有色连通区.有色 连通区G亦为一集合,其元素就是互相连通的有色栅格.
1.5有色段
定义7:在意匠图第i行上有颜色为0<ck<15的n个栅格gI(i.j】_),k=1.…n.如果满
足以下条件.则称这n个栅格为有色段.
?j,…j可排或一连续的整数序列,其中最小列为jl=min(j…j.).最大列为j=max(j, …
j):
?gl(i,jl,1)左侧的栅格g1.1(i,jl_I,0)为黑色;g(i,j,cr)右侧的栅格+l(i.j+l,0)亦为 黑色.
在有色段的定义中n可以为1.由以上定义可以看出有色段就是在意匠图上同一行中连
在一起的颜色不为黑色的栅格.同一行中可能有若干个有色段.我们用符号s({,j1,j)表示
处于第t行,起始刊为j,终止列为jz的有色段.如果有色段s属于有色连通区G.那么s即为
G的一个子集.
1.6有色段的连通
定义8:设有色段为sl和sz.如果sI中存在一个栅格g与sz中任何一个栅格有色连通.劂
称有色段s1与sz有色连通.
设sl的行数为il.sz的行数为i2,若sl与sz有色连通.则必有lil—i2l=1.即只有在意匠
图上相邻行的有色段才有可能连通.
2连通区的数据结构
对意匠圉进行计算机辅助设计的目的是为了利用意匠图的信息控制打版机的运行.因此
意匠图的数据宜采用二维数组,或其压缩的形式存储.但是意匠图上连通区(同色连通或有色
连通)的数据还可以用树结构表示.
图3为一意匠图.其中同色段s1.…sz6形成连通区G.现在我们要把此连通区表示为树结
30
构.首先将G中的每个同色段看作结点.这些结点具有圉4所示的四个域这样我们便得到
Sl,…S26这z6个结点.
行起始列终止列颜色
圈4结点的域
如果以同色段连通的原则连接这些结点.也就是说,如果两个同色段连通,剜将其所对应
的结点相连.我们便得到一个图(graphic).如果在这个图申不存在环路.并且设同色段s!作
为根结点,该图便成为一棵树(见图5).如果在上述图中存在环路.那么将环路中任何一个连
接弧切断,该图仍可成为讨由于意匠图中组成同色连通区的同色段均两两连通(见1.3节),
故其所对应的节点亦两两相连.换而言之.同色连通区的各个同色段与树结点是一一对应的.
按照上述方法.我们可以把意匠图中同色连通区的数据用树结丰暂表示.对于讨的根结点
的选择并无限制,同色连通区中任何一个同色段(一般是光标所在的同色段)都可以当作根结
点.因此表示连通区数据的树结构不是唯一的.
以上方法对意匠图的有色连通区同样适用也就是说将有色段定义为结点,连通的有色
段所对应的结点也相连,任选一结点作为根结点,这样有色连通区的数据也可表示为一树结
构.与同色连通区树结构的区别在于有色段定义为结点时.其域的数目由其包分的同色段的
个数而定.
圈5意匠图所对应的树结构
3图形标记区的实现
所谓图形标记区.就是操作者欲对其编辑的同色或有色连通区.将其同(有)色段的
记
录下来以后.再将连通区改变为白色.这个白色的连通区就叫作图形标记区. 为了实现上述转换,首先将该连通区的数据按讨结构表示,然后从根结点开始进行该树结
31
点的遍历.从而实现连通区到标记区的转换.实际上.树的生成过程即是结点的遍历过程.
错结构是一种递归结构,因此可以用图6所示的递归程序实现指定标记区的运算. 艇——.::.|f.…:/豇
求栅诂g(i.j,cj所在韵已到拭底/尉色段的参数j
,
j,骰\/翅
将j.j.j2.c存入敛组
刷色段}于,
使阿色段各栅藉的c=15
列数出棱
返
在i一1行和i+1行搜索连通的同巴段
并赋给叫
假\—/竺其—l?J
符连通的!司色段的行,到鼗主
压入栈中
当有连通的同色臣时程
,,,笠兰序同色辟行列数出栈递归
并赋给i,j返回主程序
谬用
递归铡用
图6生成坛记区的递归子程序盘圈
囝6中,使同色段颜色变为15这一步很重要.它不但使屏幕上的标记区的栅格变为白色(便
操作者观察)?而且避免了连通的同色段行,列数的重复压栈,也防止了环路的形成.否则程序
将呈现死循环.仔细考察图6的程序.将会发现,该程序并不能生成连通区的树结构.实际上
连通区数据的树结构在程序运行时始终也没有出现.这棵树仅仅存在于我们的观念之中.因
此可称为"虚树".这也就说明了在上一节所讨论的结点的域(见图4)中为什幺没有指向其它
结点的指针域c树既然上虚的,也就无须用指针进行结点的连装.但是虚树的结点(同色段)
却是实的,我们通过二个结点的参数很窑易判断二者是否相连.这样对虚树的结点就可进
行实访问.利用虚树的概念.对结点进行实访问是本程序的特点.虽然不能保证虚树中的每个
结点在遍历时仅访问一次,但对虚树的全部结点均能访问到,而结点与连通区的同色段又是一
一
对应的,这就保证了对于意匠图上任何复杂的连通图形,本程序均可避免出现屏蔽现象.
有色连通区为标记区的子程序与图6中的子程序十分类似.这里不再赘述. 参考文献
1严蔚敏,吴伟民<敷据结构)清华大学出版社1987年8月
32