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.
12
｜
第
1
章
和最小点（即图
1-6
中用框圈起来的点），然后将每个区域中的这两个点以及点集的最
左点和最右点连起来，就得到一个近似凸包。当然，这样做有可能会漏掉实际上应该在
凸包中的点
P
1
，如图
1-6
所示。
图 1-6：通过近似计算得到凸包
1.3.5 融会贯通
通常，解决某一类问题的算法和解决某一个特定问题的算法是大致相通的。
Voronoi
图
（
Preparata and Shamos
，
1993
）是这样一个几何结构——它可以将平面上的点集划分成
多个区域，其中每个区域的重心点为输入集
P
中的点。每个区域
R
i
中任意一点
(
x
,
y
)
到
P
i
的距离都比到其他区域的重心点要近。图
1-7
展示了计算出的
Voronoi
图。灰色区域
是
半无限
的，并且灰色区域的重心点组成了凸包。由此可以得出以下算法：
1.
计算输入集
P
的
Voronoi
图。
2.
将
P
中的最低点
low
作为凸包的起始位置，并从与之相联的区域开始遍历。
3.
按顺时针顺序访问共享一条无限长边的邻接区域，并不断将这些区域的重心点加入
凸包。
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.