WebGIS空间寻径算法设计（车辆自驾导航算法）

一.路网空间模型设计
采用有向连通图模型对路网建模

• A。以道路交叉点作为路网的连通图节点
• B。以从A路点到B路点的单向通路建立有向连线A->B，即普通道路建立A->B，B->A双向连接，单行道建立A->B单向连接
• C。高架桥、地下隧道做独立连接线处理；即，将高架或地下通道的起终点设立为连通图节点，并直接连接起终点，建立连线，中间不设定断点。
• D。在有向线段上设置属性，如：有分隔护栏、禁左转、禁掉头、高速路、城市一级道路、路口有交通灯等

路网数据使用MapInfo进行人工采编，并记录道路相关属性。完成数据编辑后，通过EasyLoader导入Oracle Spatial空间数据库。

二.空间数据结构设计
使用Oracle 10G Spatial存储空间数据结构

• A. 从MapInfo导入原始道路线路空间信息表，该表仅描述道路连线的空间数据和连线的道路相关属性，不对道路交叉结点进行描述。
• B。将原始的道路空间数据加工形成有向连通图模型数据
• 　B-1 对道路连线数据的起终点进行交叉重叠计算，建立路网结点数据表
• 　B-2 以路网结点数据表的结点数据为图点，建立图点间的有向连通线路数据表，并保存道路相关属性
• C. 计算并记录道路连通线的延展方向（向东、向西、向南、向北。。。），以辅助后期自驾中的文字描述（左转、右转、掉头）

三.寻径算法设计
结合Dijsk和A*算法，设计寻径模型，根据用户的寻径方案需求（最短路程、高速优先、综合优先），设计相应的寻径评估函数

• A.根据道路结点表和道路连线表，建立有向连通图的网状内存模型
• B。设计寻径过程中的条件排除规则（如，禁左，禁调头，有护栏，只走高速路等）
• C。设计寻径过程中的结点优先级排序算法，数据结构及优先级评估判定函数。
• D。设计算法的终止退出判定条件，包括：找到自驾方案；判定无可用方案。

四。程序实现设计
设计实现从用户输入起终点信息查询到获得文字及图形描述自驾方案的程序实现过程。

• A。根据用户输入关键字，结合分词搜索引擎和空间碰撞算法，查找最合理的起点终点的道路投影。
• B。根据起、终点的道路投影，并结合寻径算法，计算可用的路径方案，生成路径的数学模型描述。
• C。结合起点、重点以及道路的方向、位置等信息，转换生成人可识别的文字信息和路径几何描述。
• D。输出最终文字描述，并在地图图面描绘结果路径。

参考实现：猎图网 http://www.richmap.cn