Skip to Main Content
算法技术手册(原书第2 版)
book

算法技术手册(原书第2 版)

by George T.Heineman, Gary Pollice, Stanley Selkow
August 2017
Intermediate to advanced content levelIntermediate to advanced
360 pages
8h 35m
Chinese
China Machine Press
Content preview from 算法技术手册(原书第2 版)
计算几何
253
计算几何
9.6 Voronoi
Fortune
1986
年创新性地使用线段扫描技术解决了笛卡平面上点集
P
Voronoi
的问题。
Voronoi
的应用非常广泛,例如生命科学和经济研究(
Aurenhammer, 1991
)。
Voronoi
图将平面分成
n
个区域,每个区域中的所有点到点
p
i
(
p
i
P
)
的距离都小于到其他
任何点
p
j
(
p
j
P
)
的距离。图
9-8
所示为
13
个点的
Voronoi
图,它包含
13
个区域(图中
的正方形)。当计算出
Voronoi
图之后,我们可进行如下操作
计算凸包。
计算点能组成的最大空心圆。
找到各个点的最近点。
找到集合中最近的两个点。
Fortune
扫描算法
使用了类似于检测线段相交线段扫描技术。回想一下,线段扫描算
法将点插入优先队列中然后按序处理,这样就抽象地模拟了一条扫描线。本算法也会维
护一个高效更新的线段状态,进而确定
Voronoi
。最重要的一点是,
Fortune
扫描算
中的扫描线需要将平面分成
3
个区域,如图
9-9
所示。
使用这条线扫描平面,一个
Voronoi
图就逐渐构建出来。在图
9-9
中,与
p
2
相关联的区
域已经完全计算出来了,即由
4
条粗线组成的一个半无限多边形。扫描线现在正在处
理点
p
6
,而
p
7
~
p
11
处于待处理状态。现在线段状态结构中需要维护的点为
p
1
p
4
p
5
p
3
理解
Fortune
扫描算法
的关键便是线段状态的结构,我们把这个结构叫作
海岸线
beach
line
)。在图
9-9
中,海岸线即黑色的曲线组成的区域;两条抛物线相交的点叫作 ...
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.
Start your free trial

You might also like

机器学习实战:基于Scikit-Learn、Keras 和TensorFlow (原书第2 版)

机器学习实战:基于Scikit-Learn、Keras 和TensorFlow (原书第2 版)

Aurélien Géron
Go语言编程

Go语言编程

威廉·肯尼迪
C++语言导学(原书第2版)

C++语言导学(原书第2版)

本贾尼 斯特劳斯特鲁普

Publisher Resources

ISBN: 9787111562221