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.
234
｜
第
9
章
这些概念可以很自然地扩展到多维空间：
IMultiPoint
表示一个
n
维的笛卡儿平面点，每个坐标值是双浮点精度。实现版本可以确定和另
外一个相同维度的
IMultiPoint
的距离，也可返回一个坐标值的数组以优化某些算
法的性能。
IHypercube
表示一个
n
维的立体形体，每个维度的边界为
[
left
,
right
]
。它需要能够判断是否和
一个
IMultiPoint
相交或者是否包含一个同维度的
IHypercube
。
每个接口都会有各种实现版本（例如
TwoDPoint
就会实现
IPoint
和
IMultiPoint
两个
接口）。
一般来说，点的坐标值都是实数，所以实现必须使用浮点值来存储数据。在
20
世纪
70
年代，由于计算机硬件的限制，浮点计算的费用要大于整数计算的费用。但是现在的计
算机已经不需要考虑这个因素了。我们在第
2
章讨论了几个更重要的浮点计算问题（例
如舍入错误），这些问题会对本章算法产生一定的负面影响。
9.1.2 计算类型
计算几何问题大致可以分为以下三类，见表
9-1
。
查询
寻找数据中满足条件限制（例如包含、最近或者最远）的元素，这类任务和第
5
章
的查找算法直接相关（第
10
章也会涉及）。
几何计算
在输入集（例如线段）上进行一系列的计算，得到一些包含输入数据的几何结构（例
如线段的相交点）。
预处理
将大规模的输入集组织成一种数据结构后，来回答一系列的问题。换句话说，预处
理任务的结果将作为一系列问题的输入。
表
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.