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

判断多边形是否存在自相交的算法可以使用射线法。具体思路是，对于多边形中的每条边，向外发射一条射线，如果这条射线与其他边相交了奇数次，则说明多边形存在自相交。

以下是一个示例代码，使用数组存储多边形的顶点坐标：

struct Point {
    double x, y;
};

bool isIntersect(Point a1, Point a2, Point b1, Point b2) {
    // 判断线段a1-a2和b1-b2是否相交
    double c1 = (b2.x - b1.x) * (a1.y - b1.y) - (b2.y - b1.y) * (a1.x - b1.x);
    double c2 = (b2.x - b1.x) * (a2.y - b1.y) - (b2.y - b1.y) * (a2.x - b1.x);
    double c3 = (a2.x - a1.x) * (b1.y - a1.y) - (a2.y - a1.y) * (b1.x - a1.x);
    double c4 = (a2.x - a1.x) * (b2.y - a1.y) - (a2.y - a1.y) * (b2.x - a1.x);
    if ((c1 * c2 < 0) && (c3 * c4 < 0)) {
        return true;
    }
    return false;
}

bool isSelfIntersect(Point p[], int n) {
    for (int i = 0; i < n; i++) {
        Point a1 = p[i], a2 = p[(i + 1) % n];
        for (int j = i + 2; j < n; j++) {
            Point b1 = p[j], b2 = p[(j + 1) % n];
            if (isIntersect(a1, a2, b1, b2)) {
                return true;
            }
        }
    }
    return false;
}

其中 `isIntersect` 函数用于判断两条线段是否相交，`isSelfIntersect` 函数用于判断多边形是否存在自相交。可以将多边形的顶点坐标存储在一个 `Point` 类型的数组中，参数 `n` 表示多边形的顶点数。