内容发布更新时间 : 2024/6/18 19:06:34星期一 下面是文章的全部内容请认真阅读。

《程序设计艺术与方法》课程实验报告 实验名称 计算几何算法的实现 姓 名 系院专业 计算机与信息 指导教师 班 级 学 号 实验日期 2012年11月8日 成 绩 一、实验目的和要求 (1) 理解线段的性质、叉积和有向面积。 (2) 掌握寻找凸包的算法。 (3) 综合运用计算几何和搜索中的知识求解有关问题。 二、实验预习内容 (1) 将讲义第三章第三节中的凸包代码上机运行并检验结果。 (2) 完成讲义第三章的课后习题，上机运行并检验结果。 (3) 思考： 判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的 端点重合，思考这样的情况怎么办。 (4) 房间最短路问题： 给顶一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房间的边界 固定在x=0,x=10,y=0 和y=10。起点和重点固定在(0,5)和(10,5)。房间里还有0 到18 个 墙，每个墙有两个门。输入给定的墙的个数，每个墙的x 位置和两个门的y 坐标区间， 输出最短路的长度。 三 实验项目摘要 (1) 将讲义第三章第三节中的凸包代码上机运行并检验结果。 (2) 完成讲义第三章的课后习题，上机运行并检验结果。 (3) 思考：判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的端点重合，思考这样的情况怎么办。 (4) 房间最短路问题：给顶一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房间的边界固定在x=0,x=10,y=0 和y=10。起点和重点固定在(0,5)和(10,5)。房间里还有0 到18 个墙，每个墙有两个门。输入给定的墙的个数，每个墙的x 位置和两个门的y 坐标区间，输出最短路的长度。下图是个例子：

四、实验结果与分析（源程序及相关说明） 1)#include #include #include #include using namespace std;

typedef pair POINT;//线段

//fuction dirction determines the direction that the seqment //p1p turns to p2p with respect to point p //if return value is positive,means clockwise;

//if return value is negative,means counter-clockwise; //naught means on the same line;

double direction(POINT p,POINT p1,POINT p2){ POINT v1,v2; v1.first=p2.first-p1.first; v1.second=p2.second-p1.first; v2.first=p1.first-p.first; v2.second=p1.second-p.second; return v1.first*v2.second-v1.second*v2.second;} //fuction on_seqment determines whether the point p is on the segment p1p2

bool on_segment(POINT p,POINT p1,POINT p2){ double min_x=p1.firstp2.first?p1.first:p2.first; double min_y=p1.secondp2.second?p1.second:p2.second; if(p.first>=min_x&&p.first= min_y&&p.second<=max_y) return true; else return false;}

//point startPoint is the polor point that is needed for comparing two other poinr; POINT startPoint;

//function sortByPolorAngle provides the realizing of comparing two points,which support //the STL function sort();

bool sortByPolorAngle(const POINT &p1,const POINT &p2) {

double d=direction(startPoint,p1,p2); if(d<0)return true; if(d>0)return false; if(d==0&&on_segment(startPoint,p1,p2))return true; if(d==0&&on_segment(p2,startPoint,p1))return true; return false; }

//here realizes the process of finding convex hull void find_convex_hull(vector&point) { POINT p0=point[0]; int k=0; for(int i=0;i

point[i].second==p0.second&&point[i].firstconvex_hull; do{ convex_hull.push_back(point[0]); startPoint=point[0]; point.erase(point.begin()); sort(point.begin(),point.end(),sortByPolorAngle); if(point[0]==convex_hull[0])break; point.push_back(convex_hull[convex_hull.size()-1]); }while(1); for(int j=0;j pv; double x,y; int i; cout<<\请输入10个点：\ for(i=1;i<=10;i++){ cout<<\ cin>>x>>y; pv.push_back(make_pair(x,y));} cout<