如何做一个类似于gps地图的寻找最近路线的系统
我最近接了一个业务,是关于地图的,要求是用鼠标点地图上的任意两个点,系统能实现最近路线的显示,有人懂着方面的设计吗,希望能够指点一二,本人在此先谢谢大哥大姐了!
-----------------------------------------------------------------------------------------
问题点数：100、回复次数：12Top
1 楼terryapp（terryapp）回复于 2006-06-24 14:24:24 得分 0
一个人?没基础?
恕我直言没可能.
最短路径的算法就有你好想想了...Top
2 楼iegrhn（‘）回复于 2006-06-24 15:38:46 得分 0
用A*算法Top
3 楼zhaogis（野猫）回复于 2006-06-24 19:19:44 得分 0
一般考虑到点的缓冲区内最近直线，然后再最短路径的算法。Top
4 楼hsghxm（专业杀鸡）回复于 2006-06-26 17:50:13 得分 0
不知道你用什么开发的，如果用esri的产品，直接有这样的接口：ITraceFlowSolver，很简单就可以搞定Top
5 楼sunzhong2003（）回复于 2006-06-27 08:29:11 得分 0
我搞了十天左右Top
6 楼slackwater（山林风雨）回复于 2006-06-29 17:00:19 得分 0
研究A*算法Top
7 楼tdoflying（tdoflying）回复于 2006-07-01 11:25:54 得分 0
很简单,理解用1星期,实现用4天就差不多了
2天做周边(点线的提取)2天做算法, 算法用标准最短路径, 大林
最后再揉一个显示, 以前收集的一个代码:
本例以由拓扑关系的arc/info 文件为数据源。其中a1,b1,c1是以fnode排序生成的数组，a1对应fnode,b1对应tnode,c1对应length,同样a2,b2,c2,是以tnode 生成的数组。Indexa1是对应某一起点与其相连的终点的个数，indexb1时对应某一终点与其相连的起点的个数，即其拓扑关系。
Public Function shortpath(startno As Integer, endno As Integer) As Single
以开始点，结束点为参数。
Dim result() As Single
Dim result1 As Integer
定义结果点
Dim s1 As Single
Dim min As Single
Dim ii, i, j, aa As Integer
Dim yc() As Boolean
Dim ycd() As Boolean
Dim rs1() As Single
Dim no() As Integer
Dim nopoint As Integer
ReDim yc(1 To maxno) As Boolean
ReDim ycd(1 To maxno) As Boolean
ReDim rs1(1 To maxno) As Single
ReDim result(1 To 2, 1 To maxno) As Single
定义结果，其中result(1,maxno)为结果点，result(2,maxno)为结果长度。
For i = 1 To maxno// maxno为网中最大的节点数。
yc(i) = False //标记已经查过的点。
ycd(i) = False //标记已经作结果点用过的点
rs1(i) = 1E+38 //假设从起点到任一点的距离都为无穷大
Next i
ll = startno //设置开始点。
yc(ll) = True //标记开始点为真。即已经作结果点用过。
j = 0
For aa = 1 To maxno
先从与开始点相连的终点寻找
For i = 1 To indexa1(2, ll) //以与ll点相连的起点的个数循环
result1 = b1(indexa1(1, ll) - i + 1)找出与LL点相连的终点的点号
s1 = c1(indexa1(1, ll) - i + 1) + result(2, ll)找出长度并求和
If yc(result1) = True Then GoTo 200如果以被经查过进行下一个
If ycd(result1) = True Then//如果已经作为结果点判断哪一个长
If rs1(result1) >= s1 Then//如果这一点到起点的长度比现在的路线长，替代
rs1(result1) = s1
result(1, result1) = ll//设置到这点的最短路径的前一点为LL点（精华部分）
result(2, result1) = s1设置到这点的最短路径长度
GoTo 200
Else
GoTo 200
End If
End If
如果上面的条件都不符合则进行下面的语句
ycd(result1) = True
rs1(result1) = s1
result(1, result1) = ll
result(2, result1) = s1
每找到一个点加一，为了下面的判断
j = j + 1
ReDim Preserve no(1 To j) As Integer
从新 定义数组并使其值为当前的点号
no(j) = result1
200 Next I
再从与开始点相连的终点寻找，与上面一样不再标注
For i = 1 To indexb2(2, ll)
result1 = a2(indexb2(1, ll) - i + 1)
s1 = c2(indexb2(1, ll) - i + 1) + result(2, ll)
If yc(result1) = True Then GoTo 300
If ycd(result1) = True Then
If rs1(result1) >= s1 Then
rs1(result1) = s1
result(1, result1) = ll
result(2, result1) = s1
GoTo 300
Else
GoTo 300
End If
End If
ycd(result1) = True
rs1(result1) = s1
result(1, result1) = ll
result(2, result1) = s1
j = j + 1
ReDim Preserve no(1 To j) As Integer
no(j) = result1
300 Next I
设置最小为无穷大，最短路径点为空
min = 1E+38
minpoint = Null
（优化部分）
找出已经查过点中长度最短的点
For i = aa To j
If min > rs1(no(i)) Then
ii = i
min = rs1(no(i))
minpoint = no(i)
End If
Next I
如果没有结果，即起点与终点没有通路退出程序
If min = 1E+38 Then Exit Function
（重点优化）将两点互换，减少循环。
no(ii) = no(aa)
no(aa) = minpoint
标记已经作为结果点判断过
yc(minpoint) = True
ll = minpoint
判断结果点是否等于终点，如果等于则已经找到最短路径
If minpoint = endno Then Exit For
Next aa
返回最短路径长度
Stpath = result(2, endno)
End Function
Top
8 楼yishh（）回复于 2006-07-01 20:17:49 得分 0
这种算法还得考虑到数据的规范性，不规范的数据很难有什么效果/Top
9 楼chy_hs（大脚test）回复于 2006-07-10 17:16:04 得分 0
赞同，对数据有一些要求
看看http://r.mapbased.com/wc/map.htm?sn=rwcgb&_l=zh_CN吧Top
10 楼ljz9425（阿九）回复于 2006-08-30 11:05:40 得分 0
也在寻找这样的办法Top
11 楼metrix（柳生杀神）回复于 2006-08-30 14:44:10 得分 0
从你的要求来看，用迪杰斯特拉算法很容易就搞定了，关键是你的数据要符合一定的要求，然后构造成算法所需要的格式，传递进去，出来就OK了。Top
12 楼lsj811228（追梦）回复于 2006-10-21 13:03:05 得分 0
我做过导航软件,这种算法是其中一点,有意可以交流!QQ:652787912Top
