判断两折线段是否相交

Question

折线段为LineString，即给出顺序连接线段的端点
除了暴力枚举两折线段的所有边，还有没有时间复杂度更低的算法

Answer 1

有一种基于扫描线的算法可以判断两条折线段是否相交，时间复杂度为O((n+m)log(n+m))，其中n和m分别为两条折线段的点数。下面是具体的实现思路：

• 将两条折线段的所有端点按照x坐标从小到大排序，如果x坐标相等则按照y坐标从小到大排序。这样可以保证扫描线从左往右扫描时，每个点都是按照从左往右、从下往上的顺序依次遍历的。

• 开始扫描线，从左往右依次扫描每个点。对于每个点，判断它是否是某条折线段的端点，如果是，则将该折线段的所有边加入到一个线段集合中。

• 对于线段集合中的每条线段，判断它是否与其他线段相交。可以使用线段树等数据结构来维护线段集合，并在插入线段和删除线段时判断相交关系。

• 如果存在相交的线段，则说明两条折线段相交。

下面是一个C++的实现示例，使用了STL中的set和pair来实现线段集合：

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <utility>

using namespace std;

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

struct Segment {
    Point p1;
    Point p2;
    Segment(Point p1, Point p2): p1(p1), p2(p2) {}
};

bool cmp(const Point& p1, const Point& p2) {
    if (p1.x != p2.x) {
        return p1.x < p2.x;
    } else {
        return p1.y < p2.y;
    }
}

bool intersect(const Segment& s1, const Segment& s2) {
    int x1 = s1.p1.x, y1 = s1.p1.y;
    int x2 = s1.p2.x, y2 = s1.p2.y;
    int x3 = s2.p1.x, y3 = s2.p1.y;
    int x4 = s2.p2.x, y4 = s2.p2.y;
    if (max(x1, x2) < min(x3, x4) || max(x3, x4) < min(x1, x2) ||
        max(y1, y2) < min(y3, y4) || max(y3, y4) < min(y1, y2)) {
        return false;
    }
    int c1 = (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1);
    int c2 = (x2-x1)*(y4-y1) - (y2-y1)*(x4-x1);
    int c3 = (x4-x3)*(y1-y3) - (y4-y3)*(x1-x3);
    int c4 = (x4-x3)*(y2-y3) - (y4-y3)*(x2-x3);
    return (c1*c2 <= 0) && (c3*c4 <= 0);
}

int main() {
    // 读入两条折线段的端点
    int n, m;
    cin >> n >> m;
    vector<Point> points;
    for (int i = 0; i < n+m; i++) {
        int x, y;
        cin >> x >> y;
        points.push_back(Point(x, y));
    }

    // 按照x坐标从小到大排序，如果x坐标相等则按照y坐标从小到大排序
    sort(points.begin(), points.end(), cmp);

    // 扫描线
    set<pair<Segment, int>> segments;
    for (int i = 0; i < n+m; i++) {
        // 判断当前点是否是某条折线段的端点
        if (i > 0 && points[i].x == points[i-1].x && points[i].y == points[i-1].y) {
            continue;
        }
        int j = i+1;
        while (j < n+m && points[j].x == points[i].x && points[j].y == points[i].y) {
            j++;
        }
        if (j-i == 2) {
            // 当前点是一条线段的端点
            Segment seg(points[i], points[j-1]);
            if (i < n) {
                // 第一条折线段
                segments.insert(make_pair(seg, 1));
            } else {
                // 第二条折线段
                segments.insert(make_pair(seg, 2));
            }
        }
        i = j-1;
    }

    // 判断相交关系
    for (auto it1 = segments.begin(); it1 != segments.end(); it1++) {
        for (auto it2 = next(it1); it2 != segments.end(); it2++) {
            if (it1->second != it2->second && intersect(it1->first, it2->first)) {
                cout << "Two segments intersect" << endl;
                return 0;
            }
        }
    }
    cout << "Two segments do not intersect" << endl;
    return 0;
}

这个程序先将所有点按照x坐标从小到大排序，然后扫描线从左往右依次扫描每个点，将每条线段加入到一个set中。最后，遍历set中的所有线段，判断它们是否相交。