《计算机图形学》课件——第5章 图形运算.pptVIP

对于每个可能的Vk用对角线V0Vk(或V6Vk)把原多边形剖分成两个较小的多边形,这样原问题就被分成为两个子问题。 往下需要寻找分成的两个较小凸多边形的最小三角剖分。（递归）V6V5V4V3V2V1V0V0V6V6V5V4V3V3V2V1V0V3V6V5V4V3V2V1V0 选择剖分方法,使得每次剖分后所得的子问题只涉及一条原多边形的对角线。 由事实4知在最小剖分中的对角线一定与另外一点构成三角形。V0V6V6V5V4V3V3V2V1V0V3 引人记号Sis,表示一个子多边形Vi,Vi+1,…,Vi+s-1的最小三角剖分问题。子多边形由Vi开始的S个顶点按顺时针向排列围成。（图中S04,S34） 解Sis,必须考虑如下三种情况: 对1≤k≤S-2,选择Vi+k(例如k=3,s=7)这时构成一个三角形ViVi+kVi+S-1,得到两个子问题Si,k+1和Si+k,S-k。V6V5V4V3V2V1V0 对1≤k≤S-2,选择Vi+k(例如k=4)这时构成一个三角形ViVi+kVi+S-1,得到两个子问题Si,k+1和Si+k,S-k。 1.当k=S-2时，选择顶点Vi+S-2,这时构成一个三角形ViVi+S-2Vi+S-1,得到一个子问题Si,S-1 2.当k=1时，选择顶点Vi+1,这时构成一个三角形ViVi+1Vi+S-1,得到一个子问题Si+1,S-1。 V6V5V4V3V2V1V0V6V5V4V3V2V1V0V6V5V4V3V2V1V0CiS记为子问题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;若S4,则CiS=0。这因为CiS是最小三角剖分中所有对角线的总长度,原多边形的边不是对角线,当S4时,无对角线。V6V5V4V3V2V1V0多边形v0,v1,v2,v3,v4,v5,v6的顶点坐标如下:(6,2),(3,5),(5,11),(10,15),(18,11),(21,7),(12,2)。要计算的各CiS,有0≤i≤6,4≤S≤6。可用填表的方式逐个计算。C07=44.27C06=36.26C16=35.22C05=22.06C15=25.81C25=23.82C04=9.06C14=12.21C24=13.00C34=10.82如,对表中C65的计算由公式(1)应该计算下面三个值:C62+C04+D(V6V0)+D(V0V3)C63+C13+D(V6V1)+D(V1V3)C64+C22+D(V6V2)+D(V2V3)代入数值进行计算，注意到D(V6V0)=D(V2V3)=0,D(V6V2)=11.40,D(V1V3)=12.21,D(V6V1)=9.49,D(V0V3)=13.60,C04,C64在表中己求出,C62,C63,C13,C22为0,于是算出上述三式的值分别为22.66,21.7,20.46。所以知道C65=20.46,可以把这个值填入表中,并知道按第一式子问题S65分解出一个子问题S04,另一个S62不成为子问题。C65=20.46C04=9.06C64=9.06C07C06C16C05C15C25C04C14C24C34C03=0C13=0C23=0C33=0C43=0C02=0C12=0C22=0C32=0C42=0C52=0C01=0C11=0C21=0C31=0C41=0C51=0C61=0最小三角剖分问题的求解适合采用动态规划方法。voidMin_Polygon_Triangulation(Pointp[][2],intm){/*P存储多边形顶点坐标m为顶点数*/ doubled[m][m],cc,c