合工大程序設計與藝術試驗三

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

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

3、跨立p3P4,則(p1-p3)X(p4-p3)*(p2-p3)X(p4-p3)>0,當(p1-p3)X(p4-p3)=0時，說明p1,p3,p4共線，但是因為已經通過了快速排斥實驗，所以點p1一定在線段p3,p4上。所以判斷線段p1p2,p3P4相交的依據是(p1-p3)X(p4-p3)*(p2-p3)X(p4-p3)>=0。#include<iostream>#include<utility>usingnamespacestd;typedefpair<double,double>POINT;doubledirection(POINTp,POIN

4、Tp1,POINTp2)POINTv1,v2;=;=;=return*on_segment(POINTp,POINTp1,POINTp2)doublemin_x=<?:;doublemax_x=>?:;doublemin_y=<?:;doublemax_y=>?:;if>=min_x&&<=max_x&&>=min_y&&<=max_y)returntrue;elsereturnfalse;)boolsegment_intersect(POINTp1,POINTp2,POINTp3,POINTp4)

5、doubled1=direction(p3,p4,p1);doubled2=direction(p3,p4,p2);doubled3=direction(p1,p2,p3);doubled4=direction(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_segment(p1,p3,p4)returntrue;elseif(

6、d2=0&&on_segment(p2,p3,p4)returntrue;elseif(d3=0&&onsegment(p3,p1,p2)returntrue;elseif(d4=0&&on_segment(p4,p1,p2)returntrue;elsereturnfalse;intmain()POINTp1,p2,p3,p4;cout<<"請輸入四個點："<<endl;cin>>>>>>>>>>>>>>>>

7、;segment_intersect(p1,p2,p3,p4);if(true)cout<<"線段有交點"<<endl;elsecout<<"線段無交點"<<endl;運行結果：最短路問題：#include<iostream>#include<utility>#include<vector>#include<algorithm>usingnamespacestd;typedefpair<double,double>POINT;doubledirec

8、tion(POINTp,POINTp1,POINTp2)POINTv1,v2;=return*on_segment(POINTp,POINTp1,POINTp2)doublemin_x=<?:;doublemax_x=>?:;doublemin_y=<?:;doublemax_y=>?:;if>=min_x&&<=max_x&&>=min_y&&<=max_y)returntrue;elsereturnfalse;POINTstartPoint;boolsortByPolorAngle(constP

9、OINT&p1,constPOINT&p2)(doubled=direction(startPoint,p1,p2);if(d<0)returntrue;if(d>0)returnfalse;if(d=0&&on_segment(startPoint,p1,p2)returntrue;if(d=0&&on_segment(p2,startPoint,p1)returntrue;returnfalse;voidfind_convex_hull(vector<POINT>&point)(POINTp0=point0;i

10、ntk=0;for(inti=0;i<();i+)(if(pointi.second<|pointi.second=&&pointi.first<(p0=pointi;k=i;()+k);(),p0);vector<POINT>convex_hull;do(point0);startPoint=point0;();sort(),(),sortByPolorAngle);if(point0=convex_hull0)break;(convex_hull()-1);while(1);for(inti=0;i<();i+)cout<<convex_hulli.first<<''<<convex_hulli.second<<endl;intmain()(vector<POINT>pv;doublex,y;inti;cout<<"請輸入5個點<x,y>:"<<endl;for(i=1;i<5;i+)(cou