使用Bowyer-Watson算法完成将20个以上随机生成的点完成三角剖分的实现。用opencv库画出用Bowyer-Watson算法处理后的三角剖分的点和线的蓝色图像。我用的是c++20,给类写出必要的重载运算符的代码,添加完整的头文件,写出正确完整详细的c++代码,我不要框架,我要一个可以直接完美执行的代码
时间: 2023-11-28 15:48:33 浏览: 139
以下是使用Bowyer-Watson算法进行三角剖分的C++代码,其中包括对Point和Triangle的类定义和重载运算符的实现,以及使用OpenCV库绘制三角剖分的图像:
```c++
#include <iostream>
#include <vector>
#include <cmath>
#include <opencv2/opencv.hpp>
using namespace std;
using namespace cv;
class Point {
public:
double x, y;
Point() : x(0), y(0) {}
Point(double x, double y) : x(x), y(y) {}
Point operator+(const Point& p) const {
return Point(x + p.x, y + p.y);
}
Point operator-(const Point& p) const {
return Point(x - p.x, y - p.y);
}
bool operator==(const Point& p) const {
return (x == p.x && y == p.y);
}
bool operator!=(const Point& p) const {
return !(*this == p);
}
};
class Triangle {
public:
Point p1, p2, p3;
Triangle() {}
Triangle(const Point& p1, const Point& p2, const Point& p3)
: p1(p1), p2(p2), p3(p3) {}
bool contains(const Point& p) const {
double s1 = (p1.y - p2.y) * (p.x - p2.x) - (p1.x - p2.x) * (p.y - p2.y);
double s2 = (p2.y - p3.y) * (p.x - p3.x) - (p2.x - p3.x) * (p.y - p3.y);
double s3 = (p3.y - p1.y) * (p.x - p1.x) - (p3.x - p1.x) * (p.y - p1.y);
return ((s1 >= 0 && s2 >= 0 && s3 >= 0) || (s1 <= 0 && s2 <= 0 && s3 <= 0));
}
};
vector<Point> generate_points(int n, int width, int height) {
vector<Point> points;
for (int i = 0; i < n; ++i) {
double x = (double)rand() / RAND_MAX * width;
double y = (double)rand() / RAND_MAX * height;
points.push_back(Point(x, y));
}
return points;
}
vector<Triangle> bowyer_watson(const vector<Point>& points, double width, double height) {
vector<Triangle> triangles;
Point p1(-width, -height);
Point p2(-width, height);
Point p3(width, -height);
Point p4(width, height);
triangles.push_back(Triangle(p1, p2, p3));
triangles.push_back(Triangle(p3, p2, p4));
for (int i = 0; i < points.size(); ++i) {
Point p = points[i];
vector<Triangle> bad_triangles;
for (int j = 0; j < triangles.size(); ++j) {
Triangle t = triangles[j];
if (t.contains(p)) {
bad_triangles.push_back(t);
}
}
vector<Edge> polygon;
for (int j = 0; j < bad_triangles.size(); ++j) {
Triangle t = bad_triangles[j];
polygon.push_back(Edge(t.p1, t.p2));
polygon.push_back(Edge(t.p2, t.p3));
polygon.push_back(Edge(t.p3, t.p1));
triangles.erase(remove(triangles.begin(), triangles.end(), t), triangles.end());
}
vector<Edge> boundary;
for (int j = 0; j < polygon.size(); ++j) {
Edge e = polygon[j];
if (count(polygon.begin(), polygon.end(), e) == 1) {
boundary.push_back(e);
}
}
for (int j = 0; j < boundary.size(); ++j) {
for (int k = j + 1; k < boundary.size(); ++k) {
if (boundary[j].shares_vertex_with(boundary[k])) {
triangles.push_back(Triangle(boundary[j].p1, boundary[j].p2, boundary[k].p2));
triangles.push_back(Triangle(boundary[j].p1, boundary[k].p2, boundary[k].p1));
}
}
}
}
vector<Triangle> valid_triangles;
for (int i = 0; i < triangles.size(); ++i) {
Triangle t = triangles[i];
if (!t.contains(p1) && !t.contains(p2) && !t.contains(p3) && !t.contains(p4)) {
valid_triangles.push_back(t);
}
}
return valid_triangles;
}
class Edge {
public:
Point p1, p2;
Edge() {}
Edge(const Point& p1, const Point& p2) : p1(p1), p2(p2) {}
bool operator==(const Edge& e) const {
return ((p1 == e.p1 && p2 == e.p2) || (p1 == e.p2 && p2 == e.p1));
}
bool shares_vertex_with(const Edge& e) const {
return (p1 == e.p1 || p1 == e.p2 || p2 == e.p1 || p2 == e.p2);
}
};
void draw_triangles(const vector<Point>& points, const vector<Triangle>& triangles, int width, int height) {
Mat img(height, width, CV_8UC3, Scalar(255, 255, 255));
for (int i = 0; i < points.size(); ++i) {
circle(img, Point(points[i].x, points[i].y), 3, Scalar(0, 0, 255), FILLED);
}
for (int i = 0; i < triangles.size(); ++i) {
line(img, Point(triangles[i].p1.x, triangles[i].p1.y), Point(triangles[i].p2.x, triangles[i].p2.y), Scalar(255, 0, 0));
line(img, Point(triangles[i].p2.x, triangles[i].p2.y), Point(triangles[i].p3.x, triangles[i].p3.y), Scalar(255, 0, 0));
line(img, Point(triangles[i].p3.x, triangles[i].p3.y), Point(triangles[i].p1.x, triangles[i].p1.y), Scalar(255, 0, 0));
}
namedWindow("Triangulation", WINDOW_NORMAL);
imshow("Triangulation", img);
waitKey(0);
}
int main() {
int n = 50;
int width = 800;
int height = 600;
vector<Point> points = generate_points(n, width, height);
vector<Triangle> triangles = bowyer_watson(points, width, height);
draw_triangles(points, triangles, width, height);
return 0;
}
```
阅读全文