在软件设计师的备考中，数据结构与算法部分的几何算法基础是一个重要考点。
一、点与点、点与线、线与线的几何关系判断
1. 点与点
- 知识点：主要判断两点之间的距离。可以通过坐标公式计算，在平面直角坐标系中，若有点(A(x_1,y_1))和点(B(x_2,y_2))，两点间距离(d = \sqrt{(x_2 - x_1)^2+(y_2 - y_1)^2})。
- 学习方法：要牢记公式，多做一些简单的计算练习，比如给定几个点的坐标，快速计算它们之间的距离。同时可以结合图形理解，在纸上画出点，直观感受距离的计算。
2. 点与线
- 知识点：判断点是否在直线上。对于直线(Ax + By+C = 0)，点(P(x_0,y_0))，若(Ax_0+By_0 + C=0)，则点在直线上；若(Ax_0+By_0 + C\lt0)，点在直线一侧；若(Ax_0+By_0 + C\gt0)，点在直线另一侧。
- 学习方法：理解直线方程的表达式，通过大量实例进行练习。可以先从简单的直线(y = kx + b)入手，将点的坐标代入方程判断，再过渡到一般式。
3. 线与线
- 知识点：判断两条直线是否平行、垂直或者相交。对于直线(y_1=k_1x + b_1)和(y_2=k_2x + b_2)，若(k_1 = k_2)且(b_1\neq b_2)，则两直线平行；若(k_1\times k_2=- 1)，则两直线垂直；若(k_1\neq k_2)，则两直线相交。
- 学习方法：掌握直线斜率的概念，通过做一些综合性的题目，如给出两条直线的不同表达式，准确判断它们的关系。
二、凸包（Graham扫描法、Andrew算法）
1. Graham扫描法
- 实现步骤：
- 首先找到最下方的点（如果有多个，取最左边的），设为起始点(p_0)。
- 将其余点按照与(p_0)的极角排序。
- 创建一个栈，先将(p_0)、(p_1)、(p_2)入栈。
- 对于后续的每个点(p_i)，判断栈顶的两个点和(p_i)构成的向量是否左转，如果不是，则弹出栈顶元素，直到满足左转条件，然后将(p_i)入栈。
- 学习方法：理解极角的概念，通过画图辅助理解每一步的操作。多分析一些简单的凸包例子，比如三角形的凸包等。
2. Andrew算法
- 实现步骤：
- 先将所有点按照(x)坐标从小到大排序，如果(x)坐标相同，则按照(y)坐标从小到大排序。
- 从左到右构建下凸包，从排序后的第一个点开始，依次判断后面的点与栈顶两个点构成的向量是否左转，若不是则弹出栈顶元素，最后得到下凸包。
- 从右到左构建上凸包，方法类似，最后合并上下凸包得到完整的凸包。
- 学习方法：注重排序的依据，通过实际操作一些点的集合来掌握算法流程。
三、多边形面积计算
1. 实现步骤
- 对于简单多边形（不自交），可以使用叉乘法。将多边形的顶点按顺序连接，设顶点为(P_0,P_1,\cdots,P_n)，那么多边形面积(S=\frac{1}{2}\sum_{i = 0}^{n - 1}(P_i\times P_{i+1}))（这里(P_i\times P_{i+1})是向量叉乘）。
- 学习方法：掌握向量叉乘的计算方法，通过计算一些规则多边形（如矩形、三角形）的面积来加深理解。
四、计算几何库（CGAL）使用简介
- CGAL提供了很多高效的计算几何算法实现。首先要安装CGAL库，然后在代码中包含相应的头文件。例如，要使用凸包算法，可以包含特定的凸包算法头文件。在使用时，按照库的文档说明创建相应的数据结构并调用函数。不过在备考中，重点是理解算法原理，对于库的使用只需有一定的了解即可。
总之，在强化阶段备考几何算法基础时，要扎实掌握各个知识点的原理和计算方法，多做练习题，并且对相关算法有整体的把握。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
