区域树(Range Tree)的构建(Build)与查询(Query)一、什么是区域树(Range Tree)二、区域树构建(Build)三、区域树查找(Query)
一、什么是区域树(Range Tree) 首先以2D Range Tree为例,在一个二维平面上有很多点,点都有x和y坐标,现在要查询在区域 [x1,x2] × [y1,y2] 范围内的所有点,常用的方法一般是先将数据点预处理成一棵树,然后通过对数中点集的查找来实现。其中区域树就是一种正交查找的常用方法,主要思路是将点沿X坐标建立一棵树,再将每个节点的子树按照Y坐标再建立一棵树,具体实现与查找见下文。二、区域树构建(Build) 首先对于平面中的四个点,可以根据...