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

1、程序設(shè)計(jì)藝術(shù)與方法課程實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱實(shí)驗(yàn)三計(jì)算幾何算法的實(shí)現(xiàn)姓名系院專業(yè)班級(jí)學(xué)號(hào)實(shí)驗(yàn)日期指導(dǎo)教師徐本柱成績一、實(shí)驗(yàn)?zāi)康暮鸵?1)理解線段的性質(zhì)、叉積和后向回積。(2)掌握尋找凸包的算法。(3)綜合運(yùn)用計(jì)算幾何和搜索中的知識(shí)求解有關(guā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、個(gè)內(nèi)含阻礙墻的房間，求解出一條從起點(diǎn)到終點(diǎn)的最最短路徑。房間的邊界固定在x=0,x=10,y=0和y=10o起點(diǎn)和終點(diǎn)固定在(0,5)和(10,5)。房間里還有0到18個(gè)墻，每個(gè)墻有兩個(gè)門。輸入給定的墻的個(gè)數(shù)，每個(gè)墻的x位置和兩個(gè)門的y坐標(biāo)區(qū)間，輸出最矩路的長度。卜圖是個(gè)例子：四、實(shí)驗(yàn)結(jié)果與分析(源程序及相關(guān)說明)思考：判線段相交時(shí)，如果有個(gè)線段的端點(diǎn)在另一條線段上，注意可能與另一條線段上的端點(diǎn)重合，思考這樣的情況怎么辦。用跨立的方法。線段相交滿足且只需滿足如下兩個(gè)條件就可以了：(1)兩條線段相互跨立；(2)一條線段的一個(gè)端點(diǎn)在另一條線段上。如果兩線段相交，則兩線段必然相互跨立對(duì)方，若p1p2

3、跨立p3P4,則(p1-p3)X(p4-p3)*(p2-p3)X(p4-p3)>0,當(dāng)(p1-p3)X(p4-p3)=0時(shí)，說明p1,p3,p4共線，但是因?yàn)橐呀?jīng)通過了快速排斥實(shí)驗(yàn)，所以點(diǎn)p1一定在線段p3,p4上。所以判斷線段p1p2,p3P4相交的依據(jù)是(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<<"請(qǐng)輸入四個(gè)點(diǎn)："<<endl;cin>>>>>>>>>>>>>>>>

7、;segment_intersect(p1,p2,p3,p4);if(true)cout<<"線段有交點(diǎn)"<<endl;elsecout<<"線段無交點(diǎn)"<<endl;運(yùn)行結(jié)果：最短路問題：#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<<"請(qǐng)輸入5個(gè)點(diǎn)<x,y>:"<<endl;for(i=1;i<5;i+)(cou