获取路网上单反向最远邻居的地标方法及系统

摘要

本发明提供了一种获取路网上单反向最远邻居的地标方法及系统，包括：使用Dijkstra算法预计算每个结点L到路网G上所有结点V_G的距离；对于每一个V_G中的结点d，使用三角不等式检查距离||d‑q||是否一定小于d到距离d最远地标f的距离||d‑f||，若结点L中存在地标u和f，使得||d‑u||+||u‑q||<||d‑f||，则q一定不是d的最远邻居，从而d一定不是q的反向最远邻居，将该结点d从路网上排除。本发明能够在路网上快速搜索到查询点的单反向邻居。

主权项

一种获取路网上单反向最远邻居的地标方法，其特征在于，包括：对于给定路网G上的某一结点p和路网G上的所有结点V_G，如果路网G上存在结点q，q与p的路网距离||q‑p||不小于p到V_G当中任何点p’的距离||p′‑p||，则定义q为p相对于V_G的最远邻居，记为fn(p,V_G)；对于给定路网G上的所有结点V_G，定义q的单反向最远邻居是V_G中以q作为最远邻居点的集合即MRFN(q,V_G)＝{p|p∈V_G,fn(p,V_G∪{q})＝q}；选择路网上的多个结点L作为地标，使用Dijkstra算法预计算每个结点L到路网G上所有结点V_G的距离；对于每一个V_G中的结点d，使用三角不等式检查距离||d‑q||是否一定小于d到距离d最远地标f的距离||d‑f||，若结点L中存在地标u，使得||d‑u||+||u‑q||＜||d‑f||，则q一定不是d的最远邻居，从而d一定不是q的反向最远邻居，将该结点d从路网上排除；使用Dijkstra算法以每一个d∈V_G作为源点进行一次扩展，直到查询点q被访问到为止，若q在路网上的其他点被全部遍历之前被访问到，则q并非d的最远邻居，从而d不属于q的反向最远邻居；若q在路网上的其他点被全部遍历之后才被访问到，则确定d为p，p∈MRFN(q,V_G)。