1.一种方向感知的路网移动对象k近邻查询方法，应用于用户通过打车软件搜索最近的k辆出租车，查询点为用户的位置地点，路网移动对象为出租车；包括如下步骤：步骤1.评估查询范围；

方向感知的路网移动对象k近邻查询首先确定一个查询范围，其中包括了k近邻的候选对象；在查询范围内执行方向感知的路网移动对象k近邻查询方法提升查询效率，步骤如下：(11)利用网格索引定位查询点所在的网格，然后统计网格内的移动对象的数量num；设定探测系数μ＝2，如果num大于等于μ*k，得到该网格所覆盖的范围；

(12)若num小于μ*k，以当前网格为中心，向周围外扩一层网格，得到一个较大的网格，然后统计这个大网格内移动对象的数量，如此反复进行，直到移动对象的数量大于等于μ*k为止，以网格边界作为查询范围；

(13)把网格边界确定的查询范围之内移动对象到查询点的最大距离定义查询半径e；

步骤2.构建局部路网；

根据查询范围评估阶段确定的查询范围构建局部路网，并预计算局部路网中各节点到查询点的距离；

(21)在简单网格上执行欧式距离的范围查询，排除所有路网距离大于查询半径e的移动对象，获得方向感知的路网移动对象范围查询的候选对象；

(22)在R‑tree上执行欧式距离的范围查询从全局路网中获得局部路网的信息；R‑tree中是对全局路网的索引，保存了所有的道路信息，在R‑tree上进行一次查询，将半径为e的查询窗口作为输入，输出被查询范围覆盖的路段；最后根据获得的局部路网信息在内存中重构局部路网；

(23)使用Dijkstra最短路径算法预计算局部路网中各节点到查询点的距离，一方面为接下来方向感知的路网扩展提供服务，另一方面加速计算移动对象到查询点的路网距离；

步骤3.扩展方向感知的路网；

根据路网节点到查询点的距离由近及远扩展路网，当扩展到某个路段时，要获得路段上的移动对象；采用双索引结构，路网与移动对象分开索引导致从R‑tree只能检索路网信息，从简单网格只能检索移动对象信息，若想获得指定路段上的移动对象就必须关联两者信息，具体步骤如下：(31)首先根据给定的路段利用简单网格索引获取该路段覆盖的有效网格，然后获取有效网格内的移动对象；

(32)判断有效网格内的移动对象是否处于指定路段；一个移动对象在某个路段上的必要条件是该对象在路段的最小边界矩形中，借助R‑tree索引递归地自顶向下搜索，获取最小边界矩形包含了该移动对象的所有候选路段；计算移动点到候选路段之间的垂直距离，若移动点到指定路段的垂直距离最小，则说明该移动对象处于指定路段；

(33)对有效网格内所有移动对象进行过滤之后，便获得指定路段上的移动对象；

在取得指定路段上的移动对象之后要判断对象的运动方向是否朝向查询点；利用方位角来表征移动对象与路网扩展方向，方位角是从当前节点的指北方向线起，依顺时针方向到目标方向线之间的水平夹角，假定移动对象移动方向的方位角为α，路网扩展方向的方位角为β；朝向查询点的路网移动对象的判定准则为：逆着路网节点扩展方向运动的移动对象就是朝向查询点的移动对象，即α＝(β+180)mod360时，当前移动对象是朝向查询点运动的；

完成朝向查询点的判定之后，若移动对象朝向查询点运动则将当前移动对象加入候选集；若候选集中对象个数达到k个，需要判断是否继续扩展，只有当下一个路网节点到查询点的距离比候选集中距离最大的移动对象更近时，才需要继续扩展，否则算法在返回候选集中top‑k个移动对象后直接退出；

步骤4.迭代扩张查询范围；

若候选集中的移动对象个数为x个，x