江苏大学 学士学位论文
在实际应用中，记录路网信息的地图数据库往往规模庞大,而负责路径规划功能的导航计算机受车载环境和成本限制,处理能力和存储资源都十分有限,难以承担苛刻的计算量需求。所以 Dijkstra 算法通常不能直接使用[9]。本设计对 Dijkstra 算法的改进考虑了如下2点：
（1）对Dijkstra 算法中的邻接矩阵作改进，采用动态数据结构，用动态记录数组存储节点信息，这样比原来的邻接矩阵节省了很大的存储空间，也能很容易找到哪些节点间有通路，在一定程度上减少了算法的循环次数，这一点在程序设计中已经实现。
（2）采用基于矩形区域的递增法确定搜索范围，系统分别将用户输入的起始点和终止点两个顶点构成的矩阵扩大到一定的范围，并在扩大的矩形区进行搜索，如果不能得出一条最短路径, 则将范围递增型的再扩大后继续搜索, 直至能得到一条最短路径为止。它们的关系如图4.3所示，A点和B点是用户输入的起始点和终止点，系统将以横向长度a和纵向长度b将A点和B点分别向外扩展至C点和D点，并最终在矩形区域CD中进行搜索。如果不能在该区域内得出一条最短路径，则将C点和D点继续以a、b长度递增扩展，并在新的区域内进行搜索。其中的a值设为两条相邻垂直大路间的平均距离，b值设为两条相邻水平大路间的平均距离。算法流程如图4.4 所示，采用这种划分矩形区域和范围递增的方式进行路径搜索, 可以过滤掉部分与当前所要搜索的最短路径无关的节点. 而在判断某点是否在区域范围内只需判断两个数的大小, 减少了算法的规模和算法的复杂性, 节省了计算时间。
图4.3 范围扩增示意图
16
江苏大学 学士学位论文
图4.4 改进算法流程图
17
江苏大学 学士学位论文
第五章 路径规划子系统的实现
5．1 地图的制作
这部分工作是在SuperMap Deskpro中完成的，具体步骤如下： 1、 新建、保存工作空间zjjtmap
1）、点选【文件】－>【新建工作空间】 ，或在工作空间管理器中，点击鼠标右键，选中“新建工作空间?”；
2）、在弹出的对话框中输入工作空间的名字“zjjtmap”； 3）、保存工作空间。
2、 新建数据源（SQL Server空间数据库）
1）点选【文件】－>【新建数据源】 ，或在工作空间管理器中，右击zjjtmap，选中“新
建数据源?”；
2）在弹出对话框的“保存类型”的下拉框中，选择“SDX for SQL Server数据源”，出
现图5.1所示的对话框，输入相关的参数；
图5.1 连接数据库对话框
3）点击“确定”按钮；
4）回到“新建数据源”对话框中，输入文件名“zjjtmap”，点击“保存”按钮。 3、 导入栅格数据集
1）点选【数据集】－>【导入数据集】 ，或右击数据源zjjtmap，选中“导入数据集?”； 2）在出现的“批量导入数据”话框中选择“添加文件?”，打开“公路网.dat”文件； 3）点击“导入”，待文件导入状态出现“成功”字样，就表示已将栅格数据转化为矢量数； 4）点击“关闭”，回到工作空间，可发现在数据源zjjtmanp下已存在新的数据集“公路网
18
江苏大学 学士学位论文
L”。
4、 图层编辑
下面以编辑图层“公路网L”（图层与数据集一一对应）为例，具体操作：
1) 双击数据集“居民地R”，打开一个临时地图窗口；
2) 在工作空间管理器中，右击数据集“公路网L”，选中“添加到当前窗口?”； 3) 在图例编辑器中右击数据集“公路网L”，选中“可编辑”，或在工具栏上的下拉
列表框中选择要编辑的图层名称，或点击修改几何对象工具条中的第一个按钮
，这时可发现绘制工具栏可用工具将反蓝显示；
4) 选择“打断”工具，将相交的路打断，因为路径规划时需要用到交点信息，原始
地图里，本身并没有路的交叉点这个点，将路断开，拓扑处理的时候，才会在断开处出现交叉点；
5) 对几何对象、图层进行风格设置。
按照同样的方法编辑其他图层，同样直接引用图层名，不再详述其编辑过程。 5、保存地图
将编辑好的图层按顺序迭放在一起，显示在一个地图窗口中，就可以成为一个地图了。这时在地图上点击右键，保存地图，就可以完成地图的保存了。
5．2 路网拓扑处理
在路网的数学模型中,只需要用到结点与结点以及道路的连通性,即结点与结点以及线段之间的拓扑关系。由于在路径规划的实现过程中将通过道路信息进行计算,所以应在地图中建立一层路网拓扑图层, 道路必须在每个道路交叉口断开，道路数据将以图元的格式存放在数据库中,其中包括ID、图元的各点坐标。
SuperMap Deskpro中提供了将线数据集拓扑生成网络数据集，通过网络数据集生成和维护网络拓扑关系。具体实现步骤：
1）打开线数据集，显示在地图窗口中；
2）选择菜单“数据集－>线数据集拓扑处理?”，弹出“自动拓扑处理”对话框(如图5.2)； 3）对话框的“选项”页中设置：选择待处理的线数据集；在创建拓扑项里选择创建网络数据集，并为其命名；在错误处理选项中选择要进行哪些拓扑错误处理；
4）在“容限”页中设置各种拓扑容限；
19
江苏大学 学士学位论文
5）点击“应用”,“确定”按钮，即可生成网络数据集。
图5.2 自动拓扑处理对话框
拓扑处理完成以后，将生成的拓扑数据集添加到地图窗口中，保存地图，这样拓扑地图就制作完成了。
5．3 系统界面程序设计
地图制作完成以后，下面的工作是在Delphi7.0 中编程实现的。
Delphi是Windows下优秀的可视化编程环境，是当今流行的Windows程序开发环境之一，它的功能很强大。其主要特性是：有良好的可视化开发设计环境IDE；编译的速度一流、可执行程序的效率高；可执行程序对开发环境的依赖性很小；基于组件的可复用性和可扩展性强大；具有强大的数据库开发功能；CLX组件可开发跨平台的应用程序。Delphi 7.0是Borland公司经过进一步研究开发出的新一代产品，它的最显著的特点是增加了对Windows XP和.NET的支持。
1、 新建一个应用程序，将窗体命名为 FrmMain，保存应用程序为：将工程保存为MySuperMap.dpr，FrmMain对应的单元文件保存为Main.pas；
2、 在窗体上添加下列控件，设置如表5.1所示：
表5.1 控件设置表
控件类型 SuperWorkspace1 SuperMap Object1 控件名字 SuperWorkspace SuperMap 说明 工作空间 地图窗口 20