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

1、程序設(shè)計(jì)藝術(shù)與方法課程實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)三計(jì)算幾何算法的實(shí)現(xiàn)一、實(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)題：給定一個(gè)內(nèi)含阻礙墻的房間，求解出一條從起點(diǎn)到終點(diǎn)的最最短路徑。

2、房間的邊界固定在x=0,x=10,y=0和y=10。起點(diǎn)和終點(diǎn)固定在(0,5)和(10,5)。房間里還有0至U 18個(gè) 墻，每個(gè)墻有兩個(gè)門(mén)。輸入給定的墻的個(gè)數(shù)，每個(gè)墻的x位置和兩個(gè)門(mén)的y坐標(biāo)區(qū)間，輸出最短路的長(zhǎng)度。下圖是個(gè)例子：實(shí)驗(yàn)名稱實(shí)驗(yàn)日期6.5指導(dǎo)教師徐本柱系院專(zhuān)業(yè)班 級(jí)四、實(shí)驗(yàn)結(jié)果與分析(源程序及相關(guān)說(shuō)明)思考：判線段相交時(shí)，如果有個(gè)線段的端點(diǎn)在另一條線段上，注意可能與另一條線段上的端點(diǎn)重合，思考這樣的情況怎么辦。用跨立的方法。線段相交滿足且只需滿足如下兩個(gè)條件就可以了：(1) 兩條線段相互跨立；(2) 一條線段的一個(gè)端點(diǎn)在另一條線段上。如果兩線段相交，則兩線段必然相互跨立對(duì)方，若p1

3、p2跨立卩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 #in clude using n ames pace std;typ edef pair P OINT;double directio n(P OINT p,P OINT p 1, POINT p2)POINT v1,v2;vl.first =p

4、 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=p l.first p2.first?pl.first:p2.first;double min_y=p l.sec ondp 2.sec ond?p

5、 1.sec ond:p 2.sec ond;if(p. first=min_x&p. first=min_y&p. sec on d0 & d20 II d10 )&( d30 & d40 | d30) 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 if (d4=0 & on_segme n

6、t( p4, p1, p2) return true;elsereturn false;int mai n()POINT p1, p2, p3,p4;cout請(qǐng)輸入四個(gè)點(diǎn)：p 1.first p 1.sec ondp 2.first p 2.sec ondp 3.first p 3.sec ondp4 .firstp4 .sec ond; segme nt_in tersect (p1,p2,p3,p4);if(true)cout線段有交點(diǎn)endl;elsecout線段無(wú)交點(diǎn)endl;運(yùn)行結(jié)果:最短路問(wèn)題:#in elude #in clude #in clude #i nclude usin

7、g n ames pace std;typ edef pairP 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.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

8、p,P OINT p1, POINT p2)double min_x=p 1.first p2.first?p1.first:p2.first;double min_y=p l.sec ondp 2.sec ond?p l.sec ond:p 2.sec ond;if(p. first=min_x&p. first=min_y&p. sec on d=max_y) return true;請(qǐng)wA四T點(diǎn):12231210 0線段無(wú)交點(diǎn)ProcessProcess rsturnedrsturnedPressPress anyany keykey toto00 x0)0 x0) executione

9、xecution timetime : :continue.continue.ProcessProcessreturnedreturnedPressPress anyany keykey toto0 COiO)COiO) executionexecution timetime : :continue.continue.8. 030030 s selsereturn false;POINT start Poi nt;bool sortBy PolorA ngle(co nst P OINT&p 1,co nst P OINT&p2) double d=directi on( start Poin

10、 t, p1,p 2); if(d0)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) P OINT p0=poin t0;int k=0;for(i nt i=0;i poin t.size();i+)if(poin ti.sec ondp0 .sec on d| poin ti.sec on

11、d=p0 .sec ond&poin ti.firstp0 .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_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;ic on vex_hull.size();i+)coutc on vex_hulli.first c on vex_hulli.sec on de ndl;int m