-
公开(公告)号：CN103345509B
公开(公告)日：2016-08-10
申请号：CN201310279899.0
申请日：2013-07-04
Applicant: 上海交通大学
Abstract: 本发明提供了一种获取路网上复反向最远邻居的层次分区树方法及系统，包括：对于路网G，某一查询集Q，构建路网G关于查询集Q的最远Voronoi图，定义某一查询点q∈Q在所述最远Voronoi图上的最远Voronoi区是这样一部分结点fvc(q,Q)，满足对于fn(p,Q)=q,即所有fvc(q,Q)所包含的点p均以q作为其相对于Q的最远邻居，则BRFN(q,Q,VG)=fvc(q,Q);为了获取fvc(q,Q)，首先建立一个包含路网G上所有点VG的潜在解的集合S,每次从Q的其余结点中取出一个结点q′,根据所述集合S中每个潜在解到q和q′的距离将S划分为两部分后，将距离查询点q较近的部分从S中删除，直至Q的所有其余结点q′都取出过后，所述最远Voronoi图中最终未删除的部分即为fvc(q,Q)，其中，所述潜在解为路网G上的某一结点，能够在路网上快速搜索到查询点的单反向邻居。
-
-
公开(公告)号：CN103336825A
公开(公告)日：2013-10-02
申请号：CN201310280205.5
申请日：2013-07-04
Applicant: 上海交通大学
IPC: G06F17/30
Abstract: 本发明提供了一种获取路网上单反向最远邻居的暴力搜索方法及系统，包括：对于给定路网G上的某一结点p和路网G上的所有结点VG，如果路网G上存在结点q，q与p的路网距离||q-p||不小于p到VG当中任何点p’的距离||p′-p||，则定义q为p相对于VG的最远邻居，记为fn(p,VG)；对于给定路网G上的所有结点VG，定义q的单反向最远邻居是VG中以q作为最远邻居点的集合即MRFN(q,VG)={p|p∈VG,fn(p,VG∪{q})=q}；使用Dijkstra算法以每一个d∈VG作为源点进行一次扩展，直到查询点q被访问到为止，若q在路网上的其他点被全部遍历之前被访问到，则q并非d的最远邻居，从而d不属于q的反向最远邻居；若q在路网上的其他点被全部遍历之后才被访问到，则确定d为p，p∈MRFN(q,VG)，能够在路网上快速搜索到查询点的单反向邻居。
-
公开(公告)号：CN103365983B
公开(公告)日：2016-09-07
申请号：CN201310279130.9
申请日：2013-07-04
Applicant: 上海交通大学
IPC: G06F17/30
Abstract: 本发明提供了一种获取路网上单反向最远邻居的层次分区树方法及系统，包括：将层次分区树的所有分区压入一遍历队列，从所述遍历队列依次弹出每个分区或子分区SGi，判断每个子分区SGi，是否使得若是，则SGi中的结点将该子分区从队列中排除，若否，将该未排除的子分区的子分区SGi或无子分区的子分区自身压入所述遍历队列，从所述遍历队列依次弹出每个子分区的子分区SGi，并重复上述判断，直至从所述遍历队列里只剩下无子分区的分区或子分区，并检查每一个未排除的分区中的节点d∈P的最远邻居是不是q，如果是，则确定d为p，p∈MRFN(q,P)。本发明能够在路网上快速搜索到查询点的单反向邻居。
-
-
Patent Agency Ranking
公开(公告)号：CN103345509A
公开(公告)日：2013-10-09
申请号：CN201310279899.0
申请日：2013-07-04
Applicant: 上海交通大学
Abstract: 本发明提供了一种获取路网上复反向最远邻居的层次分区树方法及系统，包括：对于路网G，某一查询集Q，构建路网G关于查询集Q的最远Voronoi图，定义某一查询点q∈Q在所述最远Voronoi图上的最远Voronoi区是这样一部分结点fvc(q,Q)，满足对于fn(p,Q)=q,即所有fvc(q,Q)所包含的点p均以q作为其相对于Q的最远邻居，则BRFN(q,Q,VG)=fvc(q,Q);为了获取fvc(q,Q)，首先建立一个包含路网G上所有点VG的潜在解的集合S,每次从Q的其余结点中取出一个结点q′,根据所述集合S中每个潜在解到q和q′的距离将S划分为两部分后，将距离查询点q较近的部分从S中删除，直至Q的所有其余结点q′都取出过后，所述最远Voronoi图中最终未删除的部分即为fvc(q,Q)，其中，所述潜在解为路网G上的某一结点，能够在路网上快速搜索到查询点的单反向邻居。
-
公开(公告)号：CN103336827A
公开(公告)日：2013-10-02
申请号：CN201310280245.X
申请日：2013-07-04
Applicant: 上海交通大学
IPC: G06F17/30
Abstract: 本发明提供了一种获取路网上复反向最远邻居的暴力搜索方法及系统，本发明通过使用Dijkstra算法以每一个d∈VG作为源点进行一次扩展，直到Q中的所有点被访问到为止，若q在Q中的所有点被全部遍历之前被访问到，则q并非d的最远邻居，从而d不属于q的反向最远邻居；若q在Q中的其他点被全部遍历之后仍未被访问到，则确定d为p，p∈BRFN(q，Q，VG)，能够在路网上快速搜索到查询点的单反向邻居。
-
公开(公告)号：CN103336827B
公开(公告)日：2016-11-30
申请号：CN201310280245.X
申请日：2013-07-04
Applicant: 上海交通大学
IPC: G06F17/30
Abstract: 本发明提供了一种获取路网上复反向最远邻居的暴力搜索方法及系统，本发明通过使用Dijkstra算法以每一个d∈VG作为源点进行一次扩展，直到Q中的所有点被访问到为止，若q在Q中的所有点被全部遍历之前被访问到，则q并非d的最远邻居，从而d不属于q的反向最远邻居；若q在Q中的其他点被全部遍历之后仍未被访问到，则确定d为p，p∈BRFN(q,Q,VG)，能够在路网上快速搜索到查询点的单反向邻居。
-
公开(公告)号：CN103324746B
公开(公告)日：2016-08-31
申请号：CN201310279900.X
申请日：2013-07-04
Applicant: 上海交通大学
IPC: G06F17/30
Abstract: 本发明提供了一种获取路网上复反向最远邻居的递进最远分区方法及系统，包括：首先建立一个包含路网G上所有点VG的潜在解的集合,每次从Q的其余结点中取出一个结点q′,使用Erwig and Hagen算法根据所述潜在解的集合中每个潜在解到q和q′的距离将所述潜在解的集合划分为两部分后，将距离查询点q较近的部分从潜在解的集合中删除，直至Q的所有其余结点q′都取出过后，所述最远Voronoi图中最终未删除的部分即为fvc(q,Q)，其中，所述潜在解为路网G上的某一结点，能够在路网上快速搜索到查询点的单反向邻居。
-
公开(公告)号：CN103365983A
公开(公告)日：2013-10-23
申请号：CN201310279130.9
申请日：2013-07-04
Applicant: 上海交通大学
IPC: G06F17/30
Abstract: 本发明提供了一种获取路网上单反向最远邻居的层次分区树方法及系统，包括：将层次分区树的所有分区压入一遍历队列，从所述遍历队列依次弹出每个分区或子分区SGi，判断每个子分区SGi，是否使得若是，则SGi中的结点将该子分区从队列中排除，若否，将该未排除的子分区的子分区SGi或无子分区的子分区自身压入所述遍历队列，从所述遍历队列依次弹出每个子分区的子分区SGi，并重复上述判断，直至从所述遍历队列里只剩下无子分区的分区或子分区，并检查每一个未排除的分区中的节点d∈P的最远邻居是不是q，如果是，则确定d为p，p∈MRFN(q,P)。本发明能够在路网上快速搜索到查询点的单反向邻居。
-
-
-
-
-
-
-
-
-
Search Results
11
records
(took 0.022 seconds)
