本文涉及知识点数学 几何一维区域查找我们输入数据是一维空间中即一条直线上)的一个点集。需要查询该点集中落在某个一维矩形即某个区间[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(klogn)时间内查找出任何区间内的所有点。其中,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记录线上方的点。6V 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,depth1)Vleft←BuildKDTree(P1,depth1)7V 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,depth1)Vright←BuildKDTree(P2,depth1)8,生成一个节点v以存储直线l并分别将V l e f t 和 V r i g h t V_left和V_rightVleft和Vright设置为v的左、右孩子。9,return v。中值定义为从小到大第 ⌊ n 2 ⌋ 从小到大第\lfloor \frac n 2 \rfloor从小到大第⌊2n⌋个数。在O(n)时间内找到中位数的算法过于复杂预处理时将P按x排序QP,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(nk)时间内完成其中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)22f(n/4)。令n 4 k , g ( k ) f ( 4 k ) n 4^k,g(k)f(4^k)n4k,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)22g(k-1)22*22g(k-2)2^12^2\cdots 2^{k-1}2^k-2 \approx 2^k\sqrt{4^k}\sqrt nn→∞limf(n)22g(k−1)22∗22g(k−2)2122⋯2k−12k−2≈2k4kn3 区域树二维线段树、树套树)通过x建立线段树每个节点都包括一个二维树通过y建立)。性质一令线段树的根节点是第0层。从第一层起每层顶多有两个节点和查询区域部分重叠。且节点的左边界或右边界在查询区域。性质二从第一层起每层顶多两个顶多两个节点和全部在查询区域。下面用树数学归纳法证明第一层显然符合。节点区域全部在查询区域的节点进行第二维查询,故不会产生下一层的节点。不失一般性,令节点n是右边界在查询区域如果左孩子的右边界不在查询区域则左孩子不需处理右孩子需要处理。符合性质一二。如果左盒子的右边界在查询区域则右孩子完整在查询区域左孩子由边界在查询区域。符合性质一二。时间复杂度O(klognlogn) logn个节点全部在查询区域每个节点对y查询时间复杂度是O(logn)。空间复杂度O(nlogn)每个节点每层最多存储一次共logn层。4 高维区域树定理9给定由d维空间中任意n个点构成的集合,d ≥ 2 d \ge 2d≥2。对应于P的一棵区域树占用O(n l o g d − 1 n nlog^{d-1}nnlogd−1n)的存储空间并且可以在O(n l o g d − 1 n nlog^{d-1}nnlogd−1n)时间内构造处理。对这棵区域进行查询可以在O(kl o g d n log^dnlogdn)时间内从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 b0≤x,yM则将(a,b)转成a×Mb扩展阅读算法为骨CAD为魂亲士工具箱支持中望CAD2024、AutoCad2013及以上多年承接CAD项目的精华工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》《数学》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作活到老学到老。明朝中后期大约50%的进士能当上堂官(副部及更高)能当上堂官的举人只有十余人。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。视频课程先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。https://edu.csdn.net/course/detail/38771如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程https://edu.csdn.net/lecturer/6176测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。