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.
232
第
9
章
计算几何
计算几何可以算是数学领域里面最严密的问题之一，它需要高效准确地计算出几何结构
以及各种性质。由于篇幅和内容所限，这里只讨论在笛卡儿二维平面上的几何结构问题，
不过这些解法都可以很自然而然地推广到
n
维空间结构。在过去几个世纪里，数学家们
已经研究过大量类似的问题，但是从
20
世纪
70
年代开始，计算几何才开始被认为是一
个系统的领域学科。本章将介绍一些用于解决计算几何问题的抽象概念，这些方法并不
仅仅局限于计算几何问题。
本章的算法可以用于解决大量的现实生活中的问题：
凸包
计算出一个最小的凸多边形，从而将二维平面上点集
P
中的所有点包含在内。该问
题可以在
O(
n log n
)
的时间内解决，而无须使用
O(
n
4
)
的穷举解法。
线段相交
给定二维平面上由一些线段所组成的集合
S
，计算所有交点。该问题可以在
O((
n
+
k
)
log
n
)
的时间内完成，其中
k
是交点的个数，而无须使用
O
(
n
2
)
的穷举解法。
Voronoi
图
根据二维平面上点集
P
中各点的间距将平面分成多个区域，每个区域包含点集中的
一个点
p
i
，从而使每个区域中的任意一点到
p
i
的距离都小于等于到点集
P
中其他任
意一点
p
j
的距离。该问题可以在
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.