《程序设计艺术与方法》课程实验报告
实验名称 姓 名 实验日期 6.5 系院专业 指导教师 实验三 计算几何算法的实现 班 级 徐本柱 学 号 成 绩 一、实验目的和要求 (1) 理解线段的性质、叉积和有向面积。 (2) 掌握寻找凸包的算法。 (3) 综合运用计算几何和搜索中的知识求解有关问题。 二、实验预习内容 1．掌握线段的性质以及叉积和有向面积的计算方法。 2．预习寻找凸包的算法。 三、实验项目摘要 (1) 将讲义第三章第三节中的凸包代码上机运行并检验结果。 (2) 完成讲义第三章的课后习题，上机运行并检验结果。 (3) 思考： 判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的端点重合，思考这样的情况怎么办。 (4) 房间最短路问题： 给定一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房间的边界 固定在 x=0,x=10,y=0 和 y=10。起点和终点固定在(0,5)和(10,5)。房间里还有 0 到 18 个 墙，每个墙有两个门。输入给定的墙的个数，每个墙的 x 位置和两个门的 y 坐标区间， 输出最短路的长度。下图是个例子：
四、实验结果与分析（源程序及相关说明） 思考： 判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的端点重合，思考这样的情况怎么办。 用跨立的方法。线段相交满足且只需满足如下两个条件就可以了： （1）两条线段相互跨立； （2）一条线段的一个端点在另一条线段上。 如果两线段相交，则两线段必然相互跨立对方，若p1p2跨立p3p4，则（p1-p3）×(p4-p3)*（p2-p3）×(p4-p3)>0，当（p1-p3）×(p4-p3)=0时，说明p1,p3,p4共线，但是因为已经通过了快速排斥实验，所以点p1一定在线段p3,p4上。所以判断线段p1p2,p3p4相交的依据是（p1-p3）×(p4-p3)*（p2-p3）×(p4-p3)>=0。 #include #include using namespace std; typedef pair POINT; double direction(POINT p,POINT p1,POINT p2) { POINT v1,v2; v1.first =p2.first -p.first ; v1.second=p2.second-p.second; v2.first =p1.first -p.first; v2.second=p1.second-p.second; return v1.first*v2.second-v1.second*v2.first; } 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<=max_x&&p.second>=min_y&&p.second<=max_y) return true; else return false; } bool segment_intersect(POINT p1,POINT p2,POINT p3,POINT p4) { double d1=direction(p3,p4,p1); double d2=direction(p3,p4,p2); double d3=direction(p1,p2,p3); double d4=direction(p1,p2,p4); if ((d1>0 && d2<0 || d1<0 && d2>0 )&&( d3>0 && d4<0 || d3<0 && d4>0)) return true; else if (d1==0 && on_segment(p1,p3,p4)) return true; else if (d2==0 && on_segment(p2,p3,p4)) return true; else if (d3==0 && on_segment(p3,p1,p2)) return true; else if (d4==0 && on_segment(p4,p1,p2)) return true; else return false; } int main() { POINT p1,p2,p3,p4; cout<<\请输入四个点：\ cin>>p1.first>>p1.second>>p2.first>>p2.second>>p3.first>>p3.second>>p4.first>>p4.second; segment_intersect(p1,p2,p3,p4); if(true) cout<<\线段有交点\ else cout<<\线段无交点\} 运行结果：
最短路问题： #include #include #include #include using namespace std; typedef pairPOINT; double direction(POINT p,POINT p1,POINT p2) { POINT v1,v2; v1.first=p2.first-p.first; v1.second=p2.second-p.second; v2.first=p1.first-p.first; v2.second=p1.second-p.second; return v1.first*v2.second-v1.second*v2.first; } 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<=max_x&&p.second>=min_y&&p.second<=max_y) return true; else return false; } POINT startPoint; 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; } void find_convex_hull(vector&point) { POINT p0=point[0]; int k=0; for(int i=0;i convex_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 i=0;ipv; double x,y; int i; cout<<\请输入5个点:\ for(i=1;i<5;i++) { cout<<\ cin>>x>>y; pv.push_back(make_pair(x,y)); } cout<
} while (1); for (int i=0;ipv; double x,y; int i; cout<<\请输入5个点:\ for(i=1;i<5;i++) { cout<<\ cin>>x>>y; pv.push_back(make_pair(x,y)); } cout< 本文来源：https://www.bwwdw.com/article/qktp.html