August 2017
Intermediate to advanced
360 pages
8h 35m
Chinese
Content preview from 算法技术手册（原书第2 版）
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
246
｜
第
9
章
9.5.2 使用环境
当交点的期望数目远远少于线段的个数时，此算法能够轻而易举地得到比穷举算法好很
多的性能。但是如果交点大量存在，那么算法的记录管理功能的实现复杂程度可能会超
过这个算法带来的好处。
扫描线的思想非常有用，因为它可以高效地构建扫描线状态并维护事件队列。在
线段扫
描算法
中，要考虑大量的特殊情况，因此代码会比穷举算法（时间复杂度为
O(
n
2
)
）复杂
很多。我们之所以选择本算法，是因为看重其性能的改进以及最坏情况下的表现。
线段扫描算法
在处理的过程中会不断生成结果。在这个例子中，扫描线状态其实是一个
线段的二叉平衡树，这样我们能够得到扫描线上线段的顺序。事件队列也可以简化为一
棵按字典序排序的事件点所组成的平衡二叉树。也就是说，
y
坐标值较大的点出现在前
面（因为在笛卡儿平面上扫描线是从上向下扫描），如果两个点具有相同的
y
值，则将
x
坐标值较小的点放在前面。
为了简化算法的编码，二叉树通常用一个扩展平衡二叉树来表示扫描线状态，这棵树只
有叶子结点才能存储真正的信息。内部结点存储了最左侧线段和最右侧线段的
min
和
max
信息。这棵树中
的线段顺序以
扫描点
为准，即从优先队列中取出。正在处理的事件
点（
Event Point
）。
线段扫描算法小结
最好情况、平均情况和最坏情况：
O((
n
+
k
)log
n
)
intersection (S)
EQ = new EventQueue
foreach s in S do
❶
ep = find s.start in EQ or create ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.