《程序设计艺术与方法》课程实验报告实验名称姓名实验日期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
