判断多边形是否存在自相交 算法 c++

判断一个多边形是否存在自相交可以使用射线法。

具体步骤如下：

1. 从一个点出发画一条射线，如果这条射线与多边形的边界相交了奇数次，说明这个点在多边形内部；如果相交了偶数次，说明这个点在多边形外部。

2. 对于多边形的每个顶点，都画一条射线，如果存在任意两条射线相交，则说明多边形存在自相交。

C++代码实现如下：

#include <iostream>
#include <vector>
using namespace std;

struct Point {
    double x, y;
};

struct Segment {
    Point start, end;
};

// 计算两个向量的叉积
double crossProduct(Point A, Point B, Point C) {
    double BAx = A.x - B.x;
    double BAy = A.y - B.y;
    double BCx = C.x - B.x;
    double BCy = C.y - B.y;
    return BAx * BCy - BAy * BCx;
}

// 判断两条线段是否相交
bool isIntersect(Segment A, Segment B) {
    double cp1 = crossProduct(A.start, B.start, B.end);
    double cp2 = crossProduct(A.end, B.start, B.end);
    double cp3 = crossProduct(B.start, A.start, A.end);
    double cp4 = crossProduct(B.end, A.start, A.end);
    if ((cp1 * cp2 < 0) && (cp3 * cp4 < 0)) {
        return true;
    }
    return false;
}

// 判断多边形是否存在自相交
bool isSelfIntersect(vector<Point>& points) {
    int n = points.size();
    for (int i = 0; i < n; i++) {
        Segment s1 = { points[i], points[(i + 1) % n] };
        for (int j = i + 1; j < n; j++) {
            Segment s2 = { points[j], points[(j + 1) % n] };
            if (isIntersect(s1, s2)) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    vector<Point> points = {
        {0, 0},
        {1, 1},
        {2, 2},
        {1, 0},
        {2, -1}
    };
    if (isSelfIntersect(points)) {
        cout << "存在自相交" << endl;
    }
    else {
        cout << "不存在自相交" << endl;
    }
    return 0;
}

本算法的时间复杂度为 $O(n^2)$，其中 $n$ 是多边形的顶点数。如果需要更高效的算法可以考虑使用扫描线算法。