第六章形体表示及其数据结构.ppt

第六章 形体的表示及其数据结构 ;第一节 二维形体的表示 ; 设已经用某种方法取得了曲线上足够多的点,使连接那些点的折线可以很好地表达该曲线。问题是:怎样在其中选择尽可能少的点,使选出的点仍能较好地表达原曲线。具体地说,使选出的点满足以下二条准则: (1)共线性 设Pj和Pk是选出的两点,则在Pj到Pk之间所有点到直线PjPk的垂直距离,应小于某个预先给定的限制阈值ε0,这里ε00,是一个可以由应用问题需要而确定的很小的正数。若不小于ε0,应寻找距离为最大之点并考虑是否可以在该点将这一段分裂为两段。 ; (2)设选出的连续三点是Pi,Pj,Pk,则向量PiPj与PjPk的夹角α的绝对值,应大于某个预先给定的限制阈值α0。,若小于α0,则Pj不应选取而应考虑是否能将Pi至Pj和Pj至Pk两段合并。 ; 设有曲线上n+1个点的坐标序列,各点依次编号为0,1,2,…,n;为使删去各点距留下前后二点所形成直线的距离不很大而预先给定的阈值ε0;为使选出连续三点所成向量夹角不很小而预先给定的阈值α0;参数k0表示每次向前检查k0个点。 ;1.〔初始化〕 i←0,j←0,k←k0,输出点编号0,s←1。{i记最近己选之点,初始起点0为必选,j记待检查之点,算法中保持i≤j,待检查线是点j到k的直线。} 2.〔共线性检查〕检查点j到k间各点共线性。若不能通过,距离直线PjPk最远的点是m,则k←m返回本步开头。否则继续。{本步必能通过,因最坏在k=j+1时能通过。} 3.〔暂定j前后两线方向〕L2←点j到k的方向,若i=j则L1←L2,到6;否则继续。{L2是暂定找到从j向后的新线方向,L1是前次找到原有线方向。};4.〔向量夹角检查〕检查Pi,Pj,Pk三点形成二向量L1和L2的夹角的绝对值,若可以通过即应发生合并,做j←i然后返2,否则继续。{本步检查通过即点j不能选取,而要检查原i到k的直线。} 5.〔找到一个选取点〕i←j,L1←点j到k的方向,输出点编号j,s←s+1。 6.〔准备下次〕j←k,k←k+k0,若kn则k←n,若j≤n-1则返2,否则继续。 7.〔最后取点〕输出点编号n,算法结束。;P0;带树法 带树是一棵二叉树,树的每个结点对应一个矩形带段,这样每个结点可由八个字段组成,前六个字段描述矩形带段,后二个是指向两个子结点的指针, 即矩形带段的起点是(xb,yb),??点是(xe,ye)。相对从起点到终点的连线,矩形有两边与之平行,两边与之垂直,平行两边与之距离分别为wl和wr。 ;; 设要表示的曲线是由经过适当选取已确定的一组离散点P0,P1,…,Pn序列给出,则生成表示曲线的分辨率为w0的带树的算法,可简略描述如下: 1. 找出由起点P0,终点Pn确定的矩形带段,其中包含P0至Pn的全部点,构造此矩形带段的对应结点并令为根。 2. 找出P0至Pn之间距离连线P0Pn为最远的点Pk,然后对P0至Pk和Pk至Pn这两组点分别做与步1中相同的构造矩形带段及对应结点的操作,产生的两个结点,分别是根的左右子结点。 3. 反复执行上述操作,直到所产生结点的w=wl+wr ≤w0。这样的结点是叶结点。 ;BINARY *Create(float P,int i,int j，float W) /* BINARY带树节点类型 P[i]至P[j]描述折线表示的曲线 W为分辨率 */ { Search(P,i,j-i+1,wl,wr); //确定P[i]至P[j]所有点所形成的矩 形带段的宽度 root=new(BINARY); //获取带树节点 CBINARY(root,wl,wr,P,i,j); //构造根节点 if (wl+wr=W) return root; //返回带树根节点 else { maxdis(P,i,j,k);//找出距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);// } }; 设表示曲线有5个点(3,7)(9,12),(15,4),(18,5),(20,7) ,取分辨率w0=1,则上述算法构造的带树; 以不同的分辨率显