c++ 多边形是否相交

一个多边形是否相交可以通过判断其中是否存在交叉线段或者部分相交的方式来判断。如果存在这样的情况就说明多边形相交了，否则表示多边形不相交。

判断方法可以使用扫描线算法来实现。具体来说，可以先将多边形的顶点按照顺序排列，然后选择一条水平的扫描线从上向下扫描每一个顶点。在扫描过程中，可以将扫描线与多边形的边进行求交，并将交点插入一个有序的事件列表中。如果扫描线经过了一个顶点，那么就需要将该顶点插入到事件列表中。

接下来，需要初始化一个状态列表，表示扫描线与多边形的边是否相交。然后开始处理事件列表中的事件点。如果事件点是顶点，那么就需要更新状态列表并检查是否存在相交。如果事件点是交点，那么就需要交换相交边的状态并检查是否存在相交。

处理完所有的事件点后，就可以得到多边形是否相交的结果。如果状态列表中存在相交的边，那么就可以说明多边形相交了。否则，表示多边形不相交。

需要注意的是，扫描线算法可以用来判断简单多边形的相交性，而对于复杂多边形的情况需要采用其他算法来进行处理。

相关问题

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

判断多边形是否自相交，可以使用射线法。具体实现步骤如下：

1. 遍历多边形的每条边，依次将每条边作为射线，从一个端点向另一个端点发出一条射线。

2. 统计每条射线与多边形的交点数量，若交点数量为奇数，则说明射线从该端点出发与多边形相交，否则不相交。

3. 对于所有的射线进行判断，若有一条射线与多边形相交，则说明多边形自相交，否则不自相交。

具体实现可参考以下代码：

struct Point {
    int x, y;
    Point(int x = 0, int y = 0): x(x), y(y) {}
};

// 判断两条线段是否相交
bool intersects(Point& a1, Point& a2, Point& b1, Point& b2) {
    int c1 = (a2.x - a1.x) * (b1.y - a1.y) - (a2.y - a1.y) * (b1.x - a1.x);
    int c2 = (a2.x - a1.x) * (b2.y - a1.y) - (a2.y - a1.y) * (b2.x - a1.x);
    int c3 = (b2.x - b1.x) * (a1.y - b1.y) - (b2.y - b1.y) * (a1.x - b1.x);
    int c4 = (b2.x - b1.x) * (a2.y - b1.y) - (b2.y - b1.y) * (a2.x - b1.x);
    return ((c1 ^ c2) < 0 && (c3 ^ c4) < 0);
}

// 判断点是否在多边形内
bool inside(Point& p, vector<Point>& polygon) {
    int n = polygon.size(), cnt = 0;
    for (int i = 0; i < n; ++i) {
        Point& a1 = polygon[i], a2 = polygon[(i + 1) % n];
        if (a1.y == a2.y) continue;  // 忽略水平线段
        if (a1.y > a2.y) swap(a1, a2);  // 保证 a1 在 a2 下方
        if (p.y < a1.y || p.y >= a2.y) continue;  // 忽略射线与线段不相交的情况
        int x = (p.y - a1.y) * (a2.x - a1.x) / (a2.y - a1.y) + a1.x;  // 计算交点的 x 坐标
        if (x > p.x) cnt++;  // 统计交点数量
    }
    return (cnt & 1) == 1;  // 判断交点数量的奇偶性
}

// 判断多边形是否自相交
bool isSelfIntersecting(vector<Point>& polygon) {
    int n = polygon.size();
    for (int i = 0; i < n; ++i) {
        Point& a1 = polygon[i], a2 = polygon[(i + 1) % n];
        for (int j = i + 2; j < n; ++j) {
            Point& b1 = polygon[j], b2 = polygon[(j + 1) % n];
            if (intersects(a1, a2, b1, b2)) return true;  // 判断相邻两条边是否相交
        }
    }
    for (int i = 0; i < n; ++i) {
        if (inside(polygon[i], polygon)) return true;  // 判断顶点是否在多边形内部
    }
    return false;
}

其中，`intersects` 函数用于判断两条线段是否相交，`inside` 函数用于判断点是否在多边形内部，`isSelfIntersecting` 函数用于判断多边形是否自相交。

判断多边形是否自相交 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` 函数的实现中，我们对多边形上的每一条线段进行两两比较，如果发现有相交的线段，则直接返回结果。