多边形自相交判断 实现

判断多边形是否自相交可以采用射线法、三角剖分法等多种方法，这里介绍一种基于求解交点的方法。

假设有一个简单多边形，可以将其顶点按逆时针顺序排列。对于任意两条边 $AB$ 和 $CD$，如果它们不共线且相交，则交点 $P$ 必定在边 $AB$ 和边 $CD$ 的延长线上。因此，可以将多边形的每条边看作一个线段，依次检查每对线段是否相交，如果相交，则判断是否在延长线上。如果存在交点且在延长线上，则说明多边形自相交。

具体实现步骤如下：

1. 构造线段类，包含起点和终点坐标。

2. 对于多边形的每条边 $AB$，依次检查它和后面的每条边 $CD$ 是否相交。

3. 如果 $AB$ 和 $CD$ 不共线，则计算它们的交点，判断交点是否在 $AB$ 和 $CD$ 的延长线上。

4. 如果存在交点且在延长线上，则说明多边形自相交。

代码实现如下（以C++为例）：

#include <iostream>
#include <vector>

using namespace std;

// 线段类
class Segment {
public:
    int x1, y1, x2, y2;
    Segment(int a, int b, int c, int d) : x1(a), y1(b), x2(c), y2(d) {}
};

// 判断两条线段是否相交
bool isIntersect(Segment s1, Segment s2) {
    int x1 = s1.x1, y1 = s1.y1, x2 = s1.x2, y2 = s1.y2;
    int x3 = s2.x1, y3 = s2.y1, x4 = s2.x2, y4 = s2.y2;
    int d = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
    if (d == 0) return false;  // 两线段平行
    double ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) * 1.0 / d;
    double ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) * 1.0 / d;
    if (ua < 0 || ua > 1 || ub < 0 || ub > 1) return false;  // 交点不在线段上
    return true;
}

// 判断多边形是否自相交
bool isSelfIntersect(vector<Segment>& segments) {
    int n = segments.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (isIntersect(segments[i], segments[j])) {
                // 计算交点
                int x1 = segments[i].x1, y1 = segments[i].y1, x2 = segments[i].x2, y2 = segments[i].y2;
                int x3 = segments[j].x1, y3 = segments[j].y1, x4 = segments[j].x2, y4 = segments[j].y2;
                int x = ((x4 - x3) * (x2 - x1) * (y1 - y3) + y3 * (x2 - x1) * (x4 - x3) - y1 * (x4 - x3) * (x2 - x1)) / ((y4 - y3) * (x2 - x1) - (y2 - y1) * (x4 - x3));
                int y = ((y4 - y3) * (y2 - y1) * (x1 - x3) + x3 * (y2 - y1) * (y4 - y3) - x1 * (y4 - y3) * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3));
                // 判断交点是否在延长线上
                if ((x < x1 || x > x2) && (x < x2 || x > x1) && (x < x3 || x > x4) && (x < x4 || x > x3)) continue;
                if ((y < y1 || y > y2) && (y < y2 || y > y1) && (y < y3 || y > y4) && (y < y4 || y > y3)) continue;
                return true;
            }
        }
    }
    return false;
}

int main() {
    // 构造多边形（按逆时针顺序）
    vector<Segment> segments;
    segments.emplace_back(0, 0, 2, 0);
    segments.emplace_back(2, 0, 2, 2);
    segments.emplace_back(2, 2, 1, 1);
    segments.emplace_back(1, 1, 0, 2);
    segments.emplace_back(0, 2, 0, 0);
    // 判断多边形是否自相交
    if (isSelfIntersect(segments)) {
        cout << "The polygon is self-intersect." << endl;
    } else {
        cout << "The polygon is simple." << endl;
    }
    return 0;
}