合工大程序設(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)實(shí)驗(yàn)日期系院專業(yè)6.5班 級(jí)指導(dǎo)教師徐本柱一、實(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至U 18個(gè) 墻，每個(gè)墻有兩個(gè)門。輸入給定的墻的個(gè)數(shù)，每個(gè)墻的x位置和兩個(gè)門的 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跨立卩3卩4,則(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>#in clude <utility>using n ames pace std;typ edef pair<double,double> P O

4、INT;double directio n(P OINT p,P OINT p 1, POINT p2)POINT v1,v2;vl.first =p 2.first -p. first ;v1.sec ond=p 2.sec ond-p .sec ond;v2.first =p 1.first -p .first;v2.sec ond=p 1.sec ond-p .sec ond;return v1.first*v2.sec on d-v1.sec on d*v2.first;bool on_segme nt( POINT p,P OINT p1, POINT p2)double min_x

5、=p l.first <p 2.first ?p l.first:p 2.first; double max x=pl.first>p2.first?pl.first:p2.first;double min_y=p l.sec ond<p 2.sec ond?p l.sec ond:p 2.sec ond;double max_y=p 1.sec ond>p 2.sec ond?p 1.sec ond:p 2.sec ond;if(p. first>=min_x&&p. first<=max_x&&p. sec on d>

6、;=min_y&&p. sec on d<=max_y) return true;elsereturn false;bool segme nt_in tersect( POINT p 1, POINT p 2, POINT p 3, POINT p4)double d1=direct ion(p3,p4,p 1);double d2=directio n(p 3, p4, p2);double d3=directio n(p1,p2,p 3);double d4=direct ion(p1,p2,p 4);if (d1>0 && d2<0 II

7、 d1<0 && d2>0 )&&( d3>0 && d4<0 | d3<0 && d4>0) return true;else if (d1=0 && on_segme nt(p 1, p3, p4) return true;else if (d2=0 && on_segme nt(p 2, p3, p4) return true;else if (d3=0 && on_segme nt( p3, p1, p2) return true;else

8、 if (d4=0 && on_segme nt( p4, p1, p2) return true;elsereturn false;int mai n()POINT p1, p2, p3,p4;cout<<"請(qǐng)輸入四個(gè)點(diǎn)："<<e ndl;cin>>p 1.first> >p 1.sec ond>>p 2.first> >p 2.sec ond>>p 3.first> >p 3.sec ond>>p4 .first>p4 .sec ond; s

9、egme nt_in tersect (p1,p2,p3,p 4);if(true)cout<<"線段有交點(diǎn)"<<endl;elsecout<<"線段無(wú)交點(diǎn)"<<endl;運(yùn)行結(jié)果:請(qǐng)wA四T點(diǎn):12231210線段無(wú)交點(diǎn)Process rsturned Press any key to0 0x0) execution time : continue.Process returned Press any key to0 COiO) execution time : continue.8. 030 s最短路問(wèn)

10、題:#in elude <iostream> #in clude <utility>#in clude <vector>#i nclude <algorithm> using n ames pace std;typ edef pair<double,double >P OINT;double directio n(P OINT p,P OINT p 1, POINT p2) POINT v1,v2;vl.first =p 2.first -p. first;v1.sec ond=p 2.sec ond-p .sec ond;v2.fi

11、rst =p 1.first -p. first;v2.sec ond=p 1.sec ond-p .sec ond;return v1.first*v2.sec on d-v1.sec on d*v2.first;bool on_segme nt( POINT p,P OINT p1, POINT p2)double min_x=p 1.first <p 2.first ?p 1.first:p 2.first;double max x=p1.first>p2.first?p1.first:p2.first;double min_y=p l.sec ond<p 2.sec

12、ond?p l.sec ond:p 2.sec ond;double max_y=p l.sec ond>p 2.sec ond?p l.sec ond:p 2.sec ond;if(p. first>=min_x&&p. first<=max_x&&p. sec on d>=min_y&&p. sec on d<=max_y) return true;elsereturn false;POINT start Poi nt;bool sortBy PolorA ngle(co nst P OINT&p 1,c

13、o nst P OINT&p2) double d=directi on( start Poin t, p1,p 2); if(d<0)return true;if(d>0)return false;if(d=0&&O n_segme nt(start Poi nt, p1,p2) return true;if(d=0&&O n_segme nt(p 2,start Poi nt,p1) return true;return false;void find_con vex_hull(vector< POINT&p oi nt)

14、P OINT p0=poin t0;int k=0;for(i nt i=0;i <poin t.size();i+)if(poin ti.sec ond<p0 .sec on d| poin ti.sec ond=p0 .sec ond&&poin ti.first <p0 .first) pO=poin ti; k=i;poin t.erase( poin t.begi n()+k);poin t.i nsert (poin t.begi n(),p 0); vectorv POINTcon vex_hull; do con vex_hull .p ush

15、_back (poin t0);start Point=poin t0;poin t.erase( poin t.beg in();sort (poin t.beg in(),poin t.e nd(),sortB yPolorAn gle);if (poin tO=co nvex_hull0)break;point-push back(c onvex hullc on vex hull.size()-1);while ；for (int i=0;i<c on vex_hull.size();i+)cout<<c on vex_hulli.first<<' '<<c on vex_hulli.sec on d<<e ndl;int mai n()vector< POINTpv;double x,y;int i;cout<<"請(qǐng)輸入 5 個(gè)點(diǎn) <x,y>:"<<endl; for(i=1;i<5;i+)cout<<