017-几何-三维凸包

计算三维点集凸包的所有面，要求无四点共面，所有面朝外，复杂度 O(n^2)。

Description: Computes all faces of the 3-dimension hull of a point set. No four points must be coplanar, or else random results will be returned. All faces will point outwards. Time: O(n^2) Status: tested on SPOJ CH3D

• 算法与实现（依据代码）

  • 类型：P3 = Point3D，F = {P3 q; int a,b,c;} 表示一个面（q 为法向量，a/b/c 为顶点索引）。
  • 边对结构 PR：每条边最多被两个面使用（ins/rem/cnt）。
  • 初始化：选取前4个点构建初始4个三角形面（通过枚举 i<j<k 并以第四个点调整法向）。
  • 增量构建：对每个后续点 i（从第5个起）：
    1. 删除所有”法向量指向新点”的面（即 f.q.dot(A[i]) > f.q.dot(A[f.a]) 的面），并从边对中移除对应边；
    2. 对剩余面的边界（E(a,b).cnt() != 2 的边），以新点 i 与该边构成新三角形面，并添加到 FS。
  • 后处理：调整每个面的 b/c 顺序，使法向量 q 与实际几何方向一致（通过叉积与点积检查）。

• 关键约束

  • 输入点集大小 ≥ 4，且任意四点不共面；否则结果未定义。

• 输出

  • 返回 vector，每个 F 代表一个朝外的三角形面。

关联节点

• 040-几何-三维点
• 025-几何-凸包
• 046-几何-多面体体积