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