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.
空间树结构
｜
287
空间树结构
空区域
我们从具有相同值的输入集合中随机选取一个随机点构造查询区域。算法性能见表
10-3
。
k
-
d
树几乎可以瞬间计算出结果。
表
10
-
3
：空区域情况下穷举算法的执行时间
n
/ 个
d
=
2
BF/ms
d
=
3
BF/ms
d
=
4
BF/ms
d
=
5
BF/ms
4,096 3.36 3.36 3.66 3.83
8,192 6.71 6.97 7.3 7.5
16,384 13.41 14.02 14.59 15.16
32,768 27.12 28.34 29.27 30.53
65,536 54.73 57.43 60.59 65.31
131,072 124.48 160.58 219.26 272.65
10.7 四叉树
四叉树可以用于解决如下查询：
范围查询
给定笛卡儿平面上的一个点集，判断点是否位于查询的矩形内。图
10-13
给出了一
个示例应用，其中虚线矩形来自于用户的选择操作，且矩形内的点呈高亮显示。当
某个四叉树区域被目标查询完全覆盖时，该区域会以灰色背景显示。
图 10-13：使用四叉树进行范围查询
碰撞检测
给定笛卡儿平面的一个对象集合，找出所有对象之间的交集。图
10-14
给出了一个
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.