下載本文檔
版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、程序設(shè)計(jì)藝術(shù)與方法課程實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱(chēng)實(shí)驗(yàn)三計(jì)算幾何算法的實(shí)現(xiàn)姓名系院專(zhuān)業(yè)班級(jí)學(xué)號(hào)實(shí)驗(yàn)日期指導(dǎo)教師徐本柱成績(jī)一、實(shí)驗(yàn)?zāi)康暮鸵?1)理解線段的性質(zhì)、叉積和后向回積。(2)掌握尋找凸包的算法。(3)綜合運(yùn)用計(jì)算幾何和搜索中的知識(shí)求解有關(guān)問(wèn)題。二、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容1 .掌握線段的性質(zhì)以及叉積和后向圖積的計(jì)算方法。2 .預(yù)習(xí)尋找凸包的算法。三、實(shí)驗(yàn)項(xiàng)目摘要(1)將講義第三章第二節(jié)中的凸包代碼上機(jī)運(yùn)行并檢驗(yàn)結(jié)果。(2)完成講義第三章的課后習(xí)題,上機(jī)運(yùn)行并檢驗(yàn)結(jié)果。(3)思考:判線段相交時(shí),如果有個(gè)線段的端點(diǎn)在另一條線段上,注意可能與另一條線段上的端點(diǎn)重合,思考這樣的情況怎么辦。(4)房間最矩路問(wèn)題:給定一
2、個(gè)內(nèi)含阻礙墻的房間,求解出一條從起點(diǎn)到終點(diǎn)的最最短路徑。房間的邊界固定在x=0,x=10,y=0和y=10o起點(diǎn)和終點(diǎn)固定在(0,5)和(10,5)。房間里還有0到18個(gè)墻,每個(gè)墻有兩個(gè)門(mén)。輸入給定的墻的個(gè)數(shù),每個(gè)墻的x位置和兩個(gè)門(mén)的y坐標(biāo)區(qū)間,輸出最矩路的長(zhǎng)度。卜圖是個(gè)例子:四、實(shí)驗(yàn)結(jié)果與分析(源程序及相關(guān)說(shuō)明)思考:判線段相交時(shí),如果有個(gè)線段的端點(diǎn)在另一條線段上,注意可能與另一條線段上的端點(diǎn)重合,思考這樣的情況怎么辦。用跨立的方法。線段相交滿(mǎn)足且只需滿(mǎn)足如下兩個(gè)條件就可以了:(1)兩條線段相互跨立;(2)一條線段的一個(gè)端點(diǎn)在另一條線段上。如果兩線段相交,則兩線段必然相互跨立對(duì)方,若p1p2
3、跨立p3P4,則(p1-p3)X(p4-p3)*(p2-p3)X(p4-p3)>0,當(dāng)(p1-p3)X(p4-p3)=0時(shí),說(shuō)明p1,p3,p4共線,但是因?yàn)橐呀?jīng)通過(guò)了快速排斥實(shí)驗(yàn),所以點(diǎn)p1一定在線段p3,p4上。所以判斷線段p1p2,p3P4相交的依據(jù)是(p1-p3)X(p4-p3)*(p2-p3)X(p4-p3)>=0。#include<iostream>#include<utility>usingnamespacestd;typedefpair<double,double>POINT;doubledirection(POINTp,POIN
4、Tp1,POINTp2)POINTv1,v2;=;=;=return*on_segment(POINTp,POINTp1,POINTp2)doublemin_x=<?:;doublemax_x=>?:;doublemin_y=<?:;doublemax_y=>?:;if>=min_x&&<=max_x&&>=min_y&&<=max_y)returntrue;elsereturnfalse;)boolsegment_intersect(POINTp1,POINTp2,POINTp3,POINTp4)
5、doubled1=direction(p3,p4,p1);doubled2=direction(p3,p4,p2);doubled3=direction(p1,p2,p3);doubled4=direction(p1,p2,p4);if(d1>0&&d2<0|d1<0&&d2>0)&&(d3>0&&d4<0|d3<0&&d4>0)returntrue;elseif(d1=0&&on_segment(p1,p3,p4)returntrue;elseif(
6、d2=0&&on_segment(p2,p3,p4)returntrue;elseif(d3=0&&onsegment(p3,p1,p2)returntrue;elseif(d4=0&&on_segment(p4,p1,p2)returntrue;elsereturnfalse;intmain()POINTp1,p2,p3,p4;cout<<"請(qǐng)輸入四個(gè)點(diǎn):"<<endl;cin>>>>>>>>>>>>>>>>
7、;segment_intersect(p1,p2,p3,p4);if(true)cout<<"線段有交點(diǎn)"<<endl;elsecout<<"線段無(wú)交點(diǎn)"<<endl;運(yùn)行結(jié)果:最短路問(wèn)題:#include<iostream>#include<utility>#include<vector>#include<algorithm>usingnamespacestd;typedefpair<double,double>POINT;doubledirec
8、tion(POINTp,POINTp1,POINTp2)POINTv1,v2;=return*on_segment(POINTp,POINTp1,POINTp2)doublemin_x=<?:;doublemax_x=>?:;doublemin_y=<?:;doublemax_y=>?:;if>=min_x&&<=max_x&&>=min_y&&<=max_y)returntrue;elsereturnfalse;POINTstartPoint;boolsortByPolorAngle(constP
9、OINT&p1,constPOINT&p2)(doubled=direction(startPoint,p1,p2);if(d<0)returntrue;if(d>0)returnfalse;if(d=0&&on_segment(startPoint,p1,p2)returntrue;if(d=0&&on_segment(p2,startPoint,p1)returntrue;returnfalse;voidfind_convex_hull(vector<POINT>&point)(POINTp0=point0;i
10、ntk=0;for(inti=0;i<();i+)(if(pointi.second<|pointi.second=&&pointi.first<(p0=pointi;k=i;()+k);(),p0);vector<POINT>convex_hull;do(point0);startPoint=point0;();sort(),(),sortByPolorAngle);if(point0=convex_hull0)break;(convex_hull()-1);while(1);for(inti=0;i<();i+)cout<<convex_hulli.first<<''<<convex_hulli.second<<endl;intmain()(vector<POINT>pv;doublex,y;inti;cout<<"請(qǐng)輸入5個(gè)點(diǎn)<x,y>:"<<endl;for(i=1;i<5;i+)(cou
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 【正版授權(quán)】 ISO 10678:2024 EN Fine ceramics (advanced ceramics,advanced technical ceramics) - Determination of photocatalytic activity of surfaces in an aqueous medium by degradation o
- 內(nèi)江市第一人民醫(yī)院?jiǎn)T額人員招聘考試試卷及答案
- 鑒賞語(yǔ)言的角度與方法-微課設(shè)計(jì)
- 崇陽(yáng)縣中醫(yī)院招聘考試試卷及答案
- 理想演講稿集錦十篇
- 新學(xué)期計(jì)劃范本7篇
- 父母感恩演講稿范例5篇
- 新學(xué)期的計(jì)劃范例集錦10篇
- 2014年內(nèi)蒙古呼和浩特市中考數(shù)學(xué)試卷(含解析版)
- 2014年貴州省黔南州中考數(shù)學(xué)試卷(含解析版)
- Q∕SY 1583-2013 二元復(fù)合驅(qū)用表面活性劑技術(shù)規(guī)范
- GB∕T 19545.1-2012 單臂操作助行器具 要求和試驗(yàn)方法 第1部分:肘拐杖
- 瑞思eaas測(cè)評(píng)系統(tǒng)介紹及考試報(bào)告解讀6
- IgG4相關(guān)性疾病醫(yī)學(xué)教學(xué)課件
- 創(chuàng)意C4D低碳環(huán)保綠色出行PPT模板
- 消防工程施工組織設(shè)計(jì)(標(biāo)準(zhǔn)版)58154
- 社會(huì)組織公益項(xiàng)目評(píng)估指標(biāo)表
- 滅火器檢查記錄表
- 中南大學(xué)本科、研究生畢業(yè)證書(shū)樣本掃描件
- 四年級(jí)奧數(shù)舉一反三-用假設(shè)法解題(課堂PPT)
- 食品分析實(shí)驗(yàn)考試計(jì)算題(答案版)
評(píng)論
0/150
提交評(píng)論