哈工大算法实验：凸包生成与点线关系判定

哈工大算法实验主要关注于两个关键部分：点线关系的判断和多边形内角的计算，以及凸包的生成算法。实验报告旨在通过具体的实例和步骤，让学生深入理解这两个核心概念。 在点与线的关系部分，首先定义了三点P1, P2, P3的面积量公式，用于判断三点的顺序。当三点按逆时针排列时，该面积量S为正，顺时针则为负，而零表示三点共线。通过计算点C与矢量AB的叉积，可以确定点C在直线AB的相对位置，这对于后续的图形处理和路径判断至关重要。 多边形内角的计算是通过以下几个步骤进行的： 1. 输入离散点序列，选择x坐标最小的点p0作为多边形的一个角点，确保多边形为凸形。 2. 定义p0、p1和p2（如果必要，考虑边界条件），并根据它们相对于向量p1p0的位置判断多边形的走向，逆时针或顺时针。 3. 计算相邻点之间的角，利用向量夹角公式，同时注意多边形的凹凸性对角度判断的影响。 4. 在确定了多边形的走向后，根据三点构成的凸角特征确定角度。 凸包生成算法则是整个实验的核心内容。它涉及到求解一组点的最小凸多边形，即在保持所有点被包含的前提下，形成一个多边形的边界尽可能简单。Graham算法被用来解决这个问题，其基本思想是： 1. 输入点集S，找到y坐标最小且X坐标最大的点P0作为基点。 2. 对剩余点按照逆时针顺序排序，确保新添加的有向边使得所有点位于其左侧。 3. 按照这个顺序逐步构建凸包，直到所有点都被包含。 在这个实验中，学生需要实现点、向量、多边形等数据结构，并编写相关的算法代码，包括点类、数学计算类和多边形类的定义，以及Graham算法的具体步骤。实验报告将展示这些实现过程，同时分析算法的效率和复杂度，以及可能遇到的问题及其解决方案。 通过这个实验，学生不仅可以掌握算法设计和编程技巧，还能增强对几何空间的理解，培养抽象思维和问题解决能力，对于提升计算机图形学和算法基础具有重要意义。