用于少量点的三维凸包算法

下面是用C++实现的三维凸包算法，该算法适用于少量的点，其时间复杂度为O(n^2)，其中n为点的数量。

代码示例：

先定义一个表示三维点的结构体：

struct point3d { double x, y, z; };

接着定义一个表示三维向量的结构体：

struct vector3d { double x, y, z; };

然后定义求两个向量叉积的函数：

vector3d cross_product(vector3d a, vector3d b) { vector3d res; res.x = a.y * b.z - a.z * b.y; res.y = a.z * b.x - a.x * b.z; res.z = a.x * b.y - a.y * b.x; return res; }

接着定义一个判断点是否在平面上的函数：

bool point_on_plane(point3d p, point3d a, point3d b, point3d c) { vector3d ab = {b.x - a.x, b.y - a.y, b.z - a.z}; vector3d ac = {c.x - a.x, c.y - a.y, c.z - a.z}; vector3d ap = {p.x - a.x, p.y - a.y, p.z - a.z}; vector3d n = cross_product(ab, ac); double d = -n.x * a.x - n.y * a.y - n.z * a.z; double dist = (n.x * p.x + n.y * p.y + n.z * p.z + d) / sqrt(n.x * n.x + n.y * n.y + n.z * n.z); return (dist < 1e-6 && dist > -1e-6); }

然后定义求点到平面的距离的函数：

double point_to_plane_dist(point3d p, point3d a, point3d b, point3d c) { vector3d ab = {b.x - a.x, b.y - a.y, b.z - a.z}; vector3d ac = {c.x - a.x, c.y - a.y, c.z - a.z}; vector3d n = cross_product(ab, ac); double d = -n.x * a.x - n.y * a.y - n.z * a.z; double dist = (n.x * p.x + n.y * p.y + n.z * p.z + d) / sqrt(n.x