图片:
针对该算法，写了一个随机生成平面点的算法和复现了该算法，代码如下：
#include <iostream> #include <vector> #include <time.h> #include <string> #include <fstream> #include <algorithm> using namespace std; struct Point { double x; double y; Point(double a = 0, double b = 0) :x(a), y(b) {}; }; void getrandompoint(int num, vector<Point>& P, string outfile) { srand(time(0)); for (int i = 0;i < num; i++) { double x = rand() / double(RAND_MAX); double y = rand() / double(RAND_MAX); P.push_back(Point(x, y)); } //保存随机点 ofstream file(outfile); int count = 1; for (auto x : P) { file << count << " "; file << x.x << " "; file << x.y << " "; file << 0 << " "; file << 0 << " " << 0 << " " << 1 << " ";//法向量 for (int i = 0;i < 10;i++) file << 0 << " "; file << endl; count++; } file.close(); } bool comp(const Point& P1, const Point& P2) { return P1.x < P2.x; } bool jiancha(const vector<Point>& P) { int size = P.size(); Point first = P[size - 3]; Point second = P[size - 2]; Point third = P[size - 1]; double v1x = second.x - first.x; double v1y = second.y - first.y; double v2x = third.x - second.x; double v2y = third.y - second.y; return v1x * v2y - v2x * v1y < 0; } void convex1(vector<Point>& P, string outfile) { vector<Point>upper; //根据x坐标对所有点排序 sort(P.begin(), P.end(), comp); upper.push_back(P[0]); upper.push_back(P[1]); int size = P.size(); for (int i = 2;i < size;i++) { upper.push_back(P[i]); while (upper.size() >= 3 && !jiancha(upper)) { Point temp = upper.back(); upper.pop_back();upper.pop_back(); upper.push_back(temp); } } vector<Point>lower; lower.push_back(P[size - 1]); lower.push_back(P[size - 2]); for (int i = size - 3;i >= 0;i--) { lower.push_back(P[i]); while (lower.size() >= 3 && !jiancha(lower)) { Point temp = lower.back(); lower.pop_back();lower.pop_back(); lower.push_back(temp); } } ofstream file(outfile); int count = 1; for (auto x : upper) { file << count << " "; file << x.x << " "; file << x.y << " "; file << 0 << " "; file << 0 << " " << 0 << " " << 1 << " ";//法向量 for (int i = 0;i < 10;i++) file << 0 << " "; file << endl; count++; } size = lower.size()-1; for (int i = 1;i < size;i++) { file << count << " "; file << lower[i].x << " "; file << lower[i].y << " "; file << 0 << " "; file << 0 << " " << 0 << " " << 1 << " ";//法向量 for (int i = 0;i < 10;i++) file << 0 << " "; file << endl; count++; } file.close(); } int main() { vector<Point>P; getrandompoint(100, P, "randomPoint.txt"); convex1(P, "convex1.txt"); return 0; }因为本人之前写过了一个opengl点云显示的软件，所以将所有结果都保存在txt中供调用，txt中数据的格式有些奇怪，这是本人写的opengl软件读取数据的基本格式，不必在意。
下面给出画出的结果图：
