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

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

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

3、互跨立对方，若p1p2 跨立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。#in clude<iostream>#i nclude<utility>usingn amespacestd;typedefpair<double,double&g

4、t;POINT;doubledirectio n(POINTp,POINTp1,POINTp2)P0INTv1,v2;=&&<=max_x&&>=min_ y&&<=max_y)returntrue;elsereturnfalse;boolsegme nt_i ntersect(POINTp1,POINTp2,POINTp3,POINTp4)doubled仁directi on( p3,p4,p1);doubled2=directi on( p3,p4,p2);doubled3=directi on (p1,p2,p3);dou

5、bled4=directi on( 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_segme nt(p1,p3,p4)returntrue;elseif(d2=0&&on_segme nt(p2,p3,p4)returntrue;elseif(d3=0&&on_segme nt(p3,p1,

6、p2)returntrue;elseif(d4=0&&on_segme nt(p4,p1,p2)returntrue;elsereturnfalse;in tmai n()POINTp1,p2,p3,p4;cout<< "请输入四个点："<<e ndl;cin>>>>>>>>>>>>>>>>segme nt_in tersect(p1,p2,p3,p4);if(true)coutvv"线段有交点"<<endl

7、;elsecout«"线段无交点"<<endl;运行结果：最短路问题：#in clude<iostream>#i nclude<utility>#in clude<vector>#i nclude<algorithm>usingn amespacestd;typedefpair<double,double>POINT;doubledirectio n(POINTp,POINTp1,POINTp2)P0INTv1,v2;=&&<=max_x&&>=mi

8、n_ y&&<=max_y) returntrue;elsereturnfalse;POINTstartPo int;boolsortByPolorA ngle(co nstPOINT&p1,con stPOINT&p2) doubled=directi on( startPo in t,p1,p2);if(d<0) returntrue;if(d>0)returnfalse;if(d=0&&on _segme nt(startPo in t,p1,p2) returntrue;if(d=0&&on_ segme

9、 nt(p2,startPo in t,p1) returntrue;returnfalse;voidfi nd_con vex_hull(vector<POINT >&poi nt)POINTp0=poi ntO;in tk=0;for(i nti=O;i<();i+)if(po in ti.sec on d<|po in ti.sec ond=&&poin ti.first<p0=poi nti;k=i;()+k);(),p0);vector<POINT>co nvex_hull;do(poi ntO);startPoi n

10、t=poi ntO;();sort(),(),sortByPolorA ngle);if(poi nt0=co nvex_hullO)break;(co nvex_hull()-1);while(1);for(i nti=O;i<();i+)cout«c on vex_hulli.first<v"v<c on vex_hulli.sec on d<<e ndl;in tmai n()vector<POINT>pv;doublex,y;in ti;cout«"请输入 5 个点 <x,y>:"<<endl;for(i=1;i<5;i+)cout<&l