基本幾何02—幾何計(jì)算.ppt

2002年10月24日,上海交通大學(xué)計(jì)算機(jī)系 何援軍,1,第4章 基本幾何,之二幾何計(jì)算,2,4.7幾何計(jì)算,3,4.7.1概述,從數(shù)學(xué)上解決直線(xiàn)和圓弧等基本幾何元素的相交問(wèn)題并不困難，只涉及到直線(xiàn)和直線(xiàn)，直線(xiàn)和圓弧，以及圓弧和圓弧的相交，相切計(jì)算。 許多圖形系統(tǒng)都采用某種方式解決了這個(gè)問(wèn)題，也投入了實(shí)際使用。只是程序系統(tǒng)所占有的空間、計(jì)算效率的高低、使用的方便性、程序和程序系統(tǒng)的適應(yīng)性上不同而已。,4,4.7.1概述,由于使用頻繁，直線(xiàn)圓弧系統(tǒng)僅考慮其準(zhǔn)確性是遠(yuǎn)遠(yuǎn)不夠的，而要著重考慮系統(tǒng)的效率及其可用性。 前者要求其各個(gè)子程序的設(shè)計(jì)具有較高的質(zhì)量，不僅要有數(shù)學(xué)處理的嚴(yán)密性，而且要用較少的步驟，較快的途徑得到結(jié)果。 后者考慮的是：在問(wèn)題有多個(gè)解的情況下，如何使用戶(hù)能夠方便、直觀地加以選擇。,5,4.7.2幾何計(jì)算的基本策略,在解決基本幾何的相交計(jì)算時(shí)，掌握一些技巧往往很有效。 在標(biāo)準(zhǔn)坐標(biāo)系下求解； （通過(guò)坐標(biāo)變換） 采用幾何計(jì)算，避免代數(shù)運(yùn)算。,6,4.7.2基本策略在標(biāo)準(zhǔn)坐標(biāo)系下求解,圓心在坐標(biāo)原點(diǎn)的圓（?。┑那蠼夤酵容^簡(jiǎn)單； 可以通過(guò)坐標(biāo)變換將求解的基本幾何轉(zhuǎn)換到標(biāo)準(zhǔn)坐標(biāo)系下： 可先將坐標(biāo)系作平移將新坐標(biāo)系原點(diǎn)移到一個(gè)圓弧的中心； 或通過(guò)平移和（或）旋轉(zhuǎn)使新的坐標(biāo)軸沿著給定直線(xiàn)的方向； 或通過(guò)平移和（或）旋轉(zhuǎn)使新的坐標(biāo)軸沿著兩個(gè)弧中心的方向。 等等,7,例：給定三點(diǎn)作一圓（1）,題：求通過(guò)3個(gè)點(diǎn)P1，P2，P3的圓 解：設(shè)所求圓的圓心為Pc(xc,yc)，半徑為R。直接的解法是解以下三個(gè)非線(xiàn)性聯(lián)立方程： (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,例：給定三點(diǎn)作一圓（2）,得到 (4.7-4) xc可由式4.7-1式4.7-2和式4.7-4，求得： (4.7-5) 式4.7-4和式4.7-5顯然有不足之處： 當(dāng)兩式的分母為0時(shí)，要輪換點(diǎn)再算； 檢驗(yàn)三點(diǎn)共線(xiàn)（半徑是無(wú)窮）的條件非顯而易見(jiàn)。,9,例：給定三點(diǎn)作一圓（3）,如果，把坐標(biāo)系平移一下，使P1為新坐標(biāo)系xp1y的原點(diǎn)，對(duì)三個(gè)點(diǎn)作一個(gè)變換，有： (4.7-6) (4.7-7) (4.7-8),10,例：給定三點(diǎn)作一圓（4）,從式4.7-7和式4.7-8中減去式4.7-6得到兩個(gè)聯(lián)立方程，解之有： (4.7-9) (4.7-10) (4.7-11) 將 平移回到原坐標(biāo)系統(tǒng)，就得到圓心(xc,yc) 的解。 解法簡(jiǎn)化，但是同樣存在分母有可能為零的情況，三點(diǎn)共線(xiàn)的條件也并不明顯。,11,例：給定三點(diǎn)作一圓（5）,為了克服上述困難，可把坐標(biāo)系統(tǒng)再作一次旋轉(zhuǎn)，求解的過(guò)程則改成如下樣式： 過(guò)P1P2建立新x“軸，并以P1為原點(diǎn)建立新坐標(biāo)系x“P1y“ ； 檢驗(yàn)共線(xiàn)情況； 在新坐標(biāo)系下解圓的中心和半徑； 將得到的解(中心)變換回到原坐標(biāo)系。,12,例：給定三點(diǎn)作一圓（6）,可得到下列三個(gè)聯(lián)立方程 (4.7-12) (4.7-13) (4.7-14),13,例：給定三點(diǎn)作一圓（7）,由式4.7.13式4.7.12得 或 (4.7-15) 由式4.7.14式4.7.12和式4.7.15得： 和 (4.7-16) 檢測(cè)式4.7-16左式，如果y3“ = 0，則yc“為無(wú)窮，而只有當(dāng)三點(diǎn)共線(xiàn)時(shí)， y3“才會(huì)等于0 。 因此，在這個(gè)新坐標(biāo)系下解的奇異狀態(tài)是顯而易見(jiàn)的。,14,4.7.2基本策略采用幾何計(jì)算，避免代數(shù)運(yùn)算,由上例可知，通過(guò)代數(shù)運(yùn)算去解決幾何段的相交運(yùn)算一般較為復(fù)雜。如果直接采用幾何計(jì)算解決過(guò)三點(diǎn)作圓問(wèn)題，有可能更為簡(jiǎn) 作P1P2的垂直平分線(xiàn)L1，作P1P3的垂直平分線(xiàn)L2 求L1與L2的交點(diǎn)即為圓心， 如果無(wú)交點(diǎn)，說(shuō)明三點(diǎn)共線(xiàn) 圓心和三點(diǎn)中任一點(diǎn)的距離 即為半徑。,15,例：求兩個(gè)圓的交點(diǎn)代數(shù)運(yùn)算,設(shè)兩圓方程為： (x-x1)2+(y-y1)2=R12 (4.7-17) (x-x2)2+(y-y2)2=R22 (4.7-18) 如果采用代數(shù)解法求解這兩個(gè)聯(lián)立二元二次方程。由式4.7.18-式4.5.17得 (x2-x1)x+2(y2-y1)y=R22-R12+x22-x12+y22-y12 (4.7-19) 當(dāng) x2=x1時(shí)，可由式4.7-19直接求得y的值； 再代入式4.7-17(或式4.7-18)，得到x值； 求得一元二次方程的2個(gè)解（選取其中一個(gè)）。,16,例：求兩個(gè)圓的交點(diǎn)代數(shù)運(yùn)算,當(dāng) x2x1時(shí)，有 (4.7-20) 將式4.7.20代入式4.7.17（或式4.7.18），消去x，得到y(tǒng)的一元二次方程，即求得2個(gè)解，選取其中的一個(gè)； 由此可知，用代數(shù)方法求解很繁瑣； 且要檢測(cè)x2和x1（或y1和y2）是否相等。,17,例：求兩個(gè)圓的交點(diǎn)幾何解法,計(jì)算二圓心O1，O2間的距離以及O1O2和x軸的夾角； 兩圓交點(diǎn)P1，P2和兩圓心構(gòu)成P1O1O2和P2O2O1，可根據(jù)余弦定理求得角；,設(shè)A是通過(guò)O1與X軸平行的直線(xiàn)與圓周O1的交點(diǎn)，A=(x1+R1，y1)，則交點(diǎn)P1和P2可由點(diǎn)A繞O1旋轉(zhuǎn)(+)和(-)角得到； 這個(gè)算法最后并不涉及三角函數(shù)的計(jì)算，而且易于選擇交點(diǎn)。,18,4.7.3 基本幾何計(jì)算,圓弧曲線(xiàn)的相交算法（例子） 最小最大判定法 劣弧段的最小外接矩形求取,19,最小最大判定法（1）,如果兩個(gè)圖形元素的最大矩形包圍盒子不相重迭，則這兩個(gè)圖形元素不可能相交。 最小最大判定法提供了這樣一種快速拒絕判定法，這個(gè)判定法是用圖形元素的最小外接矩形(或矩形盒子)來(lái)替代，用以粗略地判定兩個(gè)圖形元素之間的某種關(guān)系，例如不可能相交關(guān)系。 雖然，這種判定條件是一種充分條件，在某些情況下，這種替代是不正確的，但由于其比較速度很快的優(yōu)點(diǎn)彌點(diǎn)補(bǔ)了這種不足。,20,最小最大判定法（2）,a.外接矩形不相迭，圖形也不相迭 b.外接矩形相迭，但圖形并不相迭 c.外接矩形相迭，圖形也相迭,21,最小最大判定法（3）,判別兩個(gè)矩形相迭與否的兩種算法 （肯定算法和否定算法）,22,劣弧段的最小外接矩形求?。?）,設(shè)有一劣弧段的起點(diǎn)為P1(x1,y1)，終點(diǎn)為P2(x2,y2)，連接半徑為R（R0時(shí)為逆時(shí)針，R0時(shí)為順時(shí)針)，要求取包容此劣弧段的最小外接矩形： (Xmin，Ymin，Xmax，Ymax) 由P1，P2和R計(jì)算出圓弧段的圓心(xc , yc)。因?yàn)橐?guī)定為劣弧，所以所求圓心是唯一的。 記： X1=min(x1，x2)，X2=max(x1，x2)； Y1=min(y1，y2)，Y2=max(y1，y2)。,23,劣弧段的最小外接矩形求?。?）,24,劣弧段的最小外接矩形求取（3）,25,圓弧曲線(xiàn)的相交算法,平面上幾何元素相交中最復(fù)雜的問(wèn)題，首推直線(xiàn)和圓弧組合而成的兩條圓弧曲線(xiàn)的求解。 在船舶、飛機(jī)、汽車(chē)等外形和內(nèi)部構(gòu)件的描述中經(jīng)常需要解決曲線(xiàn)和曲線(xiàn)的相交問(wèn)題。 例如，描述船體的型線(xiàn)、橫剖肋骨線(xiàn)、平剖水線(xiàn)和縱剖線(xiàn)等曲線(xiàn)往往是先通過(guò)對(duì)一些離散的點(diǎn)列進(jìn)行曲線(xiàn)擬合，再用雙圓弧逼近的方法，最終是以一連串相切的直線(xiàn)段和圖弧段形成的圓弧曲線(xiàn)描述的。,26,圓弧曲線(xiàn)的相交算法,所謂曲線(xiàn)和曲線(xiàn)的相交，實(shí)際上是一組直線(xiàn)段或圓弧段構(gòu)成的圓弧曲線(xiàn)，和另一條同樣類(lèi)型的圓弧曲線(xiàn)的相交計(jì)算。 解的計(jì)算最終歸結(jié)為下列三種基本幾何段間的相交問(wèn)題： 直線(xiàn)段直線(xiàn)段 直線(xiàn)段圓弧段 圓弧段圓弧段 之間的相交，都是基本幾何間的計(jì)算。 當(dāng)組成兩條相交曲線(xiàn)的基本幾何段的數(shù)量達(dá)到一定的數(shù)量以后，完成兩曲線(xiàn)相交計(jì)算的幾何復(fù)雜性會(huì)明顯增加。,27,圓弧曲線(xiàn)的相交算法,設(shè)曲線(xiàn)S1有n1個(gè)基本幾何段，曲線(xiàn)S2有n2個(gè)基本幾何段，那么，兩曲線(xiàn)的相交計(jì)算的工作量為O(n1n2)。 例如船體曲線(xiàn)，一般構(gòu)造一條型線(xiàn)可達(dá)5060個(gè)點(diǎn)，如果采用雙圓弧逼近，構(gòu)造一條船體曲線(xiàn)的幾何段可達(dá)100120段。若曲線(xiàn)中有拐點(diǎn)，則段數(shù)還將增加。以每條曲線(xiàn)100段計(jì)算，兩曲線(xiàn)相交的計(jì)算量級(jí)為O(100100)。 在一條船的型線(xiàn)產(chǎn)生過(guò)程中，這種對(duì)曲線(xiàn)的相截，拼接的工作是相當(dāng)頻繁的。 如果能將兩曲線(xiàn)相交的計(jì)算這樣一種基本運(yùn)算的幾何復(fù)雜性降下來(lái)，對(duì)提高船型產(chǎn)生系統(tǒng)的效率會(huì)有相當(dāng)?shù)挠绊憽?28,圓弧曲線(xiàn)的相交算法,考慮的思路是： 兩條圓弧曲線(xiàn)雖然可有較多的基本幾何段，但是，它們之間的交點(diǎn)是較少的。在實(shí)際應(yīng)用中，一般只有12個(gè)交點(diǎn)。因此，基本幾何段間大部份是不相交的。 如果能夠以較快的速度排除掉那些不可能相交的幾何段，而使求交計(jì)算壓縮在可能產(chǎn)生的交點(diǎn)的幾何段之間進(jìn)行，那末，兩條圓弧曲線(xiàn)的求交計(jì)算的效率可能大大提高。,29,圓弧曲線(xiàn)的相交算法,一個(gè)有效的辦法是： 如果復(fù)蓋兩個(gè)基本幾何段的外接矩形（邊平行于坐標(biāo)軸）是不相重迭的，那末這兩個(gè)幾何段之間就不可能產(chǎn)生交點(diǎn)。 而兩個(gè)矩形的重迭判別是較簡(jiǎn)單的，這種算法就是最小最大判別法。,30,圓弧曲線(xiàn)的相交算法（1）,算法P：求取兩條圓弧曲線(xiàn)S1和S2一個(gè)交點(diǎn)的算法。（曲線(xiàn)S1有n1個(gè)幾何段，曲線(xiàn)S2有n2個(gè)幾何段） P1【建立S1的新坐標(biāo)系】：由曲線(xiàn)S1的首端點(diǎn)向末端點(diǎn)建立u軸，在中點(diǎn)建立v軸，形成uv右手坐標(biāo)系統(tǒng)。其工作量為：O(1)。,31,圓弧曲線(xiàn)的相交算法（1）,P2【求S1的外接矩形】：在uv坐標(biāo)下，建立包容曲線(xiàn)S1的最小外接矩形R1，矩形的邊平行于uv軸。其工作量為；O(n1)。,32,圓弧曲線(xiàn)的相交算法（1）,P3【判別S2中和R1的重迭段】：對(duì)曲線(xiàn)S2的每一幾何段在uv坐標(biāo)系下建立其最小外接矩形盒子R2j，如果R2j和R1不相迭，則此幾何段和S1無(wú)交點(diǎn)，否則記錄段號(hào)j。其工作量為：O(n2)。,33,圓弧曲線(xiàn)的相交算法（4）,P4【判別】：如果所有的R2j均與R1不相迭，則表明兩曲線(xiàn)S1和S2無(wú)交點(diǎn)，算法結(jié)束。 其工作量為：O(1),34,圓弧曲線(xiàn)的相交算法（5）,P5【反向檢測(cè)】：設(shè)曲線(xiàn)S2的R2N21到R2N22與R1相迭，則截取S2的第N21到第N22段曲線(xiàn)作為新的S1，以原S1作為新的S2，重復(fù)步驟P1P4，得到原曲線(xiàn)S1上的N11和N12。 其工作量為：O(m2)+O(n1)+O(1),35,圓弧曲線(xiàn)的相交算法（6）,P6【求交】：如果N11和N12不存在，則兩曲線(xiàn)無(wú)交點(diǎn)，算法結(jié)束；否則在原曲線(xiàn)S1的第N11-N12和S2的第N21-N22幾何段間在原始坐標(biāo)系下求交，得到兩曲線(xiàn)S1和S2的一個(gè)交點(diǎn)，或認(rèn)定無(wú)交點(diǎn)。算法結(jié)束。 其工作量為：O(m1m2)。,36,圓弧曲線(xiàn)的相交算法（7）,n1為S1的初始幾何段數(shù)；m1為S1落在S2中由第n21-n22幾何段構(gòu)成的最小外接矩形內(nèi)的段數(shù)；m2為S2落在S1的最小外接矩形內(nèi)的段數(shù)。由此，兩條圓弧曲線(xiàn)求交的工作量由O(n1n2)變?yōu)镺(n1+n2+m1m2)。 一般情況下有m1n1，m2n2。在兩條曲線(xiàn)分段外接矩形不重迭的情況下，可能出現(xiàn)m1=m2=0。 P算法將使兩圓弧曲線(xiàn)求交的幾何復(fù)雜性由O(n1n2)下降到O(n1n2)，計(jì)算復(fù)雜性大為降低。,37,圓弧曲線(xiàn)的相交算法（8）,用P算法考察兩條曲線(xiàn)的求交：將兩個(gè)圓弧段各分成99等份，曲線(xiàn)S1由99個(gè)順時(shí)針圓弧段構(gòu)造，曲線(xiàn)S2由99個(gè)逆時(shí)針圓弧段構(gòu)造(n1=n2=99)，兩者的交點(diǎn)應(yīng)為(0,1)。,38,圓弧曲線(xiàn)的相交算法（9）,曲線(xiàn)S1實(shí)際參與求交的幾何段為第48段至第50段(共3個(gè)幾何段) 即：n11=48，n12=50，n22=67，m1=3，m2=8 時(shí)間比例達(dá)7.3倍以上,39,圓弧曲線(xiàn)的相交算法（10）,在實(shí)際工程領(lǐng)域中，曲線(xiàn)的性質(zhì)還會(huì)比以上分析的更好一點(diǎn)。 例如：在船體曲線(xiàn)中，甚至于加上以下的限制也是符合實(shí)