合工大程序設(shè)計(jì)與藝術(shù)實(shí)驗(yàn)三

1、程序設(shè)計(jì)藝術(shù)與方法課程實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱實(shí)驗(yàn)三計(jì)算幾何算法的實(shí)現(xià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) 房間最短路

2、問(wèn)題：給定一個(gè)內(nèi)含阻礙墻的房間，求解岀一條從起點(diǎn)到終點(diǎn)的最最短路徑。房間的邊界固定在x=0,x=10,y=0 和y=10。起點(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)重合，思考這樣的情況怎么辦。用跨立的方法。線段相交滿足且只需滿足如下兩個(gè)條件就可以了：(1) 兩條線段相互跨立；(2) 一條線段的一個(gè)端點(diǎn)在另一條線段上。如果兩線段相交，則兩線段必然相

3、互跨立對(duì)方，若p1p2 跨立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。#in clude<iostream>#i nclude<utility>usingn amespacestd;typedefpair<double,double&g

4、t;POINT;doubledirectio n(POINTp,POINTp1,POINTp2)P0INTv1,v2;=&&<=max_x&&>=min_ y&&<=max_y)returntrue;elsereturnfalse;boolsegme nt_i ntersect(POINTp1,POINTp2,POINTp3,POINTp4)doubled仁directi on( p3,p4,p1);doubled2=directi on( p3,p4,p2);doubled3=directi on (p1,p2,p3);dou

5、bled4=directi on( 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_segme nt(p1,p3,p4)returntrue;elseif(d2=0&&on_segme nt(p2,p3,p4)returntrue;elseif(d3=0&&on_segme nt(p3,p1,

6、p2)returntrue;elseif(d4=0&&on_segme nt(p4,p1,p2)returntrue;elsereturnfalse;in tmai n()POINTp1,p2,p3,p4;cout<< "請(qǐng)輸入四個(gè)點(diǎn)："<<e ndl;cin>>>>>>>>>>>>>>>>segme nt_in tersect(p1,p2,p3,p4);if(true)coutvv"線段有交點(diǎn)"<<endl

7、;elsecout«"線段無(wú)交點(diǎn)"<<endl;運(yùn)行結(jié)果：最短路問(wèn)題：#in clude<iostream>#i nclude<utility>#in clude<vector>#i nclude<algorithm>usingn amespacestd;typedefpair<double,double>POINT;doubledirectio n(POINTp,POINTp1,POINTp2)P0INTv1,v2;=&&<=max_x&&>=mi

8、n_ y&&<=max_y) returntrue;elsereturnfalse;POINTstartPo int;boolsortByPolorA ngle(co nstPOINT&p1,con stPOINT&p2) doubled=directi on( startPo in t,p1,p2);if(d<0) returntrue;if(d>0)returnfalse;if(d=0&&on _segme nt(startPo in t,p1,p2) returntrue;if(d=0&&on_ segme

9、 nt(p2,startPo in t,p1) returntrue;returnfalse;voidfi nd_con vex_hull(vector<POINT >&poi nt)POINTp0=poi ntO;in tk=0;for(i nti=O;i<();i+)if(po in ti.sec on d<|po in ti.sec ond=&&poin ti.first<p0=poi nti;k=i;()+k);(),p0);vector<POINT>co nvex_hull;do(poi ntO);startPoi n

10、t=poi ntO;();sort(),(),sortByPolorA ngle);if(poi nt0=co nvex_hullO)break;(co nvex_hull()-1);while(1);for(i nti=O;i<();i+)cout«c on vex_hulli.first<v"v<c on vex_hulli.sec on d<<e ndl;in tmai n()vector<POINT>pv;doublex,y;in ti;cout«"請(qǐng)輸入 5 個(gè)點(diǎn) <x,y>:"<<endl;for(i=1;i<5;i+)cout<&l