数几何

扫描线算法(Line-Sweep)

字数统计: 3.5k字   |   阅读时长: 17分
, , ,

摘要: 扫描线算法：直线平移扫描

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文我们介绍一个计算几何中非常重要的算法：扫描线算法。除了计算几何之外，扫描线算法还可以解决很多区间的问题，力扣上有很多，比如 699、56、1854，更多参考 区间问题汇总。

扫描线算法常见的有直线平移扫描和射线旋转扫描两大类，本文主要学习直线平移扫描。

扫描线算法

扫描线算法是指扫描线在平面上按照给定轨迹移动的同时，根据扫描线扫过的部分更新信息，最终得到整体的结果。

扫描的方法可以是以竖直的直线从左向右扫描，也可以是以固定点的射线逆时针旋转。

下面介绍直线平移扫描可以解决的几个代表性的问题。

问题1: 以 n 个矩形的并集的面积

假想一个从左向右扫描的垂线，当前扫描到 x = x0 的位置，如果 query(x0) 返回 x0 位置的垂线分割矩形后的断面的长度和。则并集的面积就是侧函数对 x 进行定积分的结果。

对于边与 x 轴 y 轴平行的矩形，只有矩形的左右两边所在的 x1, x2，断面才会有变化。断面(或者所求的值)发生变化的位置称为事件，求出所有事件并按照位置排序后，事件之间的断面不发生变化，即两个事件 x1, x2 之间 query(x) 的值不变。

算法：扫描线算法

矩形定义

1
2
3
4
5
6
7
struct Rectangle
{
    ll x1, y1, x2, y2;
    Rectangle(ll x1, ll y1, ll x2, ll y2):x1(x1),y1(y1),x2(x2),y2(y2){}
};

vector<Rectangle> recs;

事件定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Event
{
    vector<Rectangle> *recs;
    int id; // 所属正方形 id
    int left; // 1 表示左边，-1 表示右边
    Event(vector<Rectangle> *recs, int id, int left):recs(recs),id(id),left(left){}
    ll getx() const
    {
        if(left == 1)
            return (*recs)[id].x1;
        else
            return (*recs)[id].x2;
    }
    bool operator<(const Event& e) const
    {
        return getx() < e.getx();
    }
};

在 x 位置的操作

将所有矩形的 y 坐标离散化，得到 ys

遍历事件时，统计事件位置 x 对应的 y 区间 [y1, y2]，对有几个离散化后的区间产生了影响，并记录。

枚举离散化后的 y 区间，如果 y1 <= ys[j] < y2，则记录，cnt[j] = [ys[i], ys[i+1]) 上的矩形个数。

代码模板

用数组维护 cnt $O(N^{2})$

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
ll union_area(vector<Rectangle>& recs)
{
    int n = recs.size();
    vector<Event> events;
    // 将 y 离散化，每经过一个 x，会有一条边变化，左边则加，右边则减，该变化会对应离散化后的某些区间产生影响。
    vector<int> ys;
    for(int i = 0; i < n; ++i)
    {
        ys.push_back(recs[i].y1);
        ys.push_back(recs[i].y2);
        events.emplace_back(&recs, i, 1);
        events.emplace_back(&recs, i, -1);
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    sort(events.begin(), events.end());
    vector<int> cnt((int)ys.size() - 1);
    // 遍历事件
    // 统计事件对应的左边或右边对有几个离散化后的区间产生了影响，并记录。
    // cnt[i] := [ys[i], ys[i+1]) 上的矩形个数
    ll ans = 0;
    for(int i = 0; i < (int)events.size(); ++i)
    {
        ll x = events[i].getx();
        int delta = events[i].left;
        ll y1 = recs[events[i].id].y1;
        ll y2 = recs[events[i].id].y2;
        for(int j = 0; j < (int)cnt.size(); ++j)
        {
            if(y1 <= ys[j] && ys[j] < y2)
                cnt[j] += delta;
        }
        ll len_y = 0;
        for(int j = 0; j < (int)cnt.size(); ++j)
            if(cnt[j] > 0)
                len_y += ys[j + 1] - ys[j];
        if(i + 1 < (int)events.size())
            ans += (events[i + 1].getx() - x) * len_y;
    }
    return ans;
}

当矩形个数不多的时候，这个 $O(N^{2})$ 的算法可以用。比如下面这个力扣的第 223 题。

题目 223. 矩形面积

给你 二维 平面上两个 由直线构成且边与坐标轴平行/垂直 的矩形，请你计算并返回两个矩形覆盖的总面积。

每个矩形由其 左下 顶点和 右上 顶点坐标表示：

  • 第一个矩形由其左下顶点 (ax1, ay1) 和右上顶点 (ax2, ay2) 定义。
  • 第二个矩形由其左下顶点 (bx1, by1) 和右上顶点 (bx2, by2) 定义。

提示：

1
-1e4 <= ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 <= 1e4

示例 1：
输入：ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
输出：45

示例 2：
输入：ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
输出：16

算法：扫描线算法

代码 (C++)

求两个矩形面积的并集。直接调用 union_area 即可。

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        vector<Rectangle> recs;
        recs.emplace_back(A, B, C, D);
        recs.emplace_back(E, F, G, H);
        ll ans = union_area(recs);
        return ans;
    }
};

优化：线段树维护 cnt

对于矩形，所有第二次出现的线段一定在之前是出现过的，他们是成对出现的。

每个左边界造成的影响一定要等到另一个和他配对的右边界到来才会消失，并且是完全消失，因此不需要 lazy 标记，但是对于梯形等不具备这个特性的，还是要写 lazy 标记。

查询只需要查根节点的数据。

代码 (C++)

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
class SegmentTree
{
public:
    SegmentTree(vector<ll> *ys)
    {
        this -> n = ys -> size();
        this -> ys = ys;
        tree.assign(n * 8, 0);
        len.assign(n * 8, 0);
    }

    void range_update_add(int i, int j, int delta)
    {
        _range_update(0, 0, n - 1, i, j, delta);
    }

    ll query()
    {
        // 查询整个区间
        return len[0];
    }

private:
    vector<int> tree; // 节点被覆盖的次数 cnt
    vector<ll> len; // 节点代表的区间被覆盖的长度 len
    vector<ll> *ys;
    int n;

    void _range_update(int node, int l, int r, int i, int j, int delta)
    {
        // 线段树节点 [l, r]
        if(l > r || l > j || i > r)
            return;
        if(i <= l && j >= r)
        {
            tree[node] += delta;
            if(tree[node] > 0)
                len[node] = (*ys)[r + 1] - (*ys)[l];
            else
                len[node] = len[node * 2 + 1] + len[node * 2 + 2];
            return;
        }
        int mid = (l + r) / 2;
        _range_update(node * 2 + 1, l, mid, i, j, delta);
        _range_update(node * 2 + 2, mid + 1, r, i, j, delta);
        if(tree[node] > 0)
            len[node] = (*ys)[r + 1] - (*ys)[l];
        else
            len[node] = len[node * 2 + 1] + len[node * 2 + 2];
    }
};

模板题 P5490 扫描线

求 n 个矩形的面积并。

代码模板 (C++)

实现前面的算法，包括线段树优化。

注：线段树的空间需要开 8n，开 4n 结果错误。

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <vector>
#include <climits>
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

using ll = long long;

class SegmentTree
{
public:
    SegmentTree(vector<ll> *ys)
    {
        this -> n = ys -> size();
        this -> ys = ys;
        tree.assign(n * 8, 0);
        len.assign(n * 8, 0);
    }

    void range_update_add(int i, int j, int delta)
    {
        _range_update(0, 0, n - 1, i, j, delta);
    }

    ll query()
    {
        // 查询整个区间
        return len[0];
    }

private:
    vector<int> tree; // 节点被覆盖的次数 cnt
    vector<ll> len; // 节点代表的区间被覆盖的长度 len
    vector<ll> *ys;
    int n;

    void _range_update(int node, int l, int r, int i, int j, int delta)
    {
        // 线段树节点 [l, r]
        if(l > r || l > j || i > r)
            return;
        if(i <= l && j >= r)
        {
            tree[node] += delta;
            if(tree[node] > 0)
                len[node] = (*ys)[r + 1] - (*ys)[l];
            else
                len[node] = len[node * 2 + 1] + len[node * 2 + 2];
            return;
        }
        int mid = (l + r) / 2;
        _range_update(node * 2 + 1, l, mid, i, j, delta);
        _range_update(node * 2 + 2, mid + 1, r, i, j, delta);
        if(tree[node] > 0)
            len[node] = (*ys)[r + 1] - (*ys)[l];
        else
            len[node] = len[node * 2 + 1] + len[node * 2 + 2];
    }
};


struct Rectangle
{
    ll x1, y1, x2, y2;
    Rectangle(ll x1, ll y1, ll x2, ll y2):x1(x1),y1(y1),x2(x2),y2(y2){}
};

struct Event
{
    vector<Rectangle> *recs;
    int id; // 所属正方形 id
    int left; // 1 表示左边，-1 表示右边
    Event(vector<Rectangle> *recs, int id, int left):recs(recs),id(id),left(left){}
    ll getx() const
    {
        if(left == 1)
            return (*recs)[id].x1;
        else
            return (*recs)[id].x2;
    }
    bool operator<(const Event& e) const
    {
        if(getx() == e.getx())
            return left > e.left;
        return getx() < e.getx();
    }
};

int find(ll v, const vector<ll>& aa) // 从 nums 的值找到对应的离散化之后的值
{
    return lower_bound(aa.begin(), aa.end(), v) - aa.begin();
}

ll union_area(vector<Rectangle>& recs)
{
    int n = recs.size();
    vector<Event> events;
    // 将 y 离散化，每经过一个 x，会有一条边变化，左边则加，右边则减，该变化会对应离散化后的某些区间产生影响。
    vector<ll> ys;
    for(int i = 0; i < n; ++i)
    {
        ys.push_back(recs[i].y1);
        ys.push_back(recs[i].y2);
        events.emplace_back(&recs, i, 1);
        events.emplace_back(&recs, i, -1);
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    sort(events.begin(), events.end());

    SegmentTree sttree(&ys);
    // 遍历事件
    // 统计事件对应的左边或右边对有几个离散化后的区间产生了影响，并记录。
    // cnt[i] := [ys[i], ys[i+1]) 上的矩形个数
    ll ans = 0;
    for(int i = 0; i < (int)events.size(); ++i)
    {
        ll x = events[i].getx();
        int delta = events[i].left;
        ll y1 = recs[events[i].id].y1;
        ll y2 = recs[events[i].id].y2;
        int l = find(y1, ys);
        int r = find(y2, ys);
        // 影响 ys 上的 [l, r) 区间
        sttree.range_update_add(l, r - 1, delta);
        ll len_y = sttree.query();
        if(i + 1 < (int)events.size())
        {
            ans += (events[i + 1].getx() - x) * len_y;
        }
    }
    return ans;
}

int main()
{
    int n;
    cin >> n;
    vector<Rectangle> recs;
    for(int i = 0; i < n; ++i)
    {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        recs.emplace_back(x1, y1, x2, y2);
    }
    ll ans = union_area(recs);
    cout << ans << endl;
}

问题2：矩形覆盖点

平面有一系列点 (x, y, w)，w 为权值，矩形的宽 w，高 h 固定。求矩形能覆盖到的最大权值和。

算法

考虑矩形的右上角位置 (X, Y)，对点 (x, y, w)，想要覆盖 (x, y, w)，需要有

1
2
3
4
X - x + 1 < W
Y - y + 1 < H
X > x
Y > y

由于 X, Y 可以取浮点数，因此可以假设所有点 (x, y) 向左下平移里一小段，使得 X == x, Y == y 也可以了。

即 x <= X < x + W - 1 和 y <= Y < y + H - 1，用闭区间表示，就是当矩形右上角的横纵坐标范围为在 [x, x + W - 2], [y, y + H - 2]，这是一个区域，即从 X 取到 x，Y 取到 y 开始可以取到点 (x, y)，这是一个事件。

当 x 取到 x + W - 1 或者 y 取到 y + H - 1 时，(x, y) 就取不到了，这也是一个事件。

取每个点 (x, y) 的左右边界作为事件，表示为 (x, y, y + h - 1, w), (x + w, y, y + h - 1, -w)

纵坐标建立一颗线段树，维护区间最大值。

代码 (C++)

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <vector>
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

using ll = long long;

class SegmentTree
{
public:
    SegmentTree(int n)
    {
        this -> n = n;
        tree.assign(n * 4, 0);
        lazy_add.assign(n * 4 , 0);
    }

    void range_update_add(int i, int j, int delta)
    {
        _range_update(0, 0, n - 1, i, j, delta);
    }

    int query()
    {
        return tree[0];
    }

private:
    vector<int> tree; // tree[i] := 当前事件的 x 下, y=i 可以取到的权值和
    vector<int> lazy_add;
    int n;

    void _range_update(int node, int l, int r, int i, int j, int delta)
    {
        if(lazy_add[node] != 0)
        {
            tree[node] = tree[node] + lazy_add[node];
            if(l != r)
            {
                lazy_add[node * 2 + 1] = lazy_add[node * 2 + 1] + lazy_add[node];
                lazy_add[node * 2 + 2] = lazy_add[node * 2 + 2] + lazy_add[node];
            }
            lazy_add[node] = 0;
        }
        // 线段树节点 node 持有的区间 [l, r]，待更新区间 [i, j]
        if(l > r || l > j || i > r)
            return;
        if(i <= l && r <= j)
        {
            tree[node] = tree[node] + delta;
            if(l != r)
            {
                lazy_add[node * 2 + 1] = lazy_add[node * 2 + 1] + delta;
                lazy_add[node * 2 + 2] = lazy_add[node * 2 + 2] + delta;
            }
            return;
        }
        int mid = (l + r) / 2;
        _range_update(node * 2 + 1, l, mid, i, j, delta);
        _range_update(node * 2 + 2, mid + 1, r, i, j, delta);
        tree[node] = max(tree[node * 2 + 1], tree[node * 2 + 2]);
    }
};

struct Rectangle
{
    ll x1, y1, x2, y2;
    Rectangle(){}
    Rectangle(ll x1, ll y1, ll x2, ll y2):x1(x1),y1(y1),x2(x2),y2(y2){}
};

struct Event
{
    vector<Rectangle> *recs;
    int id; // 所属矩形 id
    int left; // 1 表示左边，-1 表示右边
    int w; // 权值
    Event(vector<Rectangle> *recs, int id, int left, int w):recs(recs),id(id),left(left),w(w){}
    ll getx() const
    {
        if(left == 1)
            return (*recs)[id].x1;
        else
            return (*recs)[id].x2;
    }
    bool operator<(const Event& e) const
    {
        if(getx() == e.getx())
            return left < e.left;
        return getx() < e.getx();
    }
};

int find(ll v, const vector<ll>& aa) // 从 nums 的值找到对应的离散化之后的值
{
    return lower_bound(aa.begin(), aa.end(), v) - aa.begin();
}

int solve(vector<Rectangle>& recs, const vector<int>& w)
{
    vector<ll> ys;
    vector<Event> events;
    for(int i = 0; i < (int)recs.size(); ++i)
    {
        ys.push_back(recs[i].y1);
        ys.push_back(recs[i].y2);
        events.emplace_back(&recs, i, 1, w[i]);
        events.emplace_back(&recs, i, -1, w[i]);
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    sort(events.begin(), events.end());

    SegmentTree sttree((int)ys.size());

    int ans = 0;
    for(int i = 0; i < (int)events.size(); ++i)
    {
        int delta = events[i].left * events[i].w;
        ll y1 = recs[events[i].id].y1;
        ll y2 = recs[events[i].id].y2;
        int l = find(y1, ys);
        int r = find(y2, ys);
        // 影响 ys 上的 [l, r) 区间
        sttree.range_update_add(l, r, delta);
        ans = max(ans, sttree.query());
    }
    return ans;
}

int main()
{
    int n;
    ll W, H;
    while(cin >> n >> W >> H && (n > 0))
    {
        vector<Rectangle> recs;
        vector<int> ws;
        for(int i = 0; i < n; ++i)
        {
            ll x, y, w;
            cin >> x >> y >> w;
            recs.emplace_back(x, y, x + W, y + H - 1);
            ws.push_back(w);
        }
        int ans = solve(recs, ws);
        cout << ans << endl;
    }
}

问题3: 相交线段

给定线段集合判断有无交点。从左到右的扫描线，事件为线段的左右端点。算法如下：

1
2
3
枚举各个事件，得到与扫描线相交的线段，更新集合：
    如果是左端点，将新段 l 加入集合；插入前判断集合上与 l 相邻的线段与 l 是否有交点
    如果是右端点，将线段 l 从集合删除；删除前判断集合上与 l 相邻的线段与 l 是否有交点

题目

下面是几道 acwing 的题目，比较难，有时间感兴趣的可以看一看。

Share