计算机图形学 第3版 第6章 形体的表示及其数据结构.pptx

2024/10/11;第六章形体的表示及其数据结构;第六章形体的表示及其数据结构;二维图形的边界表示

带树法

带树是一棵二叉树,树的每个结点对应一个矩形带段,这样每个结点可由八个字段组成,前六个字段描述矩形带段,后二个是指向两个子结点的指针,即矩形带段的起点是(xb,yb),终点是(xe,ye)。相对从起点到终点的连线,矩形有两边与之平行,两边与之垂直,平行两边与之距离分别为wl和wr。;设表示曲线有5个点(3,7)(9,12),(15,4),(18,5),(20,7),取分辨率w0=1,则上述算法构造的带树;设要表示的曲线是由经过适当选取已确定的一组离散点P0,P1,…,Pn序列给出,则生成表示曲线的分辨率为w0的带树的算法,可简略描述如下:

BINARY*Create(float*P,inti,intj，floatW){

/*BINARY带树节点类型,P[i]至P[j]描述折线表示的曲线,W为分辨率*/

Search(P,i,j,wl,wr);//确定P[i]至P[j]所有点所形成的矩形带段的宽度

root=new(BINARY);//获取带树节点

CBINARY(root,wl,wr,P,i,j);//构造根节点

if(wl+wr=W)returnroot;//返回带树根节点

else{

k=maxdis(P,i,j);//找出距Pi与Pj连线垂直距离最远的点Pk

t1=Create(P,i,k,W);//构造P[i]至P[k]点间的带树

t2=Create(P,k,j,W);//构造P[k]至P[j]点间的带树

Left(root,t1);//t1作为root左子树

Right(root,t2);//t2作为root右子树

return(root);//

}

};带树法解决曲线的问题：

①以不同的分辨率显示用带树表示的曲线

设给出允许的分辨率为w,表示曲线的带树的分辨率为w0,并设w0≤w,则显示算法如下:

(1)根结点

若当前正考查结点的W=wl+wr≤w,

则显示该结点对应的矩形带段;

否则,即Ww

则转去分别考查该结点的左右两个子结点,

(2)对子结点做同样的处理。

左右子结点都被显示的结点就认为是被显示了,按此看法,显示带树表示的曲线就是显示带树的结点。;voidDisplay(BINARY*root,floatW){

//BINARY带树节点类型root带树根指针,W为显示分辨率

if(Width(root)=W){//wl与wr之和函数

DisplayLine(root);//显示带树为两端点线段

return;

}else{

Display(root-left,W);//显示左子树

Display(root-right,W);//显示右子树

return;

}

}

;②利用带树求曲线相交

两个矩形带段S1和S2??位置关系有如下三种:

(1)不相交。

(2)良性相交,即S1的与起点至终点连线平行的两条边都与S2相交,S2的与起点至终点连线平行的两条边也都与S1相交。

(3)可能性相交,这时不是良性相交,但也不是不相交。;设表示要求交两曲线的带树己构造得足够精确,即在树叶一层,来自不同带树的矩形带段或是不相交或是良性相交,而没有可能性相交出现。

两树T1和T2表示的两条曲线是否相交的算法叙述如下:

算法：

1.若T1和T2对应的矩形带段互不相交,那么它们代表的曲线不相交;

2.若T1和T2对应的矩形带段良性相交,那么它们代表的曲线相交;

3.若T1和T2对应的矩形带段可能性相交,且T1的面积大于或等于T2的面积,那么分别执行T2与T1的左右两个儿子结点的相交性检查。;4.若T1的面积小于T2的面积,则把它们位置对换一下再如上进行两个检查。

4.1.若左右两个子节点检查的结果都是不相交,则认为所表示曲线不相交;

4.2.若左右两个子节点检查中有一个是良性相交,则认为所表示曲线相交;

4.3.若不是上述两情形,即出现可能性相交,则对可能性相交的两个矩形带段中面积较大者,取其对应结点的两个子结点,如此进行可直到树叶那一层。;③如何确定一点是否在一封闭曲线内

从该点引射线与区域边界相交的次数为奇数，点在区域内，否则点在区域外。

判别两曲线相交：一条射线（宽度为0的带树，与表示曲线的带树求交，交点的个数即为带树良性相交次数。

;带树法的优点：

1. 用带树法表示曲线对提高计算效率是有帮助的。

2.两个带树对并、交等运算是封闭的。

3.与用像素阵列来表