计算几何算法实现

《计算几何算法实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、。房间的边界固定在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。起

3、点和重点固定在(0,5)和(10,5)。房间里还有0到18个墙，每个墙有两个门。输入给定的墙的个数，每个墙的x位置和两个门的y坐标区间，输出最短路的长度。下图是个例子：四、实验结果与分析（源程序及相关说明）1)#include#include#include#includeusingnamespacestd;typedefpairPOINT;//线段//fuctiondirctiondeterminesthedirectionthattheseqment//p1pturnst

4、op2pwithrespecttopointp//ifreturnvalueispositive,meansclockwise;//ifreturnvalueisnegative,meanscounter-clockwise;//naughtmeansonthesameline;doubledirection(POINTp,POINTp1,POINTp2){POINTv1,v2;v1.first=p2.first-p1.first;v1.second=p2.second-p1.first;v2.first=p1.first-p.first;v2.second=p1.second-

5、p.second;returnv1.first*v2.second-v1.second*v2.second;}//fuctionon_seqmentdetermineswhetherthepointpisonthesegmentp1p2boolon_segment(POINTp,POINTp1,POINTp2){doublemin_x=p1.firstp2.first?p1.first:p2.first;doublemin_y=p1.second

6、d:p2.second;doublemax_y=p1.second>p2.second?p1.second:p2.second;if(p.first>=min_x&&p.first=min_y&&p.second<=max_y)returntrue;elsereturnfalse;}//pointstartPointisthepolorpointthatisneededforcomparingtwootherpoinr;POINTstartPoint;//functionsortByPolorAngleprovidestherealizingof

7、comparingtwopoints,whichsupport//theSTLfunctionsort();boolsortByPolorAngle(constPOINT&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_segm