计算几何学习笔记, 尽量做到简单易懂.

一些约定#

用非加粗字母代表点 (例如 ).

用加粗字母代表向量 (例如 , ). 特别的, 就是 , 其他字母代表的点亦然.

向量基础#

这边介绍一个自己常用的右手定则判断叉积方向(正负).

用右手的大拇指, 食指, 中指做一个三维坐标系的样子, 形如这样:

其中大拇指与红色正半轴对齐, 食指与绿色正半轴对齐, 中指与蓝色正半轴对齐. 容易发现, 如果有向量 是红色正半轴方向的(也是大拇指所指方向), 向量 是绿色正半轴方向的(也是食指所指方向), 那么 作为三维向量就是蓝色正半轴方向, 也即 .

相似的, 我们要判断 的方向(正负)时, 也可以先让大拇指与红色正半轴对齐, 食指与绿色正半轴对齐, 中指与蓝色正半轴对齐, 然后凑出大拇指与 对齐, 食指与 对齐(大拇指和食指可以在它们张成的平面内任意移动来对齐, 也可以让整个手掌反过来), 此时中指所指的就是 作为三维向量的方向, 据此可以轻易判定 .

基本操作#

判定点在直线的哪边#

如图, 我们要判断点 在直线 的哪边.

我们计算 , 如果 则 在 上方, 如果 则 在 上, 否则 在 下方.

判定直线交点#

我们先进行快速排斥试验, 即判定这两条线段所在矩形是否有交集. 我们称一条线段所在的矩形是一个矩形, 使得这个矩形的对角线是那条线段, 且边平行于坐标轴.

可以发现, 如果不通过快速排斥试验, 那么这两条线段必定没有相交. 反之不一定, 所以需要进行跨立试验. 通过跨立试验可以辨别第二种和第三种情况.

跨立试验就是对于线段 , 判断是否有 在直线 的异侧(两次判定的结果相乘不大于 ), 反之亦然. 如果这两次试验都通过, 我们称 , 通过了跨立试验.

如果, 通过了快速排斥试验和跨立试验, 那么这两条线段必然有交点. 快速排斥试验本质是加速(多花 10% 的时间, 解决 50% 的问题), 但是仅仅通过跨立试验不能判定两条线段有交点(这是因为存在 , 共线但不相交的情况).

判定点是否在多边形内部#

给定多边形 , 判定 是否在该多边形内部.

算法 1#

我们先特判一些特殊情况(点在多边形上的情况), 然后从 引一条射线(不平行于多边形的任意一条边的), 计算这条射线和多边形的边相交的次数, 如果这个次数是奇数, 那么点在多边形内部; 否则点在多边形外部.

算法 2#

我们考虑计算 的有向夹角和. 若为 则在多边形外部, 否则在内部.

直线求交#

首先, 我们特判掉两条线段交点不为一个的情况(方向向量平行)[PS: 学了立体几何之后才发现平面的情况有多简单 quq]