您所在位置：网站首页 > 商业/管理/HR > 营销创新合工大程序设计与艺术实验三

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

5页

卖家[上传人]：工****

文档编号：497581212

上传时间：2022-10-22

文档格式：DOCX

文档大小：21.34KB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 金贝

/ 5 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、程序设计艺术与方法课程实验报告实验名称实验三计算几何算法的实现姓名系院专业班级学号实验日期指导教师徐本柱成绩一、实验目的和要求(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坐标区间，输出最矩路的长度。卜图是个例子：四、实验结果与分析(源程序及相关说明)思考：判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的端点重

2、合，思考这样的情况怎么办。用跨立的方法。线段相交满足且只需满足如下两个条件就可以了：(1)两条线段相互跨立；(2)一条线段的一个端点在另一条线段上。如果两线段相交，则两线段必然相互跨立对方，若p1p2跨立p3P4,则(p1-p3)X(p4-p3)*(p2-p3)X(p4-p3)0,当(p1-p3)X(p4-p3)=0时，说明p1,p3,p4共线，但是因为已经通过了快速排斥实验，所以点pl一定在线段p3,p4上。所以判断线段p1p2,p3P4相交的依据是(p1-p3)X(p4-p3)*(p2-p3)X(p4-p3)=0。#include#includeusingnamespacestd;typedefpairPOINT;doubledirection(POINTp,POINTp1,POINTp2)POINTv1,v2;=;=;=return*on_segment(POINTp,POINTp1,POINTp2)doublemin_x=:;doublemin_y=:;if=min_x&=min_y&0&d20|d10)&(d30&d40|d30)returntrue;elseif(d1=0&

3、on_segment(p1,p3,p4)returntrue;elseif(d2=0&on_segment(p2,p3,p4)returntrue;elseif(d3=0&onsegment(p3,p1,p2)returntrue;elseif(d4=0&on_segment(p4,p1,p2)returntrue;elsereturnfalse;intmain()POINTp1,p2,p3,p4;cout请输入四个点：;segment_intersect(p1,p2,p3,p4);if(true)cout线段有交点endl;elsecout线段无交点endl;运行结果：最短路问题：#include#include#include#includealgorithmusingnamespacestd;typedefpairPOINT;doubledirection(POINTp,POINTp1,POINTp2)POINTv1,v2;=return*on_segment(POINTp,POINTp1,POINTp2)doublemin_x=:;doublemin_y=:;if=min_x&

4、=min_y&=max_y)returntrue;elsereturnfalse;POINTstartPoint;boolsortByPolorAngle(constPOINT&p1,constPOINT&p2)doubled=direction(startPoint,p1,p2);if(d0)returnfalse;if(d=0&on_segment(startPoint,p1,p2)returntrue;if(d=0&on_segment(p2,startPoint,p1)returntrue;returnfalse;voidfind_convex_hull(vector&point)POINTp0=point0;intk=0;for(inti=0;i();i+)if(pointi.second|pointi.second=&pointi.firstp0=pointi;k=i;()+k);(),p0);vectorconvex_hull;do(point0);startPoint=point0;();sort(),(),sortByPolorAngle);if(point0=convex_hull0)break;(convex_hull()-1);while(1);for(inti=0;i();i+)coutconvex_hulli.firstconvex_hulli.secondendl;intmain()(vectorpv;doublex,y;inti;cout请输入5个点:endl;for(i=1;i5;i+)(coutNoixy;(make_pair(x,y);coutendl;find_convex_hull(pv);system(Pause);return0;运行结果：

《合工大程序设计与艺术实验三》由会员工****分享，可在线阅读，更多相关《合工大程序设计与艺术实验三》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源