如何运用快速凸包算法高效处理散点云数据？

散点云处理笔记（三）：快速凸包算法（Quick Hull Algorithm） ​ 凸包问题是计算几何中的一个经典问题，目标是找到包含给定点集的最小凸多边形(二维情形)或凸多面体(三维情形)。它解决的问题在于找到一个凸多边形或凸多边形，这个多边形包含了给定的 n 个点，使得这个多边形是包含这些点的最小凸集合。本笔记首先给出三维散点凸包算法的数学推导，可以从“凸包”这个基本概念出发，一步步深入到算法背后的数学原理，最后给出快速凸包算法的。 1. 最小凸包的数学定义 ​ 最小凸包问题（Convex Hull Problem）的数学表达可以从集合论、凸分析和计算几何三个角度进行形式化定义。核心思想是：在包含给定点集的所有凸集中，寻找体积（或表面积、维度）最小的那个。下面从凸组合、交集、对偶优化表达的几个角度给出最小凸包问题的定义。 Definition 1.1 基于凸组合的定义（构造性表达） 设点集\(\mathbf{P}=\{\mathbf{p}_1,\mathbf{p}_2,\cdots,\mathbf{p}_n\}\subset\mathbb{R}^d\)，其中凸包\(\mathbf{conv}(\mathbf{P})\) 是\(\mathbf{P}\) 中所有点的凸组合构成的集合： \[\mathbf{conv}(\mathbf{P})=\left\{\sum_{i=1}^{n}\lambda_i\mathbf{p}_i\bigg|\lambda_i\geq0,\sum_{i=1}^n\lambda_i=1\right\} \tag{1} \] 这个定义直接给出了凸包作为点集的构造方式，但不易直接用于算法设计。 Definition 1.2 基于交集的定义（几何表达） 凸包也可以表示为所有包含 \(\mathbf{P}\)的凸集的交集： \[\mathbf{conv}(\mathbf{P})=\bigcap\{\mathbf{C}\subseteq\mathbb{R}^d\big|\mathbf{C}\text{是凸包且}\mathbf{P}\subseteq{\mathbf{C}}\} \tag{2} \] 这是“最小凸集”的精确数学刻画：它唯一且必然存在。 Definition 1.3 基于支撑函数的对偶表达（优化视角） 在凸分析中，凸集可以用其支撑函数 \(h_c(\mathbf{u})=\sup_{\mathbf{x}\in{\mathbf{c}}}\mathbf{u}^{T}\mathbf{x}\) 描述。凸包问题等于求一个凸包多面体\(H\)，使得其支撑函数等于点集支撑函数的上确界： \[h_{H}(\mathbf{u})=\max_{\mathbf{p}\in{P}}\mathbf{u}^T\mathbf{p}，\forall{\mathbf{u}\in{\mathbb{R}^d}} \tag{3} \] 此时\(H=\mathbf{conv}(\mathbf{P})\)。这个表达与版空间表示紧密相关： 凸包是所有满足\(\mathbf{u}^T\mathbf{x}\leq{\max_{\mathbf{p}\in{P}}\mathbf{u}^T\mathbf{p}}\)的半空间的交集。 Definition 1.4 凸包问题离散形式（计算几何常用） 在实际算法中，我们通常要求输出凸包的顶点集（极点）及其面/边的邻接关系。因此，凸包问题可表述为： 给定有限点集\(P\subset\mathbb{\mathbb{R}^d}\)，找出最小的子集\(V\subseteq{P}\)，使得\(\mathbf{conv}(V)=\mathbf{conv}(P)\)，并给出\(\mathbf{conv}(V)\)的\(\mathbf{facet}(d-1\text{维度})\) 的几何与拓朴信息。 其中，\(\mathbf{p}\in{P}\)是极点（凸包顶点）当且仅当它不能表示为\(P\{p\}\)中点的凸组合。 Definition 1.5 优化形式的等价表述（用于数学规划） 凸包问题还可以写成线性规划的对偶形式：寻找一个凸多面体 \(Q\)，使得 \(P\subseteq{Q}\)且\(Q\)的某种度量（如体积）最小。但在离散情况下，这通常转化为枚举所有可能的外包多面体并比较。 ​ 最小凸包问题的核心数学表达是 “包含给定点集的最小凸集”，它可以用凸组合、凸集交、支撑函数等方式等价定义。在计算几何中，我们通常寻求输出该凸集的顶点和面结构。