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.
空间树结构
｜
269
空间树结构
虽然这里假定这是一棵二维树，但这种方法可用于任何维度。
l
.
e
ຏࣄݴ
l
.
e
ຏࠓ
图 10-2：使用
k-d
树划分二维平面
k
-
d
树是一个递归的二叉树结构，其中的每个结点包含了一个空间点和一个用于确定划
分方向的坐标标记（即
x
或
y
）。根结点表示的矩形区域范围是
(
x
low
=
－
∞
,
y
low
=
－
∞
,
x
high
= +
∞
,
y
high
= +
∞
)
，它被经过点
p
1
的竖线
V
进一步切分。左子树对
V
左侧的区域进行
进一步划分，右子树则对
V
右侧的区域进行进一步划分。根结点的左孩子表示顺着经过
p
2
的横线
H
进行切分，它将
V
左侧的区域细分为线
H
之上的区域和线
H
之下的区域。
根结点的左孩子的关联区域为
(
－
∞
,
－
∞
,
p
1
.x
, +
∞
)
，而右孩子的关联区域为
(
p
1
.x
,
≠ ∞
,
+
∞
, +
∞
)
。实际上，这些区域都是嵌套在一起的，我们可以看到祖先结点的区域完全包含
了其所有子孙结点的区域。
10.4.2 四叉树
四叉树
根据二维点集
P
递归地将整个空间细分为
4
个象限。它是一个树状结构，其中每
个非叶结点都有
4
个子结点。这些子结点被分别标记为
NE
（东北）、
NW
（西北）、
SW
（西
南）和
SE
（东南）。常见的四叉树有如下两
个显著的特点：
基于区域的四叉树
给定一张
2
k
×
2
k
像素的图片，其中每个像素要么是
0
要么是
1
。四叉树的根结点代
表整张图片。根结点的每个子结点代表了原始图片
2
k
－
1
×
2
k
－
1
的象限。如果
4
个区
域中的某个区域不全为
0
或不全为
1
，那么就继续将其切分，这些子区域的大小是
其父结点的
1/4 ...
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.