




已閱讀5頁,還剩36頁未讀, 繼續(xù)免費(fèi)閱讀
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
2002年10月24日,上海交通大學(xué)計(jì)算機(jī)系 何援軍,1,第4章 基本幾何,之二幾何計(jì)算,2,4.7幾何計(jì)算,3,4.7.1概述,從數(shù)學(xué)上解決直線和圓弧等基本幾何元素的相交問題并不困難,只涉及到直線和直線,直線和圓弧,以及圓弧和圓弧的相交,相切計(jì)算。 許多圖形系統(tǒng)都采用某種方式解決了這個問題,也投入了實(shí)際使用。只是程序系統(tǒng)所占有的空間、計(jì)算效率的高低、使用的方便性、程序和程序系統(tǒng)的適應(yīng)性上不同而已。,4,4.7.1概述,由于使用頻繁,直線圓弧系統(tǒng)僅考慮其準(zhǔn)確性是遠(yuǎn)遠(yuǎn)不夠的,而要著重考慮系統(tǒng)的效率及其可用性。 前者要求其各個子程序的設(shè)計(jì)具有較高的質(zhì)量,不僅要有數(shù)學(xué)處理的嚴(yán)密性,而且要用較少的步驟,較快的途徑得到結(jié)果。 后者考慮的是:在問題有多個解的情況下,如何使用戶能夠方便、直觀地加以選擇。,5,4.7.2幾何計(jì)算的基本策略,在解決基本幾何的相交計(jì)算時,掌握一些技巧往往很有效。 在標(biāo)準(zhǔn)坐標(biāo)系下求解; (通過坐標(biāo)變換) 采用幾何計(jì)算,避免代數(shù)運(yùn)算。,6,4.7.2基本策略在標(biāo)準(zhǔn)坐標(biāo)系下求解,圓心在坐標(biāo)原點(diǎn)的圓(?。┑那蠼夤酵容^簡單; 可以通過坐標(biāo)變換將求解的基本幾何轉(zhuǎn)換到標(biāo)準(zhǔn)坐標(biāo)系下: 可先將坐標(biāo)系作平移將新坐標(biāo)系原點(diǎn)移到一個圓弧的中心; 或通過平移和(或)旋轉(zhuǎn)使新的坐標(biāo)軸沿著給定直線的方向; 或通過平移和(或)旋轉(zhuǎn)使新的坐標(biāo)軸沿著兩個弧中心的方向。 等等,7,例:給定三點(diǎn)作一圓(1),題:求通過3個點(diǎn)P1,P2,P3的圓 解:設(shè)所求圓的圓心為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,例:給定三點(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時,要輪換點(diǎn)再算; 檢驗(yàn)三點(diǎn)共線(半徑是無窮)的條件非顯而易見。,9,例:給定三點(diǎn)作一圓(3),如果,把坐標(biāo)系平移一下,使P1為新坐標(biāo)系xp1y的原點(diǎn),對三個點(diǎn)作一個變換,有: (4.7-6) (4.7-7) (4.7-8),10,例:給定三點(diǎn)作一圓(4),從式4.7-7和式4.7-8中減去式4.7-6得到兩個聯(lián)立方程,解之有: (4.7-9) (4.7-10) (4.7-11) 將 平移回到原坐標(biāo)系統(tǒng),就得到圓心(xc,yc) 的解。 解法簡化,但是同樣存在分母有可能為零的情況,三點(diǎn)共線的條件也并不明顯。,11,例:給定三點(diǎn)作一圓(5),為了克服上述困難,可把坐標(biāo)系統(tǒng)再作一次旋轉(zhuǎn),求解的過程則改成如下樣式: 過P1P2建立新x“軸,并以P1為原點(diǎn)建立新坐標(biāo)系x“P1y“ ; 檢驗(yàn)共線情況; 在新坐標(biāo)系下解圓的中心和半徑; 將得到的解(中心)變換回到原坐標(biāo)系。,12,例:給定三點(diǎn)作一圓(6),可得到下列三個聯(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) 檢測式4.7-16左式,如果y3“ = 0,則yc“為無窮,而只有當(dāng)三點(diǎn)共線時, y3“才會等于0 。 因此,在這個新坐標(biāo)系下解的奇異狀態(tài)是顯而易見的。,14,4.7.2基本策略采用幾何計(jì)算,避免代數(shù)運(yùn)算,由上例可知,通過代數(shù)運(yùn)算去解決幾何段的相交運(yùn)算一般較為復(fù)雜。如果直接采用幾何計(jì)算解決過三點(diǎn)作圓問題,有可能更為簡 作P1P2的垂直平分線L1,作P1P3的垂直平分線L2 求L1與L2的交點(diǎn)即為圓心, 如果無交點(diǎn),說明三點(diǎn)共線 圓心和三點(diǎn)中任一點(diǎn)的距離 即為半徑。,15,例:求兩個圓的交點(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ù)解法求解這兩個聯(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時,可由式4.7-19直接求得y的值; 再代入式4.7-17(或式4.7-18),得到x值; 求得一元二次方程的2個解(選取其中一個)。,16,例:求兩個圓的交點(diǎn)代數(shù)運(yùn)算,當(dāng) x2x1時,有 (4.7-20) 將式4.7.20代入式4.7.17(或式4.7.18),消去x,得到y(tǒng)的一元二次方程,即求得2個解,選取其中的一個; 由此可知,用代數(shù)方法求解很繁瑣; 且要檢測x2和x1(或y1和y2)是否相等。,17,例:求兩個圓的交點(diǎn)幾何解法,計(jì)算二圓心O1,O2間的距離以及O1O2和x軸的夾角; 兩圓交點(diǎn)P1,P2和兩圓心構(gòu)成P1O1O2和P2O2O1,可根據(jù)余弦定理求得角;,設(shè)A是通過O1與X軸平行的直線與圓周O1的交點(diǎn),A=(x1+R1,y1),則交點(diǎn)P1和P2可由點(diǎn)A繞O1旋轉(zhuǎn)(+)和(-)角得到; 這個算法最后并不涉及三角函數(shù)的計(jì)算,而且易于選擇交點(diǎn)。,18,4.7.3 基本幾何計(jì)算,圓弧曲線的相交算法(例子) 最小最大判定法 劣弧段的最小外接矩形求取,19,最小最大判定法(1),如果兩個圖形元素的最大矩形包圍盒子不相重迭,則這兩個圖形元素不可能相交。 最小最大判定法提供了這樣一種快速拒絕判定法,這個判定法是用圖形元素的最小外接矩形(或矩形盒子)來替代,用以粗略地判定兩個圖形元素之間的某種關(guān)系,例如不可能相交關(guān)系。 雖然,這種判定條件是一種充分條件,在某些情況下,這種替代是不正確的,但由于其比較速度很快的優(yōu)點(diǎn)彌點(diǎn)補(bǔ)了這種不足。,20,最小最大判定法(2),a.外接矩形不相迭,圖形也不相迭 b.外接矩形相迭,但圖形并不相迭 c.外接矩形相迭,圖形也相迭,21,最小最大判定法(3),判別兩個矩形相迭與否的兩種算法 (肯定算法和否定算法),22,劣弧段的最小外接矩形求?。?),設(shè)有一劣弧段的起點(diǎn)為P1(x1,y1),終點(diǎn)為P2(x2,y2),連接半徑為R(R0時為逆時針,R0時為順時針),要求取包容此劣弧段的最小外接矩形: (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,圓弧曲線的相交算法,平面上幾何元素相交中最復(fù)雜的問題,首推直線和圓弧組合而成的兩條圓弧曲線的求解。 在船舶、飛機(jī)、汽車等外形和內(nèi)部構(gòu)件的描述中經(jīng)常需要解決曲線和曲線的相交問題。 例如,描述船體的型線、橫剖肋骨線、平剖水線和縱剖線等曲線往往是先通過對一些離散的點(diǎn)列進(jìn)行曲線擬合,再用雙圓弧逼近的方法,最終是以一連串相切的直線段和圖弧段形成的圓弧曲線描述的。,26,圓弧曲線的相交算法,所謂曲線和曲線的相交,實(shí)際上是一組直線段或圓弧段構(gòu)成的圓弧曲線,和另一條同樣類型的圓弧曲線的相交計(jì)算。 解的計(jì)算最終歸結(jié)為下列三種基本幾何段間的相交問題: 直線段直線段 直線段圓弧段 圓弧段圓弧段 之間的相交,都是基本幾何間的計(jì)算。 當(dāng)組成兩條相交曲線的基本幾何段的數(shù)量達(dá)到一定的數(shù)量以后,完成兩曲線相交計(jì)算的幾何復(fù)雜性會明顯增加。,27,圓弧曲線的相交算法,設(shè)曲線S1有n1個基本幾何段,曲線S2有n2個基本幾何段,那么,兩曲線的相交計(jì)算的工作量為O(n1n2)。 例如船體曲線,一般構(gòu)造一條型線可達(dá)5060個點(diǎn),如果采用雙圓弧逼近,構(gòu)造一條船體曲線的幾何段可達(dá)100120段。若曲線中有拐點(diǎn),則段數(shù)還將增加。以每條曲線100段計(jì)算,兩曲線相交的計(jì)算量級為O(100100)。 在一條船的型線產(chǎn)生過程中,這種對曲線的相截,拼接的工作是相當(dāng)頻繁的。 如果能將兩曲線相交的計(jì)算這樣一種基本運(yùn)算的幾何復(fù)雜性降下來,對提高船型產(chǎn)生系統(tǒng)的效率會有相當(dāng)?shù)挠绊憽?28,圓弧曲線的相交算法,考慮的思路是: 兩條圓弧曲線雖然可有較多的基本幾何段,但是,它們之間的交點(diǎn)是較少的。在實(shí)際應(yīng)用中,一般只有12個交點(diǎn)。因此,基本幾何段間大部份是不相交的。 如果能夠以較快的速度排除掉那些不可能相交的幾何段,而使求交計(jì)算壓縮在可能產(chǎn)生的交點(diǎn)的幾何段之間進(jìn)行,那末,兩條圓弧曲線的求交計(jì)算的效率可能大大提高。,29,圓弧曲線的相交算法,一個有效的辦法是: 如果復(fù)蓋兩個基本幾何段的外接矩形(邊平行于坐標(biāo)軸)是不相重迭的,那末這兩個幾何段之間就不可能產(chǎn)生交點(diǎn)。 而兩個矩形的重迭判別是較簡單的,這種算法就是最小最大判別法。,30,圓弧曲線的相交算法(1),算法P:求取兩條圓弧曲線S1和S2一個交點(diǎn)的算法。(曲線S1有n1個幾何段,曲線S2有n2個幾何段) P1【建立S1的新坐標(biāo)系】:由曲線S1的首端點(diǎn)向末端點(diǎn)建立u軸,在中點(diǎn)建立v軸,形成uv右手坐標(biāo)系統(tǒng)。其工作量為:O(1)。,31,圓弧曲線的相交算法(1),P2【求S1的外接矩形】:在uv坐標(biāo)下,建立包容曲線S1的最小外接矩形R1,矩形的邊平行于uv軸。其工作量為;O(n1)。,32,圓弧曲線的相交算法(1),P3【判別S2中和R1的重迭段】:對曲線S2的每一幾何段在uv坐標(biāo)系下建立其最小外接矩形盒子R2j,如果R2j和R1不相迭,則此幾何段和S1無交點(diǎn),否則記錄段號j。其工作量為:O(n2)。,33,圓弧曲線的相交算法(4),P4【判別】:如果所有的R2j均與R1不相迭,則表明兩曲線S1和S2無交點(diǎn),算法結(jié)束。 其工作量為:O(1),34,圓弧曲線的相交算法(5),P5【反向檢測】:設(shè)曲線S2的R2N21到R2N22與R1相迭,則截取S2的第N21到第N22段曲線作為新的S1,以原S1作為新的S2,重復(fù)步驟P1P4,得到原曲線S1上的N11和N12。 其工作量為:O(m2)+O(n1)+O(1),35,圓弧曲線的相交算法(6),P6【求交】:如果N11和N12不存在,則兩曲線無交點(diǎn),算法結(jié)束;否則在原曲線S1的第N11-N12和S2的第N21-N22幾何段間在原始坐標(biāo)系下求交,得到兩曲線S1和S2的一個交點(diǎn),或認(rèn)定無交點(diǎn)。算法結(jié)束。 其工作量為:O(m1m2)。,36,圓弧曲線的相交算法(7),n1為S1的初始幾何段數(shù);m1為S1落在S2中由第n21-n22幾何段構(gòu)成的最小外接矩形內(nèi)的段數(shù);m2為S2落在S1的最小外接矩形內(nèi)的段數(shù)。由此,兩條圓弧曲線求交的工作量由O(n1n2)變?yōu)镺(n1+n2+m1m2)。 一般情況下有m1n1,m2n2。在兩條曲線分段外接矩形不重迭的情況下,可能出現(xiàn)m1=m2=0。 P算法將使兩圓弧曲線求交的幾何復(fù)雜性由O(n1n2)下降到O(n1n2),計(jì)算復(fù)雜性大為降低。,37,圓弧曲線的相交算法(8),用P算法考察兩條曲線的求交:將兩個圓弧段各分成99等份,曲線S1由99個順時針圓弧段構(gòu)造,曲線S2由99個逆時針圓弧段構(gòu)造(n1=n2=99),兩者的交點(diǎn)應(yīng)為(0,1)。,38,圓弧曲線的相交算法(9),曲線S1實(shí)際參與求交的幾何段為第48段至第50段(共3個幾何段) 即:n11=48,n12=50,n22=67,m1=3,m2=8 時間比例達(dá)7.3倍以上,39,圓弧曲線的相交算法(10),在實(shí)際工程領(lǐng)域中,曲線的性質(zhì)還會比以上分析的更好一點(diǎn)。 例如:在船體曲線中,甚至于加上以下的限制也是符合實(shí)
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 遼寧工業(yè)大學(xué)《馬克思主義哲學(xué)經(jīng)典著作》2023-2024學(xué)年第二學(xué)期期末試卷
- 云南省祿豐縣廣通中學(xué)2024-2025學(xué)年高三4月質(zhì)量調(diào)研(二模)考試化學(xué)試題含解析
- 河北省邯鄲市成安縣2024-2025學(xué)年六年級下學(xué)期小升初招生數(shù)學(xué)試卷含解析
- 新疆大學(xué)《影視非線性編輯與合成》2023-2024學(xué)年第一學(xué)期期末試卷
- 湖南省雅禮洋湖中學(xué)2024-2025學(xué)年高三4月期中練習(xí)(二模)物理試題(理、文合卷)試題含解析
- 遼寧省重點(diǎn)高中協(xié)作校2024-2025學(xué)年全國高考招生統(tǒng)一考試考前診斷(一)英語試題含解析
- 江蘇省南京六合區(qū)程橋高中2024-2025學(xué)年高三年級模擬考試(四)英語試題含解析
- 山東省商河縣龍桑寺鎮(zhèn)2024-2025學(xué)年中考終極猜想:英語試題最后一卷名師猜題含答案
- 泰山護(hù)理職業(yè)學(xué)院《三維建模技術(shù)》2023-2024學(xué)年第二學(xué)期期末試卷
- 西南交通大學(xué)《人工智能醫(yī)療器械法規(guī)與注冊》2023-2024學(xué)年第一學(xué)期期末試卷
- 肝門部膽管癌診斷和治療指南(2025版)解讀
- 2025年廣東廣州市高三一模英語試卷試題及答案
- 2025年江蘇金陵科技集團(tuán)有限公司招聘筆試參考題庫含答案解析
- GB/T 30595-2024建筑保溫用擠塑聚苯板(XPS)系統(tǒng)材料
- 四肢骨折的固定搬運(yùn)課件
- 全國主體功能區(qū)規(guī)劃圖
- F5負(fù)載均衡運(yùn)維配置手冊V10
- 管道支架重量計(jì)算表(計(jì)算支架)
- 充電樁安裝施工流程
- 成績單表格樣表
- 人教三年級數(shù)學(xué)下冊:期中復(fù)習(xí)與檢測教學(xué)教案
評論
0/150
提交評論