OpenCV convexHull 凸包求解实战：OpenCV 5.0 opencv_geometry 模块中 Sklansky 算法与轮廓应用

本指南以 OpenCV 官方教程 convex_hull.markdown 为核心骨架，完整讲解如何使用 cv::convexHull 从 2D 点集或轮廓中求出最小凸多边形，并配合仓库内样例程序、头文件声明、底层实现与测试代码进行源码级印证。读完你将掌握 Sklansky 凸包算法的时间复杂度原理、OpenCV 5.0 将计算几何函数从 imgproc 迁移至独立 geometry 模块后的头文件与 CMake 链接方式、clockwise 与 returnPoints 两个关键参数的正确用法（尤其是为 cv::convexityDefects 输出索引的必要性），并能独立编译运行 C++ / Java / Python 三种语言的交互式凸包演示程序。

一、凸包的概念与算法原理

1.1 什么是凸包

凸包（Convex Hull）是包含给定点集的最小凸多边形。文档给出的直观类比是：想象一根拉紧的橡皮筋把所有点包围起来，一旦松手，橡皮筋会收缩并贴合在最外圈的点上，所围出的形状就是这组点的凸包。

• 凸包的所有顶点都来自原始点集（凸包点是原始点集的子集）；
• 凸包是"最小"的凸集：任何包含全部点的凸集都包含凸包；
• 在图像分析中，对单个轮廓求凸包可以得到该形状的"最小包围凸轮廓"，用于近似形状、去除非凸凹陷（defect）对识别的影响。

1.2 Sklansky 算法与时间复杂度

OpenCV 官方文档明确说明，cv::convexHull 使用 Sklansky 算法（其文献引用见 2d.hpp 中 @cite Sklansky82）计算二维凸包：

• 若输入点未排序，时间复杂度为 O(N log N)；
• 若输入点已排序（例如来自 cv::findContours 的按顺序组织的轮廓点），复杂度可降至 O(N)。

以仓库中实际实现为例，convhull.cpp 将算法拆分为 Sklansky_ 内核（见 convhull.cpp），通过一次扫描把点列分成上下左右四个单调链（tl_stack、tr_stack、bl_stack、br_stack，见 convhull.cpp）分别求解再合并，这正是它对有序点列能达到线性复杂度的原因。

需要注意：这里输入点"已经排序"指数据在内存中的存储次序满足按 X（或 Y）单调推进的形态，最典型的来源就是轮廓提取结果 findContours 输出的有序边界点。如果传入的是任意散乱点集，convexHull 内部仍需要先做排序预处理，因而整体回到 O(N log N)。

二、OpenCV 5.0 模块重组：convexHull 移入 geometry 模块

这是本教程一个重要的版本背景。文档特别指出：

在 OpenCV 5.0 中，计算几何算法被重新组织：convexHull 等函数从 imgproc 模块迁移到新的 geometry 模块。C++ 代码现在必须包含 <opencv2/geometry.hpp>。

这一点在当前仓库的源码结构中得到证实：

• 头文件入口为 modules/geometry/include/opencv2/geometry.hpp，其下 2d.hpp 声明了 2D 计算几何算法族；
• convexHull 的公开声明位于 2d.hpp：CV_EXPORTS_W void convexHull( InputArray points, OutputArray hull, bool clockwise = false, bool returnPoints = true );；
• 同一头文件还聚集了 convexityDefects（2d.hpp）、minEnclosingTriangle、minEnclosingConvexPolygon、minAreaRect、fitEllipse、moments、HuMoments、matchShapes 等计算几何函数，并提供了 geometry.cpp 示例 之外的综合演示（头文件注释 @example samples/cpp/geometry.cpp）。

因此编写 C++ 代码时：

#include <opencv2/geometry.hpp>   // convexHull、convexityDefects、minEnclosingCircle 等
#include <opencv2/imgproc.hpp>    // Canny、findContours、drawContours（仍在 imgproc）

从源码结构看，Java 绑定侧为了兼容性仍把调用放在 org.opencv.imgproc.Imgproc 类中（见下文 Java 样例 Imgproc.convexHull(...)），Python 侧则统一通过 cv.convexHull(...) 调用，两种语言绑定都对用户屏蔽了模块差异。

三、工程配置：CMake 链接 opencv_geometry

由于 5.0 将这些函数迁入了独立模块，需要在 CMakeLists.txt 中额外链接 opencv_geometry。原文档给出了完整配置示例，如下（可原样使用）：

cmake_minimum_required(VERSION 3.1)
project(ConvexHullDemo)

find_package(OpenCV REQUIRED)

add_executable(ConvexHullDemo convex_hull_demo.cpp)
target_link_libraries(ConvexHullDemo ${OpenCV_LIBS} opencv_geometry)

关键点：

• find_package(OpenCV REQUIRED) 会导入 OpenCV_INCLUDE_DIRS、OpenCV_LIBS 等变量；教程示例在这里显式补充 opencv_geometry，以表达对该新模块的依赖（你从 OpenCV_LIBS 展开出的库列表中通常已包含它，但显式写出可读性更强、也避免旧版缓存干扰）；
• target_link_libraries 中的库顺序与名称以本机安装的 OpenCV 5.x 构建为准，构建时请使用与当前仓库一致的 5.x 分支。

四、完整可运行示例代码

教程代码同时提供了 C++、Java、Python 三个版本，仓库中的实际文件为：

• C++：samples/cpp/tutorial_code/ShapeDescriptors/hull_demo.cpp
• Python：samples/python/tutorial_code/ShapeDescriptors/hull/hull_demo.py
• Java：samples/java/tutorial_code/ShapeDescriptors/hull/HullDemo.java

默认输入图像为 samples/data/stuff.jpg（可通过 samples::findFile / cv.samples.findFile 自动定位样例数据目录）。三个版本的算法流程完全一致，此处以下载并运行 C++ 版本为例说明：

# 参数格式：<程序> [输入图像]，默认 stuff.jpg
./ConvexHullDemo stuff.jpg

4.1 主流程（C++）

int main( int argc, char** argv )
{
    // 命令行解析，默认读入 stuff.jpg
    CommandLineParser parser( argc, argv, "{@input | stuff.jpg | input image}" );
    Mat src = imread( samples::findFile( parser.get<String>( "@input" ) ) );
    if( src.empty() ) { /* 报错并退出 */ }

    // 转灰度 + 3x3 均值模糊，减少边缘检测噪声
    cvtColor( src, src_gray, COLOR_BGR2GRAY );
    blur( src_gray, src_gray, Size(3,3) );

    const char* source_window = "Source";
    namedWindow( source_window );
    imshow( source_window, src );

    // 创建 Canny 阈值 trackbar（0~255，初值 100）
    const int max_thresh = 255;
    createTrackbar( "Canny thresh:", source_window, &thresh, max_thresh, thresh_callback );
    thresh_callback( 0, 0 );   // 初始化画布

    waitKey();
    return 0;
}

4.2 核心回调：边缘 → 轮廓 → 凸包 → 绘制

拖动滑块时每次都会重新执行完整流水线（对应源码 hull_demo.cpp）：

void thresh_callback(int, void* )
{
    // 1) Canny 边缘检测：低阈值 thresh，高阈值 thresh*2
    Mat canny_output;
    Canny( src_gray, canny_output, thresh, thresh*2 );

    // 2) 提取轮廓：RETR_TREE 建层级树，CHAIN_APPROX_SIMPLE 压缩水平/垂直/对角线段
    vector<vector<Point> > contours;
    findContours( canny_output, contours, RETR_TREE, CHAIN_APPROX_SIMPLE );

    // 3) 对每个轮廓求凸包（输出默认是凸包点坐标）
    vector<vector<Point> > hull( contours.size() );
    for( size_t i = 0; i < contours.size(); i++ )
        convexHull( contours[i], hull[i] );

    // 4) 在黑色画布上绘制：轮廓与其凸包共用一个随机颜色
    Mat drawing = Mat::zeros( canny_output.size(), CV_8UC3 );
    for( size_t i = 0; i < contours.size(); i++ )
    {
        Scalar color = Scalar( rng.uniform(0, 256), rng.uniform(0,256), rng.uniform(0,256) );
        drawContours( drawing, contours, (int)i, color );   // 原始轮廓
        drawContours( drawing, hull,     (int)i, color );   // 对应凸包
    }
    imshow( "Hull demo", drawing );
}

4.3 Python 等价实现

Python 版本逻辑完全一致，代码位于 hull_demo.py，核心片段如下：

def thresh_callback(val):
    canny_output = cv.Canny(src_gray, val, val * 2)
    contours, _ = cv.findContours(canny_output, cv.RETR_TREE, cv.CHAIN_APPROX_SIMPLE)

    hull_list = []
    for i in range(len(contours)):
        hull = cv.convexHull(contours[i])
        hull_list.append(hull)

    drawing = np.zeros((canny_output.shape[0], canny_output.shape[1], 3), dtype=np.uint8)
    for i in range(len(contours)):
        color = (rng.randint(0, 256), rng.randint(0, 256), rng.randint(0, 256))
        cv.drawContours(drawing, contours, i, color)
        cv.drawContours(drawing, hull_list, i, color)
    cv.imshow('Contours', drawing)

# 初始化：读图 -> 灰度 -> 3x3 模糊
src_gray = cv.cvtColor(src, cv.COLOR_BGR2GRAY)
src_gray = cv.blur(src_gray, (3, 3))

# trackbar：初值 thresh = 100，范围 0~255
cv.createTrackbar('Canny thresh:', source_window, thresh, max_thresh, thresh_callback)
thresh_callback(thresh)
cv.waitKey()

4.4 Java 版本要点

Java 版本 HullDemo.java 使用 Swing + HighGui 展示，滑块事件中同样执行 灰度/模糊 → Canny → findContours → 凸包 → 绘制 的完整链路，其核心调用为（见 HullDemo.java）：

MatOfInt hull = new MatOfInt();
Imgproc.convexHull(contour, hull);

注意这里传给 MatOfInt，等价于 C++ 的索引输出模式（见下一节）。Java 样例的默认输入路径为 ../data/stuff.jpg，运行时请确保相对路径能定位到样例图像。

五、深入 convexHull 的四个参数与两种输出模式

convexHull 函数签名（2d.hpp）为：

void convexHull( InputArray points, OutputArray hull,
                 bool clockwise = false, bool returnPoints = true );

参数	类型/默认值	含义与说明
points	InputArray	输入 2D 点集，std::vector<Point> 或 Mat 均可；支持 CV_32S（Point/Point2i）与 CV_32F（Point2f）两种深度（实现中由 convhull.cpp 分别以 int/int64 与 float/double 的内部精度分派）
hull	OutputArray	输出的凸包。有两种形态：整数索引向量 或 点坐标向量（详见下文）
clockwise	false	方向标志。为 true 时输出按顺时针排列；默认逆时针。坐标约定为 X 轴向右、Y 轴向上
returnPoints	true	操作标志。为 true 时输出凸包点坐标；为 false 时输出这些点在原数组中的 0 起始下标。当输出是 std::vector 时该标志被忽略，类型自动决定行为：std::vector<int> 等价于 returnPoints=false，std::vector<Point> 等价于 returnPoints=true

其他值得注意的语义：

• 输出索引的用途：文档强调，当 returnPoints=false（得到的是原点下标）时才能作为 cv::convexityDefects 的输入——该函数需要"构成 hull 的轮廓点下标"来计算凹陷缺陷（见 2d.hpp）。convexityDefects 输出的每个 Vec4i 为 (start_index, end_index, farthest_pt_index, fixpt_depth)，其中 fixpt_depth 是带 8 位小数的定点深度，换算浮点值需除以 256.0；
• 不支持原地处理：points 与 hull 必须是不同数组，文档注释明确 inplace processing isn't supported（2d.hpp）；
• 测试佐证：仓库测试 test_convhull.cpp 中即使用 cv::convexHull(contour, hull, clockwise, false) 的索引输出模式去驱动 convexityDefects，其中 ordering_4539、overflow 等用例还专门校验了凸包顶点/下标序列的一致性。

六、同模块关联算法一览

掌握 convexHull 之后，通常还会在 geometry 模块中使用以下互补函数，它们同声明于 2d.hpp，可作为后续深入方向：

• convexityDefects(contour, convexhull, convexityDefects)：计算轮廓的凸性缺陷（如手掌轮廓中指尖之间的凹陷），要求传入 hull 的下标结果；
• isContourConvex(contour)：判断轮廓是否为凸（test 用例 Imgproc_ConvexityDefects_ordering_4539 等中可见其与 convexHull 联合使用）；
• minEnclosingTriangle / minEnclosingConvexPolygon / minEnclosingCircle / minAreaRect / fitEllipse：各类最小包围几何体。其中 minEnclosingTriangle、minEnclosingConvexPolygon 内部需先以 convexHull 做预处理，因此整体复杂度为 O(N log N)（见 2d.hpp 的函数说明），与本节主题形成天然的进阶链路。

七、运行结果与调参建议

编译并运行后会出现两个窗口：左侧 "Source" 显示原图并带有 "Canny thresh:" 滑块（范围 0~255，默认 100）；右侧 "Hull demo" 动态显示当前阈值下的处理结果。拖动滑块时，thresh_callback 会实时重新执行 Canny → 轮廓 → 凸包 → 绘制，每个轮廓与其凸包使用同一随机颜色以便对比（随机数种子固定为 12345，见 hull_demo.cpp 与 Python 侧 rng.seed(12345)，保证每次运行配色可复现）。

实操建议：

• 阈值选择：Canny 使用 thresh 与 thresh*2 的双阈值策略。阈值偏低会得到大量琐碎轮廓（凸包也随之碎片化），阈值偏高则会丢失真实边界——通过滑块在 100 附近反复试探是理解该参数最直接的方式；
• 轮廓检索模式：示例使用 RETR_TREE 保留嵌套层级，凸包会对最外层与内层轮廓各自计算。若只想处理最外层形状，可换用 RETR_EXTERNAL；
• 凸包在真实应用中的价值：对轮廓求凸包可以"填充"物体轮廓上的凹陷，常用于手势识别中把张开的手指轮廓归一化为手掌外轮廓，再配合 convexityDefects 计算指间凹陷数量与深度来判别手势——这正是 returnPoints=false 索引输出模式的典型落地场景；
• 调试与验证：仓库测试目录 modules/geometry/test/test_convhull.cpp 覆盖了凸包方向、索引单调性、溢出与大量回归场景（如 Imgproc_minAreaRect、ConvexityDefects_regression_5908），若你自行修改或扩展相关代码，可参照这些用例补充边界测试（共线点、单点、退化轮廓等）。

八、小结

围绕 cv::convexHull 这一函数，本文完成了从理论到实践的完整闭环：以橡皮筋模型理解凸包的定义，从 convhull.cpp 的 Sklansky_ 内核确认有序/无序输入的 O(N) / O(N log N) 复杂度差异；针对 OpenCV 5.0 模块重组，明确了 <opencv2/geometry.hpp> 头文件与 CMake 中链接 opencv_geometry 的必要性；通过 C++ / Python / Java 三份样例程序掌握"灰度 → Canny → findContours → convexHull → drawContours"的标准流水线；最后厘清了 clockwise 与 returnPoints 的语义，尤其是输出下标模式在 convexityDefects 等下游算法中的不可替代作用。无论你是在做形状分析、手势识别还是最小包围几何计算，这份文档连同仓库中的源码与测试，都是直接可用的参考资料。