基本几何02-几何计算.ppt

2002年10月24日,上海交通大学计算机系何援军,1,第4章基本几何,之二几何计算,2,4.7几何计算,3,4.7.1概述,从数学上解决直线和圆弧等基本几何元素的相交问题并不困难，只涉及到直线和直线，直线和圆弧，以及圆弧和圆弧的相交，相切计算。许多图形系统都采用某种方式解决了这个问题，也投入了实际使用。只是程序系统所占有的空间、计算效率的高低、使用的方便性、程序和程序系统的适应性上不同而已。,4,4.7.1概述,由于使用频繁，直线圆弧系统仅考虑其准确性是远远不够的，而要着重考虑系统的效率及其可用性。前者要求其各个子程序的设计具有较高的质量，不仅要有数学处理的严密性，而且要用较少的步骤，较快的途径得到结果。后者考虑的是：在问题有多个解的情况下，如何使用户能够方便、直观地加以选择。,5,4.7.2几何计算的基本策略,在解决基本几何的相交计算时，掌握一些技巧往往很有效。在标准坐标系下求解；（通过坐标变换）采用几何计算，避免代数运算。,6,4.7.2基本策略在标准坐标系下求解,圆心在坐标原点的圆（弧）的求解公式往往比较简单；可以通过坐标变换将求解的基本几何转换到标准坐标系下：可先将坐标系作平移将新坐标系原点移到一个圆弧的中心；或通过平移和（或）旋转使新的坐标轴沿着给定直线的方向；或通过平移和（或）旋转使新的坐标轴沿着两个弧中心的方向。等等,7,例：给定三点作一圆（1）,题：求通过3个点P1，P2，P3的圆解：设所求圆的圆心为Pc(xc,yc)，半径为R。直接的解法是解以下三个非线性联立方程：(x1-xc)2+(y1-yc)2=R2(4.7-1)(x2-xc)2+(y2-yc)2=R2(4.7-2)(x3-xc)2+(y3-yc)2=R2(4.7-3)由消去元素法求解：(4.7-1)-(4.7-2)(x3-x2)-(4.7-3)-(4.7-2)(x1-x2),8,例：给定三点作一圆（2）,得到(4.7-4)xc可由式4.7-1式4.7-2和式4.7-4，求得：(4.7-5)式4.7-4和式4.7-5显然有不足之处：当两式的分母为0时，要轮换点再算；检验三点共线（半径是无穷）的条件非显而易见。,9,例：给定三点作一圆（3）,如果，把坐标系平移一下，使P1为新坐标系xp1y的原点，对三个点作一个变换，有：(4.7-6)(4.7-7)(4.7-8),10,例：给定三点作一圆（4）,从式4.7-7和式4.7-8中减去式4.7-6得到两个联立方程，解之有：(4.7-9)(4.7-10)(4.7-11)将平移回到原坐标系统，就得到圆心(xc,yc)的解。解法简化，但是同样存在分母有可能为零的情况，三点共线的条件也并不明显。,11,例：给定三点作一圆（5）,为了克服上述困难，可把坐标系统再作一次旋转，求解的过程则改成如下样式：过P1P2建立新x轴，并以P1为原点建立新坐标系xP1y；检验共线情况；在新坐标系下解圆的中心和半径；将得到的解(中心)变换回到原坐标系。,12,例：给定三点作一圆（6）,可得到下列三个联立方程(4.7-12)(4.7-13)(4.7-14),13,例：给定三点作一圆（7）,由式4.7.13式4.7.12得或(4.7-15)由式4.7.14式4.7.12和式4.7.15得：和(4.7-16)检测式4.7-16左式，如果y3=0，则yc为无穷，而只有当三点共线时，y3才会等于0。因此，在这个新坐标系下解的奇异状态是显而易见的。,14,4.7.2基本策略采用几何计算，避免代数运算,由上例可知，通过代数运算去解决几何段的相交运算一般较为复杂。如果直接采用几何计算解决过三点作圆问题，有可能更为简作P1P2的垂直平分线L1，作P1P3的垂直平分线L2求L1与L2的交点即为圆心，如果无交点，说明三点共线圆心和三点中任一点的距离即为半径。,15,例：求两个圆的交点代数运算,设两圆方程为：(x-x1)2+(y-y1)2=R12(4.7-17)(x-x2)2+(y-y2)2=R22(4.7-18)如果采用代数解法求解这两个联立二元二次方程。由式4.7.18-式4.5.17得(x2-x1)x+2(y2-y1)y=R22-R12+x22-x12+y22-y12(4.7-19)当x2=x1时，可由式4.7-19直接求得y的值；再代入式4.7-17(或式4.7-18)，得到x值；求得一元二次方程的2个解（选取其中一个）。,16,例：求两个圆的交点代数运算,当x2x1时，有(4.7-20)将式4.7.20代入式4.7.17（或式4.7.18），消去x，得到y的一元二次方程，即求得2个解，选取其中的一个；由此可知，用代数方法求解很繁琐；且要检测x2和x1（或y1和y2）是否相等。,17,例：求两个圆的交点几何解法,计算二圆心O1，O2间的距离以及O1O2和x轴的夹角；两圆交点P1，P2和两圆心构成P1O1O2和P2O2O1，可根据余弦定理求得角；,设A是通过O1与X轴平行的直线与圆周O1的交点，A=(x1+R1，y1)，则交点P1和P2可由点A绕O1旋转(+)和(-)角得到；这个算法最后并不涉及三角函数的计算，而且易于选择交点。,18,4.7.3基本几何计算,圆弧曲线的相交算法（例子）最小最大判定法劣弧段的最小外接矩形求取,19,最小最大判定法（1）,如果两个图形元素的最大矩形包围盒子不相重迭，则这两个图形元素不可能相交。最小最大判定法提供了这样一种快速拒绝判定法，这个判定法是用图形元素的最小外接矩形(或矩形盒子)来替代，用以粗略地判定两个图形元素之间的某种关系，例如不可能相交关系。虽然，这种判定条件是一种充分条件，在某些情况下，这种替代是不正确的，但由于其比较速度很快的优点弥点补了这种不足。,20,最小最大判定法（2）,a.外接矩形不相迭，图形也不相迭b.外接矩形相迭，但图形并不相迭c.外接矩形相迭，图形也相迭,21,最小最大判定法（3）,判别两个矩形相迭与否的两种算法（肯定算法和否定算法）,22,劣弧段的最小外接矩形求取（1）,设有一劣弧段的起点为P1(x1,y1)，终点为P2(x2,y2)，连接半径为R（R0时为逆时针，R0时为顺时针)，要求取包容此劣弧段的最小外接矩形：(Xmin，Ymin，Xmax，Ymax)由P1，P2和R计算出圆弧段的圆心(xc,yc)。因为规定为劣弧，所以所求圆心是唯一的。记：X1=min(x1，x2)，X2=max(x1，x2)；Y1=min(y1，y2)，Y2=max(y1，y2)。,23,劣弧段的最小外接矩形求取（2）,24,劣弧段的最小外接矩形求取（3）,25,圆弧曲线的相交算法,平面上几何元素相交中最复杂的问题，首推直线和圆弧组合而成的两条圆弧曲线的求解。在船舶、飞机、汽车等外形和内部构件的描述中经常需要解决曲线和曲线的相交问题。例如，描述船体的型线、横剖肋骨线、平剖水线和纵剖线等曲线往往是先通过对一些离散的点列进行曲线拟合，再用双圆弧逼近的方法，最终是以一连串相切的直线段和图弧段形成的圆弧曲线描述的。,26,圆弧曲线的相交算法,所谓曲线和曲线的相交，实际上是一组直线段或圆弧段构成的圆弧曲线，和另一条同样类型的圆弧曲线的相交计算。解的计算最终归结为下列三种基本几何段间的相交问题：直线段直线段直线段圆弧段圆弧段圆弧段之间的相交，都是基本几何间的计算。当组成两条相交曲线的基本几何段的数量达到一定的数量以后，完成两曲线相交计算的几何复杂性会明显增加。,27,圆弧曲线的相交算法,设曲线S1有n1个基本几何段，曲线S2有n2个基本几何段，那么，两曲线的相交计算的工作量为O(n1n2)。例如船体曲线，一般构造一条型线可达5060个点，如果采用双圆弧逼近，构造一条船体曲线的几何段可达100120段。若曲线中有拐点，则段数还将增加。以每条曲线100段计算，两曲线相交的计算量级为O(100100)。在一条船的型线产生过程中，这种对曲线的相截，拼接的工作是相当频繁的。如果能将两曲线相交的计算这样一种基本运算的几何复杂性降下来，对提高船型产生系统的效率会有相当的影响。,28,圆弧曲线的相交算法,考虑的思路是：两条圆弧曲线虽然可有较多的基本几何段，但是，它们之间的交点是较少的。在实际应用中，一般只有12个交点。因此，基本几何段间大部份是不相交的。如果能够以较快的速度排除掉那些不可能相交的几何段，而使求交计算压缩在可能产生的交点的几何段之间进行，那末，两条圆弧曲线的求交计算的效率可能大大提高。,29,圆弧曲线的相交算法,一个有效的办法是：如果复盖两个基本几何段的外接矩形（边平行于坐标轴）是不相重迭的，那末这两个几何段之间就不可能产生交点。而两个矩形的重迭判别是较简单的，这种算法就是最小最大判别法。,30,圆弧曲线的相交算法（1）,算法P：求取两条圆弧曲线S1和S2一个交点的算法。（曲线S1有n1个几何段，曲线S2有n2个几何段）P1【建立S1的新坐标系】：由曲线S1的首端点向末端点建立u轴，在中点建立v轴，形成uv右手坐标系统。其工作量为：O(1)。,31,圆弧曲线的相交算法（1）,P2【求S1的外接矩形】：在uv坐标下，建立包容曲线S1的最小外接矩形R1，矩形的边平行于uv轴。其工作量为；O(n1)。,32,圆弧曲线的相交算法（1）,P3【判别S2中和R1的重迭段】：对曲线S2的每一几何段在uv坐标系下建立其最小外接矩形盒子R2j，如果R2j和R1不相迭，则此几何段和S1无交点，否则记录段号j。其工作量为：O(n2)。,33,圆弧曲线的相交算法（4）,P4【判别】：如果所有的R2j均与R1不相迭，则表明两曲线S1和S2无交点，算法结束。其工作量为：O(1),34,圆弧曲线的相交算法（5）,P5【反向检测】：设曲线S2的R2N21到R2N22与R1相迭，则截取S2的第N21到第N22段曲线作为新的S1，以原S1作为新的S2，重复步骤P1P4，得到原曲线S1上的N11和N12。其工作量为：O(m2)+O(n1)+O(1),35,圆弧曲线的相交算法（6）,P6【求交】：如果N11和N12不存在，则两曲线无交点，算法结束；否则在原曲线S1的第N11-N12和S2的第N21-N22几何段间在原始坐标系下求交，得到两曲线S1和S2的一个交点，或认定无交点。算法结束。其工作量为：O(m1m2)。,36,圆弧曲线的相交算法（7）,n1为S1的初始几何段数；m1为S1落在S2中由第n21-n22几何段构成的最小外接矩形内的段数；m2为S2落在S1的最小外接矩形内的段数。由此，两条圆弧曲线求交的工作量由O(n1n2)变为O(n1+n2+m1m2)。一般情况下有m1n1，m2n2。在两条曲线分段外接矩形不重迭的情况下，可能出现m1=m2=0。P算法将使两圆弧曲线求交的几何复杂性由O(n1n2)下降到O(n1n2)，计算复杂性大为降低。,37,圆弧曲线的相交算法（8）,用P算法考察两条曲线的求交：将两个圆弧段各分成99等份，曲线S1由99个顺时针圆弧段构造，曲线S2由99个逆时针圆弧段构造(n1=n2=99)，两者的交点应为(0,1)。,38,圆弧曲线的相交算法（9）,曲线S1实际参与求交的几何段为第48段至第50段(共3个几何段)即：n11=48，n12=50，n22=67，m1=3，m2=8时间比例达7.3倍以上,39,圆弧曲线的相交算法（10）,在实际工程领域中，曲线的性质还会比以上分析的更好一点。例如：在船体曲线中，甚至于加上以下的限制也是符合实际情况的：两条曲线S1和S2在同一几何段内不出现2个交点。如果几何段是直线段，当然最多只有2个交点。但是如果其中有一个是圆弧段，就可能出现2个交点。,40,圆弧曲线的相交算法（10）,算法P只求得两条曲线的一个交点，如果有一个以上交点，可以在求取一个交点后去掉S1中交点所在段以前的那部份曲线，留下的曲线段作为新的S1与S2再求交点，如此继续。不管两曲线间有几个交点，都可通过有限次P算法予以解决。,41,总结,圆弧曲线的相交算法标准状态下求解采用几何计算，避免代数运算拒绝判定对降低算法复杂度的作用,