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

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

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

3、p2跨立卩3卩4,則(p1-p3)X (p4-p3)*(p2-p3)X(p4-p3)0，當(dāng)(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 #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請輸入四個點：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線段有交點endl;elsecout線段無交點endl;運行結(jié)果:最短路問題:#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;請wA四T點:12231210 0線段無交點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