凸包

什么是凸包(Convex Hull)隐锭，在一個多變形邊緣或者內(nèi)部任意兩個點(diǎn)的連線都包含在多邊形邊界或者內(nèi)部觉阅。
正式定義：包含點(diǎn)集合S中所有點(diǎn)的最小凸多邊形稱為凸包

Graham掃描算法

首先選擇Y方向最低的點(diǎn)作為起始點(diǎn)p0,從p0開始極坐標(biāo)掃描缔恳，依次添加p1….pn（排序順序是根據(jù)極坐標(biāo)的角度大小猪杭，逆時針方向）
對每個點(diǎn)pi來說樊拓，如果添加pi點(diǎn)到凸包中導(dǎo)致一個左轉(zhuǎn)向（逆時針方法）則添加該點(diǎn)到凸包纠亚， 反之如果導(dǎo)致一個右轉(zhuǎn)向（順時針方向）刪除該點(diǎn)從凸包中

convexHull(
InputArray points,// 輸入候選點(diǎn)，來自findContours
OutputArray hull,// 凸包
bool clockwise,// default true, 順時針方向
bool returnPoints）// true 表示返回點(diǎn)個數(shù)筋夏，如果第二個參數(shù)是vector<Point>則自動忽略

#include "pch.h"
#include <opencv2/opencv.hpp>
#include <iostream>
#include <math.h>

using namespace std;
using namespace cv;
Mat src, src_gray, dst;
int threshold_value = 100;
int threshold_max = 255;
const char* output_win = "convex hull demo";
void Threshold_Callback(int, void*);
RNG rng(12345);

int main(int argc, char** argv) {
    src = imread("D:/girl.jpg");
    //src = imread("D:/cir.png");
    if (!src.data) {
        printf("could not load image...\n");
        return -1;
    }
    const char* input_win = "input image";
    namedWindow(input_win, CV_WINDOW_AUTOSIZE);
    namedWindow(output_win, CV_WINDOW_NORMAL);
    const char* trackbar_label = "Threshold : ";

    cvtColor(src, src_gray, CV_BGR2GRAY);
    blur(src_gray, src_gray, Size(3, 3), Point(-1, -1), BORDER_DEFAULT);
    imshow(input_win, src_gray);

    createTrackbar(trackbar_label, output_win, &threshold_value, threshold_max, Threshold_Callback);
    Threshold_Callback(0, 0);
    waitKey(0);
    return 0;
}

void Threshold_Callback(int, void*) {
    Mat bin_output;
    vector<vector<Point>> contours;
    vector<Vec4i> hierachy;
    
    threshold(src_gray, bin_output, threshold_value, threshold_max, THRESH_BINARY);
    findContours(bin_output, contours, hierachy, RETR_TREE, CHAIN_APPROX_SIMPLE, Point(0, 0));

    vector<vector<Point>> convexs(contours.size());
    for (size_t i = 0; i < contours.size(); i++) {
        convexHull(contours[i], convexs[i], false, true);
    }

    // 繪制
    dst = Mat::zeros(src.size(), CV_8UC3);
    vector<Vec4i> empty(0);
    for (size_t k = 0; k < contours.size(); k++) {
        Scalar color = Scalar(rng.uniform(0, 255), rng.uniform(0, 255), rng.uniform(0, 255));
        drawContours(dst, contours, k, color, 2, 8, hierachy, 0, Point(0, 0));
        drawContours(dst, convexs, k, color, 2, 8, empty, 0, Point(0, 0));
    }
    imshow(output_win, dst);

    return;
}