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.
258
｜
第
9
章
㕐✲⟝
图 9-15：处理完圆事件之后的海岸线
9.6.1 输入 / 输出
输入为平面上的二维点集
P
。
Fortune
扫描算法
会计算出一个包含
n
个
Voronoi
多边形的
Voronoi
图，每个多边形即是
P
中每个点的区域。严格地说，有些区域是可以无限扩展的，但是该算法却将整个平面
置于一个大小适中的区域中，这个区域需要包含
P
中的所有点。输出即为一系列的线段
和顺时针排序的
Voronoi
多边形。
有些实现只能处理
P
不包含四点共圆的情况。
有些实现则需要保证两点不在同一条垂直或者水平线上。这些保证可以省略很多对特
殊情况的处理。此外，如果
x
、
y
坐标都是整数，处理起来将更加容易——可以在调用
Fortune
扫描
算法
前为坐标点添加一个随机小数。
9.6.2 解决方案
Fortune
的算法实现会比较复杂，因为整个计算过程需要维护海岸线的状态。这里忽略了
一些特殊情况。代码库中有完整的抛物线相交计算的实现。图
9-16
总结了下面的实现版
本中所需要的类。而且这个实现使用了
Python
的
heapq
模块，借助其中的
headpop
和
headpush
方法来构建和处理优先队列。
如例
9-14
所示，
process
方法为每个输入点创建了基址点事件，并按照
y
坐标值从大到
小的顺序（如果多个点的
y
坐标值相同，那么选择
x
坐标值较小的那个）依次处理每个事件。
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.