判断多边形是否自相交 c/c++

判断多边形是否自相交的算法可以通过检测多边形上的线段是否有交点来实现。以下是一个简单的 C++ 实现：

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct Point {
    double x, y;
    Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
};

struct Line {
    Point p1, p2;
    Line(Point _p1 = Point(), Point _p2 = Point()) : p1(_p1), p2(_p2) {}
};

// 判断两条线段是否相交
bool intersect(Line l1, Line l2) {
    double x1 = l1.p1.x, y1 = l1.p1.y, x2 = l1.p2.x, y2 = l1.p2.y;
    double x3 = l2.p1.x, y3 = l2.p1.y, x4 = l2.p2.x, y4 = l2.p2.y;
    double d1 = (y4-y3)*(x2-x1)-(x4-x3)*(y2-y1);
    double d2 = (y4-y3)*(x1-x3)-(x4-x3)*(y1-y3);
    double d3 = (y2-y1)*(x1-x3)-(x2-x1)*(y1-y3);
    double d4 = (y2-y1)*(x4-x3)-(x2-x1)*(y4-y3);
    if (d1 == 0) { // 平行或共线
        if (d2 == 0 && d3 == 0 && d4 == 0) { // 共线
            if (x1 == x3) { // 竖直线段
                if (y1 >= y3 && y1 <= y4 || y2 >= y3 && y2 <= y4 ||
                    y3 >= y1 && y3 <= y2 || y4 >= y1 && y4 <= y2) {
                    return true; // 重叠部分不为空
                }
            } else { // 水平线段
                if (x1 >= x3 && x1 <= x4 || x2 >= x3 && x2 <= x4 ||
                    x3 >= x1 && x3 <= x2 || x4 >= x1 && x4 <= x2) {
                    return true; // 重叠部分不为空
                }
            }
        }
        return false; // 平行
    }
    double r = d2 / d1, s = d3 / d1;
    if (r < 0 || r > 1 || s < 0 || s > 1) {
        return false; // 不相交
    }
    return true; // 相交
}

// 判断多边形是否自相交
bool isSelfIntersected(vector<Point> poly) {
    int n = poly.size();
    for (int i = 0; i < n; i++) {
        Line l1(poly[i], poly[(i+1)%n]);
        for (int j = i+2; j < n; j++) {
            Line l2(poly[j], poly[(j+1)%n]);
            if (intersect(l1, l2)) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    vector<Point> poly = {Point(0, 0), Point(0, 1), Point(1, 1), Point(1, 0)};
    cout << isSelfIntersected(poly) << endl; // 0
    poly.push_back(Point(0.5, 0.5));
    cout << isSelfIntersected(poly) << endl; // 1
    return 0;
}

以上代码中，`Point` 结构体表示点，`Line` 结构体表示线段。`intersect` 函数用于判断两条线段是否相交，`isSelfIntersected` 函数用于判断多边形是否自相交。在 `isSelfIntersected` 函数的实现中，我们对多边形上的每一条线段进行两两比较，如果发现有相交的线段，则直接返回结果。