2012《计算几何》实验任务

2012《计算几何》实验任务基本要求：最低完成100分值的题目。三维房子的显示(40分)目的：熟悉形体线框模型(或半实体模型)的描述方法，熟悉观察变换的实现及其效果。要求：已知一个房子，其在用户坐标系下的坐标如图所示。实现一个程序，可以用对话框任意输入视点坐标，把该房子的平行投影效果显示出来。房子的坐标如下：P0(-80,0,0)，P](80,0,0)，P2(80,0,200)，P3(0,0,260)，P4(-80,220,200)，P5(-80,220,0)，P6(80,220,0)，P7(80,220,200),P8(0,220,260),P9(-80,220,200)。鼓励：如果你能够用虚线显示出隐藏线，本题成绩加20分。判断隐藏线采用如下原则：凸多面体的一条边是不可见的，当且仅当它的两个面是不可见的。凸多面体的一个面是不可见的，当且仅当它的法向与视线的夹角小于90度。参考程序：目录下有可执行的演示程序。多边形的基本计算(30分)目的：熟悉多边形的交互绘制，熟悉多边形的表示，熟悉多边形的基本计算。要求：用户在交互输入一个多边形之后，可以选择菜单，完成下列计算：多边形的面积；多边形的方向；交互输入一点，判断该点在多边形的内外。计算结果以对话框的形式反馈。鼓励：本题没有额外奖励。参考程序：本题没有可执行的演示程序。在实现上，你可利用交互绘制多边形的源程序多边形的三角剖分（30分）目的：熟悉多边形的表示，熟悉多边形三角剖分的切耳算法。要求：用户在交互输入一个多边形之后，通过选择菜单，完成并显示它的三角剖分。鼓励：本题没有额外奖励。参考程序：目录下有可执行的演示程序。在实现上，你可利用交互绘制多边形的源程序平面点集的凸包（30分）目的：熟悉平面点集凸包的生成算法。要求：用户在交互输入若干个点之后，通过选择菜单，生成并显示它的凸包。鼓励：本题没有额外奖励。参考程序：目录下有可执行的演示程序。在实现上，你可以自己编写程序，卷包裹算法也可，也可以利用目录中的Graham扫描算法的控制台源程序。平面点集的Delaunay三角剖分（20分）目的：熟悉平面点集的Delaunay三角剖分及其生成算法。要求：用户在交互输入若干个点之后，通过选择菜单，生成并显示它的Delaunay三角剖分。鼓励：如果你采用的是O（n2）时间算法，额外奖励30分。如果你能够以四种颜色显示每个三角形的内部，并且使得相邻的三角形具有不同的颜色，你也将额外被奖励30分。参考程序：目录下有可执行的演示程序。在实现上，你可以利用O（n4）时间的控制台源程序，也可以利用O（n2）时间的控制台源程序。如果你想着色，需要重构出三角剖分的数据结构。多边形的布尔集合运算（60分）

目的：熟悉多边形的布尔集合运算算法。要求：用户在交互输入两个多边形之后，通过选择菜单，生成并显示它的并集、交集或差集。鼓励：本题只完成并运算即可。如果你能够完成交运算或差运算，额外奖励40分参考程序：目录下有可执行的演示程序。在实现上，你应该自己编写程序。三维点集的凸包（50分）目的：多面体的表示方法，熟悉三维平面点集凸包的生成算法。要求：提供菜单来随机地生成三维点集，通过选择菜单，生成并显示它的凸包。并且可以如房子一样，在任意视点下观察。鼓励：同房子一样，如果你能够以虚线的形式显示隐藏线，额外奖励30分参考程序：目录下有可执行的演示程序（随后提供）。在实现上，你应该利用目录下的增量式算法的控制台源程序。B样条曲面的显示（40分）目的：认识B样条曲面及其离散化方法。要求：已知存在于文件中的B样条曲面的控制顶点网格数据（bs_surf_1.txt是一个例子文件），要求读入该文件并将其真实地显示出来，并且可以在任意视点下观察。控制顶点网格数据文件的格式如下：u方向控制顶点mv方向控制顶点个数nP00的坐标值P01的坐标值Pm-1,n-1Pm-1,n-1的坐标值参考程序：目录下有可执行的演示程序。在实现上，你应该你应该自己编写程序。多面体的平移扫描生成（80分）目的：进一步熟悉多面体的表示方法，熟悉扫描法生成多面体的方法。要求：用户在交互输入一个多边形之后，可以选择菜单，输入