三维计算几何基础和三维凸包的相关概念

三维向量表示为 $(x,y,z)$

三维向量的加法、减法、数乘都和二维相同。

向量 $\vec{a} =(x,y,z)$ 的模长 $\vert \vec{a} \vert=\sqrt{x^2+y^2+z^2}$

点积：

1. 几何意义：$\vec{a} \cdot \vec{b}= \vert \vec{a} \vert \vert \vec{b} \vert \cos(\theta)$（$\theta$ 为 $\vec{a}$ 和 $\vec{b}$ 的夹角）

2. 代数求解：$(x_1,y_1,z_1) \cdot (x_2,y_2,z_2) = (x_1x_2,y_1y_2,z_1z_2)$

具体性质和二维点积类似。

叉积：

1. 几何意义：$\vec{a} \times \vec{b}=\vert \vec{a} \vert \vert \vec{b} \vert \sin{\theta}$（$\theta$ 为 $\vec{a} $ 和 $\vec{b}$ 的夹角）
2. 代数求解：$(x_1,y_1,z_1) \times (x_2,y_2,z_2) = (y_1z_2-y_2z_1, z_1x_2-z_2x_1,x_1y_2-x_2y_1)$

具体性质与二维叉积类似。

如何求一个平面的法向量

任取平面上的两个不共线的向量 $\vec{a},\vec{b}$，法向量就是 $\vec{a} \times \vec{b}$

判断点 $p$ 是否在平面里

求出平面上的法向量 $\vec{n}$，任取平面上一点 $a$，如果 $\vec{ap}$ 在 $\vec{n}$ 上的投影的长度是 $0$，则意味着 $p$ 在平面里。也就是 $\vec{ap} \cdot \vec{n}=0$ 时，点 $p$ 在平面里。如果 $\vec{ap} \cdot \vec{n} > 0$，说明点 $p$ 在平面的上方，否则说明点 $p$ 在平面的下方（平面的方向定义为法线的正方向）。

求点 $p$ 到平面的距离

求出平面上的法向量 $\vec{n}$，任取平面上一点 $a$，此时 $\vec{ap}$ 在 $\vec{n}$ 上的投影的长度就是 $p$ 到平面的距离

多面体欧拉定理

对于任意简单多面体，一定满足：顶点数 $-$ 棱长数 $+$ 面数 $=2$

求三维凸包

这里是用增量的算法来求三维凸包。三维凸包保证表面积最小，二维凸包保证周长最小。

我们存储三维凸包的方法是将三维凸包的所有面分割成若干个三角形，然后按照任意顺序存下来。

对于一个新加入的点 $p$，如果 $p$ 已经在凸包内，那么不需要额外操作，如果 $p$ 在凸包外，那么就需要更新三维凸包，我们将 $p$ 想象成一个光点，散发着光线，找出三维凸包上所有能被 $p$ 照到的面，在加入 $p$ 之后这些面都会变成凸包内部的面，因此这些面都需要被删去，和光线平行的面我们也将他删去。而所有没有被照到的面则需要保留下来。所有照到和没照到的面之间有一条分界线，每一条分界线和 $p$ 都会构成一个新的面，我们将这些新的面加入凸包，这样就得到了一个新的凸包。

按照上述思路将所有点加入凸包，就能得到一个三维凸包。

然后考虑实现细节，对于如何判断一个面能否被照到，显然当 $p$ 在当前平面的上方时，则当前平面会被照到，当 $p$ 在当前平面的下方时，则当前平面不会被照到，这个操作在上面有提到。可以用点积来判断。

对于如何找出分界线，我们可以记录一下每条边对应的面能否被照到，这里用逆时针的顺序存储所有边，那么对于一条边 $(i,j)$ 在它对应的两个面上存储的分别是 $(i,j)$ 和 $(j,i)$，如果 $(i,j)$ 是分界线就意味着它对应的两个中只有一个被照到，有一个没照到，因此我们可以枚举所有边 $(i,j)$，如果 $(i,j)$ 和 $(j,i)$ 有一个被照到，一个没被照到，就说明 $(i,j)$ 是分界线之一。

然后考虑一下该算法的时间复杂度，首先有 $n$ 个点，假设有 $m$ 个面，由于我们存的时候将所有面分割成三角形进行存储，因此每个面会有 $3$ 条边，那么会有 $3m$ 条边，但是这么数的话每条边会被计算两次，那么就会有 $\frac{3m}{2}$ 条边，然后将点数、边数、面数代入多面体欧拉定理，可以得到 $m=2n-4$，因此面的数量是 $O(n)$ 的，我们每次加入一个点会加入 $n$ 次，每次都要枚举所有的面，因此整个的时间复杂度就是 $O(n^2)$ 的。

注意，为了防止出现四点共面的情况，我们这里对每个点做一个随机扰动，将每个点任意的挪动一个极小的幅度，这样可以极大程度的避免出现四点共面的情况。

由于我们这里已经做了随机扰动，因此在用叉积判断某个点是否在平面上时就不能再用近似比较了，做随机扰动就是为了将四点共面的情况变成不共面，如果再用近似比较，就又变回四点共面了。