当前位置：首页 > article >正文

OpenCV结构分析与形状描述符（8）点集凸包计算函数convexHull()的使用

article 2024/9/22 4:22:14

操作系统：ubuntu22.04
OpenCV版本：OpenCV4.9
IDE:Visual Studio Code
编程语言：C++11

算法描述

查找一个点集的凸包。
函数 cv::convexHull 使用斯克拉斯基算法（Sklansky’s algorithm）来查找一个二维点集的凸包，在当前实现中该算法的时间复杂度为 O(N logN)。

函数 cv::convexHull 是 OpenCV 库中的一个功能，用于计算一组二维点的凸包。凸包可以理解为是最小的凸多边形，它能够包含给定的所有点。这个函数利用了Sklansky算法或其他高效算法来完成计算，其时间复杂度在当前实现中为 O(N logN)，其中 N 是输入点的数量。

函数原型


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

参数

参数points Input 2D point set, stored in std::vector or Mat.
参数hull 输出的凸包。它可以是一个整数向量的索引或者是点的向量。在第一种情况下，凸包元素是以0为基础的索引，在原始数组中的凸包点（因为凸包点集是原始点集中的一子集）。在第二种情况下，凸包元素本身就是凸包的点。
参数clockwise 方向标志。如果为真，则输出的凸包是按照顺时针方向排列的。否则，它是按照逆时针方向排列的。假设的坐标系统X轴指向右侧，Y轴向上。
参数returnPoints 操作标志。在矩阵的情况下，当此标志为真时，函数返回凸包的点。否则，它返回凸包点的索引。当输出数组是 std::vector 时，此标志被忽略，输出取决于向量的类型：std::vector 表示 returnPoints=false，std::vector 表示 returnPoints=true。

代码示例

include <iostream>
#include <opencv2/opencv.hpp>
#include <vector>

using namespace std;
using namespace cv;

int main() {
    // 创建一个随机点集
    vector<Point2f> points;
    for (int i = 0; i < 10; ++i) {
        points.push_back(Point2f(rand() % 500, rand() % 500));
    }

    // 计算凸包
    vector<vector<Point2f>> hulls;
    vector<int> hullIndices;
    convexHull(points, hullIndices, false);

    // 将索引转换为实际的点
    for (auto& index : hullIndices) {
        hulls.push_back(vector<Point2f>{points[index]});
    }

    // 创建一个空白图像来显示点和凸包
    Mat img = Mat::zeros(512, 512, CV_8UC3);

    // 绘制原始点
    for (const auto& pt : points) {
        circle(img, pt, 3, Scalar(0, 0, 255), -1); // 红色圆圈表示原始点
    }

    imshow("circle image", img);

    // 绘制凸包
    int numPoints = hulls.size();
    for (int i = 0; i < numPoints; ++i) {
        line(img, hulls[i][0], hulls[(i + 1) % numPoints][0], Scalar(0, 255, 0), 2); // 绿色线条表示凸包
    }

    // 显示结果
    imshow("Convex Hull", img);
    waitKey(0);

    return 0;
}