[图像处理] 计算n条线段的交点个数

问题

给出n条由[起点，终点]表示的线段，判断线段间的交点个数（要求O(nlogn)）

对于这一问题，可以分解为两个任务：
①快速判断两线段是否相交的方法
②优化的执行n条线段判断的方法

①线段相交判断

为了优化线段相交的判断，同样可分为两步：快速排斥实现和跨立实验

快速排斥实验

我们很容易得到这样一个结论：当两条线段相交时，以两个线段作为对角线的矩形必定相交
这类似碰撞检测时的一个预先的粗糙判断，具体实现也比较简单，即满足：

bool quick_check = min(p1.x, p2.x) < max(L.p1.x, L.p2.x) &&
                min(L.p1.x, L.p2.x) < max(p1.x, p2.x) &&
                min(p1.y, p2.y) < max(L.p1.y, L.p2.y) &&
                min(L.p1.y, L.p2.y) < max(p1.y, p2.y);
1
2
3
4

跨立实验

我们又有一个结论：当两条线段相交时，这两条线段必定相互跨立对方
以下图举例，此处的跨立意为：一条线段的两端点在另一条线段的两侧，如P1、P2分别在线段Q的两侧，Q1、Q2分别在线段P的两侧，此时P、Q即为相互跨立的关系，也一定满足相交关系

具体计算为：当P跨立Q时，向量(Q1, P1)和向量(Q1， P2)分别在向量(Q1, Q2)两侧，根据向量运算的关系有：
$$((Q1,Q2)\times (Q1,P1))\ast ((Q1,Q2)\times (Q1,P2))<0$$①叉乘的正负表示叉乘前向量到叉乘后向量的旋转方向+②点乘的正负表示两个向量是否同向
即向量(Q1, Q2)到另外两个向量的旋转方向相反，转换成坐标计算形式为：
$$((Q2.x-Q1.x)\ast (P1.y-Q1.y)-(Q2.y-Q1.y)\ast (P1.x-Q1.x))\ast ((Q2.x-Q1.x)\ast (P2.y-Q1.y)-(Q2.y-Q1.y)\ast (P2.x-Q1.x))<0$$

至此可以完成相交判断的代码，如下：

#include 
#include 

using namespace std;

struct Point
{
    int x, y;
    Point(){}
    Point(int x, int y):x(x), y(y){}
    
    static int cdot(const Point &p1, const Point &p2){
        return p1.x*p2.x + p1.y*p2.y;
    }
    static int xdot(const Point &p1, const Point &p2){
        return p1.x*p2.y-p1.y*p2.x;
    }
};


struct  Line
{
    Point p1, p2;
    Point line_vec;
    Line(const Point& p1, const Point& p2):p1(p1), p2(p2){
        line_vec = Point(p2.x-p1.x, p2.y-p1.y);
    }
    bool IsInter(const Line &L){
        bool quick_check = min(p1.x, p2.x) < max(L.p1.x, L.p2.x) &&
                        min(L.p1.x, L.p2.x) < max(p1.x, p2.x) &&
                        min(p1.y, p2.y) < max(L.p1.y, L.p2.y) &&
                        min(L.p1.y, L.p2.y) < max(p1.y, p2.y);
        if(quick_check){
            Point p1_Lp1 = Point(L.p1.x-p1.x, L.p1.y-p1.y);
            Point p1_Lp2 = Point(L.p2.x-p1.x, L.p2.y-p1.y);
            Point Lp1_p1 = Point(p1.x-L.p1.x, p1.y-L.p1.y);
            Point Lp1_p2 = Point(p2.x-L.p1.x, p2.y-L.p1.y);
            return Point::xdot(line_vec, p1_Lp1) * Point::xdot(line_vec, p1_Lp2)<0 && 
                            Point::xdot(L.line_vec, Lp1_p1) * Point::xdot(L.line_vec, Lp1_p2)<0;
        }
        return false;
    }
};

class LineVec
{
public:
    LineVec(){}
    void addLine(const Point &p1, const Point &p2){
        mLines.push_back(Line(p1, p2));
    }

public:
    vector<Line> mLines;

};

int main(){
    LineVec line_vec;
    line_vec.addLine(Point(0, 0), Point(1, 1));
    line_vec.addLine(Point(1, 0), Point(0, 1));
    cout << line_vec.mLines[0].IsInter(line_vec.mLines[1]) << endl;;
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

②n条线段相交判断

暂时没想到nlogn的做法，感觉是从排序的方法中借鉴思路？