【计算几何第五章】正交区域查找：数据库查询

本文涉及知识点

数学 几何

一维区域查找

我们输入数据是一维空间中（即一条直线上)的一个点集。需要查询：该点集中落在某个一维矩形（即某个区间[x-x’])内的所有点。对点排序后，二分查找。排序

O

(

n

l

o

g

n

)

，查询

O

(

l

o

g

n

)

O(nlogn)，查询O(logn)

O(nlogn)，查询O(logn)。 定理5.2：给定由一维空间中任意n个点构成的集合P。可以使用O(n)空间，在O(nlogn)时间内构造一棵平衡二分查找树以存储P。这样，可以在O(k+logn)时间内查找出任何区间内的所有点。其中,k是实际被查找出来的点数。

2 kd-树

设P为由平面任意n个点构成的集合。针对P的一次二维矩形区域查找，就是从P中找出落在某一待查询矩形[x:x’]

×

\\times

×[y,y’]之内的所有点。点

p

:

=

(

p

x

,

p

y

)

落在改矩形内，当且仅当

p:=(p_x,p_y)落在改矩形内，当且仅当

p:=(px​,py​)落在改矩形内，当且仅当

p

x

∈

[

x

,

x

′

]

,

p

y

∈

[

y

,

y

′

]

p_x\\in[x,x'],p_y\\in[y,y']

px​∈[x,x′],py​∈[y,y′] 对于深度为偶数的节点，使用垂线进行划分;对于深度为奇数的节点，将使用水平线进行划分。这样的树称为kd树(kd-tree)，最初这个名字的含义为k维树（k-dimensional tree）。最初的含义已经不复存在，现在都将2d-树称为2维kd-树。

算法BuildKDTree(P,depth)

输入：点集P以及当前的深度depth 输出：与P对应的kd-树的根节点。 1 如果(P只含有一个点) 2 then return(存在改节点的叶子) 3 如果(depth是偶数) 4 the 沿着通过P内各点x-坐标中值的垂线l,将P划分成左、右两两个子集,P1为l左侧或之上的点集，P2为l右侧的点集。 5 else 沿桌通过P内各点y-坐标中值水平线l，将P划分为上、下两个子集,P1记录l下方或之线上的点，P2记录线上方的点。 6

V

l

e

f

t

←

B

u

i

l

d

K

D

T

r

e

e

(

P

1

,

d

e

p

t

h

+

1

)

V_{left} \\leftarrow BuildKDTree(P_1,depth+1)

Vleft​←BuildKDTree(P1​,depth+1) 7

V

r

i

g

h

t

←

B

u

i

l

d

K

D

T

r

e

e

(

P

2

,

d

e

p

t

h

+

1

)

V_{right} \\leftarrow BuildKDTree(P_2,depth+1)

Vright​←BuildKDTree(P2​,depth+1) 8,生成一个节点v以存储直线l，并分别将

V

l

e

f

t

和

V

r

i

g

h

t

V_left和V_right

Vl​eft和Vr​ight设置为v的左、右孩子。 9,return v。 中值定义为

从小到大第

⌊

n

2

⌋

从小到大第\\lfloor \\frac n 2 \\rfloor

从小到大第⌊2n​⌋个数。 在O(n)时间内找到中位数的算法过于复杂，预处理时将P按x排序，Q=P,Q按y排序。 引理5.3：给定任意n个点组成的一个集合，其对应的k-d树占用O(n)空间，并可以在O(nlogn)时间内构造出来。 引理5.4:如果待查区域为与坐标轴平行的矩形，那么对于存储了任意n个点的一棵k-d树，每次查询都可以

O

(

n

+

k

)

时间内完成，其中

k

为实际报告出来的点数。

O(\\sqrt n + k)时间内完成，其中k为实际报告出来的点数。

O(n

​+k)时间内完成，其中k为实际报告出来的点数。 算法 SearchKDTree(v,R) 输入：kd-树的根节点v，以及待查区域R 输出：所有以v为祖先，位于R之内的叶子所对应的点 1 如果v是叶子 2 #then 如果v落在R之内，则把它报告出来。 3 #else if(左子树全部在R中) 4 # then 报告左子树所有节点 5## 如果左子树和R相交 6### then SearchKDTree(左子树,R) 7 # if(右子树全部在R中) 8 # 报告右子树 9 # else 如果右子树和R相交 10## SearchKDTree 右子树 第4行和第8行的时间复杂度是O(k),除此之外的运行时间和R相交的子树数线性相关。f(n)计算任意垂线最多和多少棵子树相交。 f(1)=1 f(2)=2 f(3)=4 f(n)=2+2f(n/4)。 令

n

=

4

k

,

g

(

k

)

=

f

(

4

k

)

n = 4^k,g(k)=f(4^k)

n=4k,g(k)=f(4k) 求

lim

⁡

n

→

∞

f

(

n

)

=

2

+

2

g

(

k

−

1

)

=

2

+

2

∗

2

+

2

g

(

k

−

2

)

=

2

1

+

2

2

+

⋯

2

k

−

1

=

2

k

−

2

≈

2

k

=

4

k

=

n

\\lim\\limits_{n \\to \\infty}f(n)=2+2g(k-1)=2+2*2+2g(k-2)=2^1+2^2+\\cdots 2^{k-1}=2^k-2 \\approx 2^k=\\sqrt{4^k}=\\sqrt n

n→∞lim​f(n)=2+2g(k−1)=2+2∗2+2g(k−2)=21+22+⋯2k−1=2k−2≈2k=4k

​=n

​

3 区域树（二维线段树、树套树)

通过x建立线段树，每个节点都包括一个二维树（通过y建立)。 性质一：令线段树的根节点是第0层。从第一层起，每层顶多有两个节点，和查询区域，部分重叠。且节点的左边界或右边界在查询区域。 性质二：从第一层起，每层顶多两个顶多两个节点和全部在查询区域。 下面用树数学归纳法证明，第一层显然符合。节点区域全部在查询区域的节点，进行第二维查询,故不会产生下一层的节点。不失一般性,令节点n是右边界在查询区域，如果左孩子的右边界不在查询区域，则左孩子不需处理，右孩子需要处理。符合性质一二。如果左盒子的右边界在查询区域，则右孩子完整在查询区域，左孩子由边界在查询区域。符合性质一二。 时间复杂度：O(k+lognlogn) logn个节点全部在查询区域，每个节点对y查询，时间复杂度是O(logn)。 空间复杂度：O(nlogn)，每个节点每层最多存储一次，共logn层。

4 高维区域树

定理9：给定由d维空间中任意n个点构成的集合,

d

≥

2

d \\ge 2

d≥2。对应于P的一棵区域树占用O(

n

l

o

g

d

−

1

n

nlog^{d-1}n

nlogd−1n)的存储空间，并且可以在O(

n

l

o

g

d

−

1

n

nlog^{d-1}n

nlogd−1n)时间内构造处理。对这棵区域进行查询，可以在O(k+

l

o

g

d

n

log^dn

logdn)时间内，从P中报告出落在给定(超)矩形待差区域之内的所有点，其中k为实际被报告的点数。

5 一般性点集

处理x或y坐标相同的点，将实数坐标(a,b)替换成合成数空间（composite number space）的元素。 我的理解：

0

≤

x

,

y

<

M

，则将

(

a

,

b

)

转成

a

×

M

+

b

0 \\le x,y < M，则将(a,b)转成a \\times M +b

0≤x,y<M，则将(a,b)转成a×M+b

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程 https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17 或者 操作系统：win10 开发环境： VS2022 C++17 如无特殊说明，本算法用**C++**实现。