基本幾何02—幾何計算.ppt

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