合工大程序设计与艺术实验三

1、程序设计艺术与方法课程实验报告实验名称实验三计算几何算法的实现实验日期系院专业6.5班 级指导教师徐本柱一、实验目的和要求(1) 理解线段的性质、叉积和有向面积。(2) 掌握寻找凸包的算法。(3) 综合运用计算几何和搜索中的知识求解有关问题。二、实验预习内容1 .掌握线段的性质以及叉积和有向面积的计算方法。2 .预习寻找凸包的算法。三、实验项目摘要(1) 将讲义第三章第三节中的凸包代码上机运行并检验结果。(2) 完成讲义第三章的课后习题，上机运行并检验结果。(3) 思考：判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的端点重合，思考 这样的情况怎么办。(4) 房间最短路

2、问题：给定一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房间的边界固定在x=0,x=10,y=0和y=10。起点和终点固定在(0,5)和(10,5)。房间里还有 0至U 18个 墙，每个墙有两个门。输入给定的墙的个数，每个墙的x位置和两个门的 y坐标区间，输出最短路的长度。下图是个例子：四、实验结果与分析(源程序及相关说明)思考：判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的端点重合，思考这样的情况怎么办。用跨立的方法。线段相交满足且只需满足如下两个条件就可以了：(1) 两条线段相互跨立；(2) 一条线段的一个端点在另一条线段上。如果两线段相交，则两线段必

3、然相互跨立对方，若p1p2跨立卩3卩4,则(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。#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<<"请输入四个点："<<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<<"线段有交点"<<endl;elsecout<<"线段无交点"<<endl;运行结果:请wA四T点:12231210线段无交点Process rsturned Press any key to0 0x0) execution time : continue.Process returned Press any key to0 COiO) execution time : continue.8. 030 s最短路问

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<<"请输入 5 个点 <x,y>:"<<endl; for(i=1;i<5;i+)cout<<