合工大程序設(shè)計與藝術(shù)實驗三

1、程序設(shè)計藝術(shù)與方法課程實驗報告實驗名稱實驗三計算幾何算法的實現(xiàn)姓名系院專業(yè)班級學(xué)號實驗日期指導(dǎo)教師徐本柱成績一、實驗?zāi)康暮鸵?1) 理解線段的性質(zhì)、叉積和有向面積。(2) 掌握尋找凸包的算法。(3) 綜合運用計算幾何和搜索中的知識求解有關(guān)問題。二、實驗預(yù)習(xí)內(nèi)容1 掌握線段的性質(zhì)以及叉積和有向面積的計算方法。2.預(yù)習(xí)尋找凸包的算法。三、實驗項目摘要(1) 將講義第三章第三節(jié)中的凸包代碼上機運行并檢驗結(jié)果。(2) 完成講義第三章的課后習(xí)題，上機運行并檢驗結(jié)果。(3) 思考：判線段相交時，如果有個線段的端點在另一條線段上，注意可能與另一條線段上的端點重合，思考這樣 的情況怎么辦。(4) 房間最短路

2、問題：給定一個內(nèi)含阻礙墻的房間，求解岀一條從起點到終點的最最短路徑。房間的邊界固定在x=0,x=10,y=0 和y=10。起點和終點固定在(0,5)和(10,5)。房間里還有 0到18個 墻，每個墻有兩個門。輸入給定的墻的個數(shù)，每個墻的x位置和兩個門的y坐標區(qū)間，輸岀最短路的長度。下圖是個例子：四、實驗結(jié)果與分析(源程序及相關(guān)說明)思考：判線段相交時，如果有個線段的端點在另一條線段上，注意可能與另一條線段上的端點重合，思考這樣的情況怎么辦。用跨立的方法。線段相交滿足且只需滿足如下兩個條件就可以了：(1) 兩條線段相互跨立；(2) 一條線段的一個端點在另一條線段上。如果兩線段相交，則兩線段必然相

3、互跨立對方，若p1p2 跨立p3p4，則(p1-p3 )X (p4-p3)*( p2-p3 )X(p4-p3)>0，當(p1-p3 )X (p4-p3)=0時，說明p1,p3,p4共線，但是因為已經(jīng)通過了快速排斥實驗，所以點 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<< "請輸入四個點："<<e ndl;cin>>>>>>>>>>>>>>>>segme nt_in tersect(p1,p2,p3,p4);if(true)coutvv"線段有交點"<<endl

7、;elsecout«"線段無交點"<<endl;運行結(jié)果：最短路問題：#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«"請輸入 5 個點 <x,y>:"<<endl;for(i=1;i<5;i+)cout<&l