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.
236
｜
第
9
章
9.2 凸包
对于二维平面上的点集
P
，凸包是能够包含
P
中所有点的最小凸多边形（在任意两点间
画的一条线段都完全在凸包内）。按照顺时针的方向开始，我们可以计算出有
h
个点的
P
的凸包，从
L
0
到
L
h
-1
，第一个点
L
0
是
P
中最左边的点，即
x
值最小的点。如果有多个
点的
x
值同为最小，那么选择
y
值最小的点。
给定
n
个点，存在
C
(
n
,3)
或者
n*
(
n
－
1
)*(
n
－
2)
个不同的三角形。如果一个点
p
i
(
p
i
∈
P
)
被
P
中任意其他三个点组成的三角形所包含，那么它不可能是凸包的一部分。例如，图
9-1
的点
p
6
被包含在
p
4
、
p
7
和
p
8
组成的三角形中。使用穷举算法可以枚举这些三角形
T
i
，
然后通过从这些三角形中一个一个地剔除点来得到凸包。
一旦知道哪些点可以组成凸包，那么接下来就是如何画出凸包。我们可以以标记为最左
边的点
L
0
为起点，将剩余的每个点与
L
0
连成一条线，然后根据这条线和水平线的夹角
从小到大进行排序，然后依次将这些点连起来即可。每三个点
L
i
、
L
i
+1
、
L
i
+2
都形成了一
个右转（同样适用于
L
h
-2
,
L
h
-1
,
L
0
）。
很明显，这种方法非常低效，它在检测三角形时就需要花费
O(
n
4
)
的时间。所以接下来
我们将会给描述一个高效的
凸包扫描
算法，它能够在
O(
n
log
n
)
的时间内计算出凸包。
图 9-1：平面上的点集及其凸包
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.