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

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

news 来源：原创 2024/9/20 0:32:48

操作系统：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;
}