第五章 图形运算 第一节 线段的交点计算 两条线段求交

Presentation on theme: "第五章 图形运算 第一节 线段的交点计算 两条线段求交"— Presentation transcript:

1 第五章 图形运算 第一节 线段的交点计算 两条线段求交
第五章 图形运算 第一节 线段的交点计算 两条线段求交 设有两线段AB和CD,其端点坐标分别为(xa,ya),(xb,yb)和(xc,yc),(xd,yd),它们所在直线的参数方程分别为：

2 若两线段相交,则交点的参数值,应满足: 即

3 因此,若行列式 表示两线段AB和CD重合或平行。一般做为它们不相交来处理。如果 ≠0,则可求出交点对应的两个参数值:

4 需要注意,只有 , 时两线段才真正相交。否则,交点在两线段或其中某一条线段的延长线上,这时仍然认为是两线段不相交。

5 两线段AB和CD交点的算法 1.〔计算行列式〕 ←(xb-xa)(yc-yd)-(xc-xd)(yb-ya)
若 =0,则两线段重合或平行,可算做无交点,算法结束; 2.〔计算交点参数〕 ←((xc-xa)(yc-yd)-(xc-xd)(yc-ya))/∆ 若 <0或 >1,则无交点,算法结束; ←((xb-xa)(yc-ya)-(xc-xa)(yb-ya))/∆

6 多条线段求交 3.〔计算交点〕x←xa+ (xb-xa),y←ya+ (yb-ya),输出交点(x,y)后算法结束;
寻找这样的算法,其计算工作量要大体上与交点个数成正比,即只对有可能相交的两线段计算交点,对不可能相交的线段不计算交点,使算法有更好的效率。

7 我们称平面内两条线段在横坐标x处是可比较的,如果存在一条通过x的垂直线,此线与两条线段都相交。我们规定一个在x处的"上面"关系为：在x处,线段S1在S2的上面,记为S1>xS2,如果在x处可比较,且S1与垂直线的交点位于S2与垂直线的交点的上面。

8 其中，S2>μS4,S1>νS2,S2>νS4,S1>νS4

9 两线段相交的必要条件,即若两线段相交,则必然存在某个x,使它们在规定的次序关系>x下是相邻的。
规定的次序关系对垂直的线段不适合 两线段相交的必要条件,即若两线段相交,则必然存在某个x,使它们在规定的次序关系>x下是相邻的。 算法从左向右扫描,在扫描过程维持正确的线段间上述次序关系。这种次序关系只能有三种可能的变化方式: 1．遇见某条线段S的左端点,此时S应加入次序关系。 2．遇见某线段S的右端点,此时S应从次序关系中删除。 3．遇到某两条线段S1和S2 的交点,这时在次序关系中S1和S2交换位置。

10 扫描线状态表L中存放按所规定次序关系>x排序的线段的序列。此表初始应为空,在平面扫描过程中当关系>x改变时变化。
算法实施需要两个基本的数据结构: 扫描线状态表和事件点进度表 扫描线状态表L中存放按所规定次序关系>x排序的线段的序列。此表初始应为空,在平面扫描过程中当关系>x改变时变化。 事件点指扫描进行中可能使所规定次序关系>x发生变化的点,存放于事件点进度表E中,该表初始时应是排序的要求交点的各线段端点的坐标。在平面扫描过程中求出的交点,应及时地插入到事件点进度表中。

11 扫描线状态表应能支持以下四个操作: (1) INSERT(S,L),把线段S插入到扫描线状态表L中,注意应插入到适当位置以保持正确的次序关系。 (2) DELETE(S,L),从L中删除线段S。 (3) ABOVE(S,L),返回次序关系中S上面紧接着的线段的编号。 (4) BELOW(S,L),返回次序关系中S下面紧接着的线段的编号。

12 事件点进度表E应能支持以下三个操作: (1) MIN(E),取出表E中的最小元素。 (2) INSERT(x,E),把横坐标为x的一个点插入到表E中,插入要使E中事件点存放保持递增次序。 (3 ) MEMBER(x,E),判定横坐标为x的点是否在事件点进度表E中。

13 算法: 1.〔事件点进度表E初始化〕将输入待求交点的n条线段的2n个端点按x,y字典式排序后存放于表E中;
2.〔准备收集交点〕A← ;{A是一集合,初为空,准备存入找到的交点;} 3.〔平面扫描〕若表E不为空,则进行(3.1)~(3.3)循环。直到表E为空时算法结束。 3.1〔取出当前事件点〕P←MIN(E)； 3.2〔当前事件点处理〕考查当前事件点P,分三种情况: (1) 若P是边S的左端点,则做：INSERT(S,L);

14 S1=ABOVE(S,L); S2=BELOW(S,L); 若S和S1相交,则求出的交点送入集和A中; 若S和S2相交,则求出的交点送入集和A中; (2) 若P是边S的右端点,则做： 若S1和S2相交于点P的右边,则求出的交点送入集和A中； DELETE(S,L)； (3) 若P是边S1和S2的交点,且在P的左边S1=ABOVE(S2),则做

15 S3=ABOVE(S1,L); S4=BELOW(S2,L); 若S3和S2相交，则求出的交点送入集合A中； 若S4和S1相交，则求出的交点送入集合A中； 在L中交换S1和S2的位置； 3.3 〔处理找到的交点〕若集合A不为空，做下面循环，直至A为空： 取出集合A中一个交点，其横坐标是x； 若MEMBER(x,E)为FALSE,则输出此交点， 并做 INSERT(x,E);

16 设有三条线段S1，S2，S3,它们的坐标如下 (1,1),(5,3,),(2,3),(4,1),(6,4),(8,2).要计算所有交点。

17 算法初始形成的事件点进度表E，可有形式 (((1,1),S1左端点)，((2,3),S2左端点) ，((4,1),S2右端点)，((5,3),S1右端点) ，((6,4),S3左端点)，((8,8),S3右端点))

18 发生S1,S2求交,求出交点(3,2)插入E((4,1),S2右端点)前
算法步骤 从表E前面取出的扫描到达的事件点P 扫描线状态表L 工作解释 3.2(1) ((1,1),S1左端点) (S1) ((2,3),S2左端点) (S1,S2) 发生S1,S2求交,求出交点(3,2)插入E((4,1),S2右端点)前 3.2(3) ((3,2),S1和S2的交点 (S2,S1) 3.2(2) ((4,1),S2右端点) ((5,3),S1右端点) ( ) ((6,4),S3左端点) (S3) ((8,8),S3右端点)

19 第二节 多边形表面的交线计算 设两个要求交线的多边形表面都是凸多边形表面,分别由它们的顶点坐标逆时针方向的序列确定,即约定按顶点序列前行时内部在左侧。 根据顶点坐标求出两个多边形表面分别所在平面的方程,再根据平面方程计算交线,最后,还要确定出交线同时在两个多边形表面内部的部分

20

21 求平面方程 采用多个顶点位置坐标来计算平面方程可以减少由于不共面而引起的偏差。 设要求出通过若干顶点的平面方程Ax+By+Cz+D=0,即要定出系数A,B,C,D,可采用如下做法 平面方程Ax+By+Cz+D=0的系数A,B,C与该平面上多边形分别在x=0,y=0,z=0三个坐标平面上投影的面积成比例

22 多边形在z=0平面上投影的面积S可如下求出:
式中若i=n则j=1,否则j=i+1。 类似地可计算多边形表面在x=0和y=0平面上投影的面积,从而确定A,B,然后D可通过代入平面上一点坐标数值来求出。

23

24 S= [(y1+y2)(x1-x2)十(y2+y3)(x2-x3） +(y3+y1)(x3-x1)]
于是有 S= [(y1+y2)(x1-x2)十(y2+y3)(x2-x3） +(y3+y1)(x3-x1)]

25 若给出空间若干点的坐标(x1,y1,z1),(x2,y2,z2),…
若给出空间若干点的坐标(x1,y1,z1),(x2,y2,z2),….(xn,yn,zn),注意这里没有要求这些点共面或围成了凸多边形,都可以求出通过或接近这些点的一个平面方程Ax+By+Cz+D=0:

26 平面方程的求交 D=-Ax1-By1-Cz1 式中若i=n,则j=1,否则j=i+1 A1x+B1y+C1z+D1=0

27 两平面重合或平行,一般算没有交点 分别对每个多边形表面各边相应的线段,计算它与另一个多边形表面所在平面的交点。注意这里是求线段与平面的交点,即交点在线段延长线上时算不相交。假定两个多边形表面都是凸的,故共可以交出四个交点。

28 线段与平面的交点计算 空间线段两个端点的坐标(x1,y1,z1)和x2,y2,z2)给出,平面方程Ax +By+Cz+D=0。

29 代入平面方程,得: A(x1+(x2-x1)t)+B(y1+(y2-y1)t)+C(z1+(z2-zl)t)+D=0 整理得到: [A(x2-x1)+B(y2-y1)+C(z2-zl)]t=-(Ax1+By1+Cz1+D) 于是知道,若 A(x2-x1)+B(y2-y1)+C(z2-z1)=0 则所给线段在平面上或与平面平行,没有唯一确定的交点。否则,交点对应的参数t可以求出:

30 第三节 平面中的凸壳算法 凸壳 包含一个平面点集的最小凸区域 凸区域指要求区域内任意两点的连线仍在该区域内。
设S是平面上n个点的集合,则S的凸壳是一个凸多边形,它包含所有n点且面积最小。事实上求点集S的凸壳就是要在S中选出壳上的点并排出围成凸多边形的次序。

31 Graham扫描算法 处理的思路是设想有一内点O并且不妨设想O就是坐标原点,这时点集S中所有各点相对轴OX有一个倾角。所有各点按倾角递增排序后,如果某一点不是壳上顶点,则它必然在两个壳顶点与点O形成的三角形内部。 Graham扫描的实质是围绕已经按"倾角"排序的各顶点进行一次扫描,在扫描过程中消去在凸壳内部的点,留下以希望次序排列的壳顶点。

32 由于是按倾角递增排序,可知若连续三个顶点P1,P2,P3是一个“右转”，则P2是一个应去掉的内点。

33 对给出的三点P1,P2, P3 ,设它们的坐标是(x1,y1),(x2,y2),(x3,y3),这时要判断三点在P2处形成一个右转还是左转,可以计算下面的行列式
其中△给出的是带有正负号的三角形P1P2P3面积的2倍,因此若△>0,则P1,P2,P3是左转; △ <0,则是右转; △ =0,则三点共线。

34 Graham扫描算法 实现此算法可选点集S中x坐标最小的点为内点O,设想过O有一条向右的射线,对其余各点,相对该射线计算倾角然后再排序。
1.〔倾角排序〕选出输入点集S中x坐标最小的点,若这样的点不唯一则再由其中选出y坐标最小的点,设为O。设想有一条从O向右的射线OX,对点集中其余每一点P,计算倾角POX,再按倾角排序,得点序列Q1=O,Q2,Q3…,Qn; 2.〔准备扫描〕v←Q1;

35 3.〔扫描〕若NEXT(v)≠Q1,则循环执行下面操作,至NEXT(v)=Q1时止,此时点序列中剩下排成凸多边形的壳上顶点,算法结束。
若三个相继的点v,NEXT(v),NEXT(NEXT(v))形成一个左转,则v←NEXT(v);否则,先删除NEXT(v),再做v←PRED(v); NEXT(v)和PRED(v)是两个函数,其值分别为算法操作的点序列中v的下一点和前一点。这里取下一点和前一点时认为点序列是首尾相接的,即若v是点序列中第一点,则PRED(υ)是点序列中最后一点;若v是最后一点,NEXT(v)是第一点。

36 P3 P0P1P2左转， P1P2P3右转， P0P1P3右转。 P0 P1 P2

37 倾角计算 记P点坐标为(Xp,Yp),O点坐标(X0,Y0),这个角度数可如下简单地计算: B=yp-y。若B≥ 0则角度数=1-A,否则角度数=3+A。这里A是向量OP与OX向上单位向量的内积,因此是倾角的余弦数值。B用以判断该倾角是否大于180度。

38 Jarvis行进 算法 想法是若相继两点是一条凸壳多边形的边,则对于过该边的直线,所有点集中的凸壳中的顶点在该直线同侧。因此若找到pq是壳上一边,则以q为端点的下一条壳边qr可以如下求出：计算点集中其余各点相对q点发出沿向量pq向的射线的倾角,若倾角最小者对应的点是r,则qr是下一条壳边 寻找开始行进的第一条壳边,可以选出点集中按x,y坐标字典式次序的最低点,该点必定是一个壳顶点。可从该点引一条竖直向下的射线,在此做一个行进步就找到了第一条壳边。

39

40 Jarvis算法 1.〔准备〕v0←点集S中按x,y字典次序最小的点; d←竖直向下的一个方向向量; 点v0送入收集凸壳顶点的队列Q中;
S1←S-{ v0}; u←v0 2.〔一步行进〕v1←Wrapping(u,d,S1); 3.〔准备下次〕若v1≠v0,则做: v1接入队Q后部; S1 =S-{u,v1}; d←从u到v1的一个方向向量;

41 u←v1 返步2。 4.〔结束〕壳顶点已经全部存入队Q中,算法结束. 其中第2步引入函数Wrapping来实现一步行进。此函数的工作是,对S1中所有各点,相对自u发出方向为d的射线,计算所成倾角。在所有倾角中取最小,若有多个则选与u距离最远的那个,它对应的点为函数的返回值。因此在步2求得的v1是一个行进步找到的下个壳顶点。 Jarvis 若点集S中只有较少数点在壳上,则算法效率很高。若点集S中绝大多数点都在壳上,算法的效率一般来说就不如Graham扫描了。

42 第四节 包含与重叠 简单多边形的包含算法 平面上的简单多边形是不相邻的边不能相交的多边形,设它用顶点坐标的逆时针序列（x0,y0）,(x1,y1),…,(xn-1, yn-1)确定,即沿顶点序列前行时内部在左侧。 对平面上坐标为(xp,yp)的任意一点P,包含性检验问题是判断它是否在所给出简单多边形的内部。

43 一个简便的判断方法是由P做竖直向下的射线,计算此射线与多边形各边交点的个数。

44 当由点P竖直向下的射线恰好通过多边形的顶点或某一边时,交点计数可采取简单的"左闭右开"法来处理,即:当多边形一边的两个顶点的x坐标都小于或等于点P的x坐标时,相应交点不计算在内。

45 简单多边形包含性检验的算法 1.〔准备〕xn←x0,yn←y0,m←-1,i←0; 2.〔排除必不相交情形〕若下列条件有一个成立,则到4。
2.1 xp<xi并且xp<xi+1: 2.2 xp≥xi并且xp≥xi+1; 2.3 yp<yi并且yp<yi+1; 3.〔计算交点〕y=yi+(xp-xi)(yi+1-yi)/(xi+1-xi),分二种情形: (1)若y=yp,则点P在多边形边界上,算法结束; (2)若y<yp",则m←(-1)•m; 4.〔结束判断〕i←i+1,若i<n",则返回到2,否则算法结束,此时若m=-1则点P在多边形外部,m=1则在内部。

46 凸多边形的包含算法 沿逆时针行进，凸多边形内部均在其各边所在直线的左侧,因此只要对询问点P,逐个检查它是否在凸多边形每一边所在直线的左侧就可.

47 判断坐标为(xp,yp)的点P是在直线的位置
设直线的端点为(x1,y1)和(x2,y2),直线方向是由(x1,y1)到(x2,y2)的方向。 直线的方程记为Ax+By+C=0,则有: A=y2-y1,B=x1-x2,C=x2y1-x1y2 计算D: D=Axp+Byp+C 若D<0,则点在直线左侧; 若D>0,则点在直线右侧; 若D=0,则点在直线上。

48 再进一步,引人“折半查找”思想,写出下面更有效率的算法。
设算法的输入是一个凸多边形的顶点序列Po,P1,…,Pn-1 ,询问点P,可有包含性检验算法如下:

49 1.〔准备〕i←1,j←n-1; 2.〔查找是否结束〕若j-i=1则到4,否则继续; 3.〔折半查找〕k←[(i+j)/2],检查询问点相对直线PoPk的位置关系,分三种情况: 3.1 在直线上,若点在线段PoPk上或内部,则点在原凸多边形内部,,若点在线段PoPk延长线上,则在原凸多边形外;输出回答后算法结束; 3.2 在左侧,i←k返回步2 3.3 在右侧,j←k返回步2 4.〔最后检查〕检查询问点P对△P0PiPj的包含性,若在内则也在原凸多边形内部,若在外则也在原凸多边形外部,输出回答后算法结束.

50 凸多边形重叠计算 两个凸多边形的重叠问题,这也就是对两个凸多边形求相交部分的问题。
现在约定凸多边形指它的边界和内部,凸多边形仍用顶点坐标的逆时针方向序列确定。 设给出的两个凸多边形P和Q的顶点序列分别是P1,P2,…,PL和Q1,Q2,…,Qm。为说明简便,假设P的边界上不包含Q的项点,Q的边界也不包含P的顶点。

51 有两个问题需要解决,一个是如何有次序地求出各边的所有交点,一个是如何排列求出交点和原凸多边形的顶点,形成交得凸多边形的顶点序列。
为了有次序地求出交点,可以在两个多边形边上交替地前进,原则是在哪个多边形的边上可能有交点就等待,在另一个多边形的边上前进。初始从对边P0P1与Q0Q1的求交开始,注意所有求交是线段的求交。这里规定了P0=PL,Q0=Qm。

52

53 求矢量积Pi-1Pi×Qj-1Qj的z分量,若该分量大于等于0,是前四种情形,小于0是后四种情形。
(1) (2) (3) (4) (5) (6) (7) (8) Pi在Qj-1Qj 左 右 Qj在Pi-1Pi 前进的多边形 Q P 区分前四种情形还是后四种情形 求矢量积Pi-1Pi×Qj-1Qj的z分量,若该分量大于等于0,是前四种情形,小于0是后四种情形。

54 Advance S←Pi-1Pi×Qj-1Qj的z分量;分二种情况处理,然后算法就结束; 1. 若S≥0,则做 若Pi在Qj-1Qj左并且Qj在Pi -1Pi左(b),或者Pi在Qj-1Qj右并且Qj在pi-1Pi左(d),则i前进1,否则j前进1; 2. 若S<0,则做 若Pi在Qj-1Qj右并且Qj在Pi-lPi左(e),或者Pi在Qj-1Qj右并且Qj在Pi-1Pi右(g),则i前进1,否则j前进1; 算法中"i前进1",指若i<l,则前进1是i+1;若i=L,则前进1是1。这因为多边形P是首尾相接的。类似地"j前进1",j<m时是j+1;j=m时是1。i总在多边形P上前进,j在Q上前进。

55 为了正确排列求出的交点并加入原两个凸多边形部分顶点以形成相交的凸多边形,可以在每求出一个交点时进行一次输出。
求出的第一个交点可只做一下记录,如果在以后交替前进求交点的过程中再次求出与第一次求得相同的交点,就知道整个求交过程已经结束了。 求得一个不是第一个的其它任何一个交点时,为形成交得凸多边形顶点序列,要区分边Pi-lPi是进入多边形Q,还是走出Q两种情况。

56 Pi-1Pi正进入多边形Q,此时应输出本次求出交点前，上次求得交点后的多边形Q上的各顶点，然后再输出本次交点，因为这些点是交得凸多边形的顶点。

57 Pi-1Pi是走出Q,这时应输出本次求出交点前，上次求得交点后的多边形P上的各顶点, 再输出本次交点。
这两种情况区分,可通过检查Pi在直线Qj-1Qj的左侧还是右侧来确定。 Output 若本过程是第一次被调用,则做: R0←第一次求得的交点,若Pi在Qj-1Qj左则 t←i,否则t←j； 否则做: 若Pi在Qj-1Qj左,则做: 输出多边形Q上t至j-1各顶点,输出当前交点,t←i;

58 否则做: 输出多边形P上t至i-1各顶点,输出当前交点,t←j;
两个凸多边形求交的完整算法: CONVEX POLYGON INTERSECTION 1.〔准备〕i←1,j←1,k←1,P0←PL,Q0←Qm; 2.〔交替前进求交〕若k≤2*(l+m)并且所求出当前交点不是第一次求得交点R0,则做 2.1~2.3循环: 2.1 若线段Pi-1Pi与Qj-1Qj相交,则调用 Output; 2.2 调用Advance; 2.3 k←k+1;

59 3.〔结束判断〕若在步2找到过交点,则交得凸多边形顶点序列已在调用Output过程中输出,算法结束;
否则,做如下检查: 若P1包含于多边形Q中,则输出P包含于Q中,算法结束;  若Q1包含于多边形P中,则输出Q包含于P中,算法结束; 若上述两个检查都不成功,输出交为空,两多边形分离,算法结束;

60 交点个数最多为2(l+m)个

61 第五节 简单多边形的三角剖分 简单多边形做三角剖分,是要求选出完全在内部又互不相交的一组对角线，把整个多边形划分成一些三角形。这里对角线是不相邻顶点间的连线,选出的对角线的集合称为是简单多边形的三角剖分。

62 对任意一个简单多边形,其三角剖分不是唯一的。
事实1 简单多边形必有一条对角线完全在其内部。 事实2 简单多边形上必有连续的三个顶点A,B,C,使对角线AC完全在其内部。

63 必有完全在内部的对角线

64 简单多边形三角剖分的算法:考查连续三个顶点A,B,C,若AC完全在多边形内部,则可输出△ABC为一个剖分后形成的三角形,删除点B后再对少了一个顶点的多边形继续进行。
简单多边形的顶点序列为P0,P1,Pn-1,那么算法可描述如下: SIMPLE POLYGON TRIANGULATION 1.〔准备〕Q0←P0; 2.〔剖分〕若n>3，则做2.1~2.2,否则转到步3: 2.1 Q1←点序列中Q0的下一个顶点;Q2←点序列中Q1的下一个顶点; 2.2 若Test(Q0,Q1,Q2)为真,则做: 输出△Q0Q1Q2;

65 从点序列中删除顶点Ql; n←n-1; 返回步2开头; 否则做Q0←Q1,返回步2.1; 3.〔最后输出〕输出点序列中剩下三点为最后一个三角形,然后算法结束。 函数Test是对△Q0Q1Q2进行检查，分两步实现,第一步检查Q0,Q1,Q2是否是一个在Ql的左转,若不然,是右转,则Q0Q2在多边形外部而可以回答假而结束。第二步可对原多边形中除去Q0,Q1,Q2这三点之外的其它点，对每一点都考查它对三角形的包含性,若有一点被包含则就可以回答假而结束,只有其它点都在三角形外部时才能回答真而结束。

66 最小权三角剖分或最小三角剖分 如果一个三角剖分中选取的对角线的总长 度最小。 任意的凸多边形最小三角剖分

67 事实3 在n边形(n≥3)的任意一种三角剖分中,每一对相邻顶点中至少有一个顶点是某条对角线的端点。
因为若相邻顶点Vi,Vi+1都不是某条对角线的端点,则区域(Vi-1,Vi,Vi+1,Vi+2)中没有对角线,因而也就没有被三角剖分。 事实4 如果ViVj是三角剖分的一条对角线,则一定存在某顶点Vk,使得ViVk和VkVj是多边形的边或对角线。 因为若不然,一定存在以ViVj为边界的某个区域没有被三角剖分。

68 顶点序列V0,V1--,Vn-1确定的凸n边形的最小三角剖分
挑选两个相邻顶点比方选V0和V1,由事实3知道在最小三角剖分中,必有另一顶点Vk,或者使V1Vk是对角线,或者使V0VK是对角线。 对有n个顶点的多边形，Vk的选取方法有n-3种。 对于每个可能的Vk用对角线V0Vk(或V1Vk)把原多边形剖分成两个较小的多边形,这样原问题就被分成为两个子问题。 往下需要寻找分成的两个较小凸多边形的最小三角剖分。（递归）

69 选择剖分方法,使得每次剖分后所得的子问题只涉及一条原多边形的对角线。
由事实4知在最小剖分中的对角线一定与另外一点构成三角形。

70 现在一般地说明所要使用的剖分方法。引入记号Sis,表示一个子多边形Vi,Vi+1,…,Vi+s-1的最小三角剖分问题。子多边形由Vi开始的S个顶点按顺时针向排列围成。
每个子问题Sis中都仅涉及原多边形一条对角线。为了解Sis,必须考虑如下三种情况: 1. 选择顶点Vi+S-2,这时构成一个三角形ViVi+S-2Vi+S-1,得到一个子问题Si,S-1 2. 选择顶点Vi+1,这时构成一个三角形ViVi+1Vi+S-1,得到一个子问题Si+1,S-1。 3. 对2≤k≤S-3,选择Vi+k这时构成一个三角形ViVi+kVi+S-1,得到两个子问题Si,k+1和Si+k,S-k。

71 实际上可以把三种情况概括为一句话,即对1≤k≤S-2,把Sis分解成两个子问题Si,k+1和Si+k,S-k。容易验证k=1和k=S-2时,各自有一个子问题不成其为问题,但这不影响一般的讨论。

72 CiS记子问题SiS的解 CiS的公式如下: CiS=min[Ci,k+1+Ci+k,S-k+D(ViVi+k)+D(Vi+kVi+S-1)] 1≤k≤S-2 如果VpVq是对角线,则D(VpVq)是它的长度;若VpVq是原多边形的边,则D(VpVq)=0;如果S<4,则CiS=0。这因为CiS是最小三角剖分中引人对角线的总长度,原多边形的边不是对角线,当S<4时也不必引入对角线。

73 对前面说明的凸七边形,要计算的各CiS,有 0≤i≤6, 4≤S≤6。可用填表的方式逐个计算。
C06=53.54 C16=55.22 C26=57.58 C36=64.49 C46=59.78 C56=59.78 C66=63.62 C05=37.54 C15=31.81 C25=35.49 C35=37.74 C45=45.50 C55=39.98 C65=38.09 C04=16.16 C14=16.16 C24=15.65 C34=15.65 C44=22.69 C54=22.69 C64=17.89

74 C65的计算由公式应该计算下面三个值: C62+C04+D(V6V0)+D(V0V3) C63+C13+D(V6V1)+D(V1V3) C64+C22+D(V6V2)+D(V2V3) 代入数值进行计算，注意到 D(V6Vo)=D(V2V3)=0,D(V6V2)=26.08 D(V1V3)=16.16,D(V6V1)=22.36,D(V0V3)=21.93 C04,C64在表中己求出,C62,C63,C13,C22为0 于是算出上述三式的值分别为 38.09,38.52,43.97。所以知道C65=38.09,可以把这个值填入表中,并知道按第一式子问题S65分解出一个子问题S04,另一个S62不成为子问题。

75 最小三角剖分问题的求解适合采用动态规划方法。
顶点坐标序列V0,V1,Vn-1给出的凸n边形,求最小三角剖分的动态规划算法的填表过程: 1.对j≤3,对i=0到n-1,令Ci,j=0; 2.对j=4到n-1,循环做:对i=0到n-1循环做: 2.1 对k=1到j-2 计算Ci,k+1+Ci+k,S-k+D(ViVi+k)+D(Vi+kVi+j-1) 2.2 Ci,j←2.1步计算各值中的最小值; 以上过程完成填表,其计算是利用公式CiS 。

76 结果C0n也用公式Cis计算: 1. 对k=1到n-2, 计算C0,k+1+Ck,n-k+D(V0Vk )+D(VkVn-1); 2. C0n←第1步计算各值中最小者;

77 以凸七边形为例,计算C07时,确定它的k值是k=5,即C06+C52+D(V0V5)+D(V5V6)|是最小的。这样应引入对角线V0V5,原问题分解为子问题S06和S52。S52已经是三角形,不必再考虑了。 再看C06,它对应k=2,于是引进对角线V0V2和V2V5,子问题S06分解为S03和S24。S03已是三角形。最后要看C24,对应k=1,于是引进对角线V3V5,子问题S24分解为S22和S33,其中S33是三角形,而S22是边。整个过程已经完成,过程中引入各对角线就构成原问题的最小三角剖分

78

79 思 考 题： 120页：1题、15题，