用蛮力法c++写凸包问题并且动态可视化

以下是用蛮力法求解凸包的C++代码，并且使用了OpenCV库进行了动态可视化。

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

using namespace cv;
using namespace std;

struct Point {
    double x, y;
};

bool cmp(Point a, Point b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

double cross(const Point &o, const Point &a, const Point &b) {
    return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}

vector<Point> convexHull(vector<Point> &points) {
    int n = points.size();
    sort(points.begin(), points.end(), cmp);

    vector<Point> hull;
    for (int i = 0; i < n; i++) {
        while (hull.size() > 1 && cross(hull[hull.size() - 2], hull[hull.size() - 1], points[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(points[i]);
    }

    int t = hull.size();
    for (int i = n - 2; i >= 0; i--) {
        while (hull.size() > t && cross(hull[hull.size() - 2], hull[hull.size() - 1], points[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(points[i]);
    }

    hull.pop_back();
    return hull;
}

int main() {
    vector<Point> points = {{2, 2}, {3, 3}, {2, 4}, {1, 3}, {3, 1}, {4, 2}};

    vector<Point> hull = convexHull(points);

    Mat img(480, 640, CV_8UC3, Scalar(255, 255, 255));
    for (int i = 0; i < points.size(); i++) {
        circle(img, Point(points[i].x * 50 + 80, points[i].y * 50 + 80), 3, Scalar(0, 0, 255), -1);
    }

    for (int i = 0; i < hull.size(); i++) {
        line(img, Point(hull[i].x * 50 + 80, hull[i].y * 50 + 80), Point(hull[(i + 1) % hull.size()].x * 50 + 80, hull[(i + 1) % hull.size()].y * 50 + 80), Scalar(0, 255, 0), 2);
    }

    namedWindow("ConvexHull", WINDOW_NORMAL);
    resizeWindow("ConvexHull", 640, 480);
    imshow("ConvexHull", img);
    waitKey(0);

    return 0;
}

运行上述代码，即可看到动态可视化的凸包结果。其中，红色点为原始点集，绿色线段为凸包的边界。