地理信息系统

目 录

摘 要……………………………………………………………………………3

ABSTRACT ………………………………………………………………………4

第1章 绪论……………………………………………………………………5

1.1本课题的研究意义与背景……………………………………………5

1.2相近研究课题的特点及优缺点分析…………………………………5

1.3本论文的内容和设计目标……………………………………………6

1.3.1本论文的内容……………………………………………………6

1.3.2本论文的设计目标………………………………………………6

第2章 需求分析………………………………………………………………6

2.1功能需求分析…………………………………………………………6

2.2数据需求分析…………………………………………………………6

2.3用户界面需求分析……………………………………………………6

第3章 系统分析………………………………………………………………7

3.1研究设计中要解决的问题……………………………………………7

3.1.1图的存储结构……………………………………………………7

3.1.2最短路径的绘制…………………………………………………7

3.1.3系统数据的格式…………………………………………………8

3.2关键技术及复杂性分析………………………………………………8

3.2.1十字链表作为图的存储结构……………………………………8

3.2.2形象动态绘制最短路径…………………………………………8

3.2.3采用XML格式存储系统数据……………………………………9

第4章 十字链表与DIJKSTRA算法分析 ……………………………………10

4.1十字链表描述…………………………………………………………10

4.2 DIJKSTRA算法描述 …………………………………………………12

4.2.1算法思想描述……………………………………………………12

4.2.2算法的复杂度分析………………………………………………13

第5章 系统设计………………………………………………………………14

5.1系统界面设计…………………………………………………………14

5.2系统状态与流程设计…………………………………………………14

5.3微型数据库设计………………………………………………………15

5.4系统模型设计…………………………………………………………15

第6章 系统实现………………………………………………………………16

6.1微型数据库实现………………………………………………………16

6.2Dijkstra引擎实现……………………………………………………17

6.3系统界面实现…………………………………………………………19

6.4系统关键状态与流程实现……………………………………………19

第7章 性能测试与分析………………………………………………………21

7.1测试环境………………………………………………………………21

7.2实例测试(表格与曲线)  ……………………………………………21

第8章 结束语…………………………………………………………………24

致 谢……………………………………………………………………………24

参考文献 ………………………………………………………………………25

附录 ……………………………………………………………………………26

附录1开发工具简介 …………………………………………………………26

摘 要

随着信息技术的飞速发展，GIS(地理信息系统)在现实中的应用也越来越重要。就区域而论，超级大的GIS有大到全球地理信息的导航，如Google的GoogleEarth 和GoogleMap、Microsoft的LiveEarth；大的GIS有大到城市地理信息的导航，如各城市的电子地图导航网站；小的GIS有小到公园、小区、校园等地理信息的导航。

本系统是以湖北民族学院为对象的校园导游系统，意在接触GIS并对Dijkstra算法进行更深一步的研究。

考虑到数据量小的原因，本系统采用XML文件作为数据源，并自建了一个以XML文件作为数据源、以XPath作为查询语言的微型数据库。在图的存储结构上，采用的是十字链表，无论是从顶点列表还是从边列表的任何一个节点都能够遍历该顶点的所有边。在求单源最短路径的过程中，可灵活的找到终点并停止运算，而不必将所有顶点的单源最短路径求出。

在图形界面方面，采用的是J2SE的Swing框架。在组件布局方面，用的是JlayeredPane 层级窗格，用于管理各组件的可见性。在路径绘制方面，用的是GlassPane 玻璃窗格，即在铺在图像上面的透明玻璃上绘制路径。

在操作方面，仅采用鼠标操作，尽可能减少操作的复杂性。

关键词：地理信息系统、dijkstra,十字链表,单源最短路径,XML,XPath,Swing，校园导游

ABSTRACT

With the rapid development of information technology, GIS (geographic information systems) in the reality of more and more important. District 1996, the GIS super large global geographic information to the navigation, such as Google and the GoogleEarth GoogleMap, Microsoft's LiveEarth; GIS is a big city geographic information to the navigation, such as the city's electronic map navigation site; GIS is a small park to small, community, school and other geographic information navigation.

The system is targeted at the Hubei Institute for Nationalities of the campus navigation system, intended to contact GIS and Dijkstra algorithm step further study.

Taking into account the reasons for the small amount of data, the system uses XML file as a data source, and to build an XML file as a data source to XPath as the mini-database query language. Figure in the storage structure, the use of a special cross chain, either from the list or the top of any list from the edge of a node can traverse the peak of all the edge. In seeking single-source shortest path in the process of flexibility to find the end and stop the operation, instead of all the top single-source shortest path obtained.

In a graphical interface, is based on the J2SE Swing framework. Components in the layout, using the JlayeredPane level pane, for the management of all components of visibility. Drawing in the path, using the GlassPane windows grid, that is, in the shop in the image above transparent glass on the road map.

In operation, only use the mouse operation, as far as possible to reduce the complexity of the operation.

KEY WORDS: geographic information system, dijkstra,cross chain, single-source shortest path, XML, XPath, Swing，campus navigation

第1章 绪论

1.1  本课题的研究意义与背景

地理信息系统（Geographic Information System，简称GIS），是20世纪60年代发展起来的一门融计算机技术、测绘科学、遥感、应用数学、信息科学、地球科学于一体的新兴交叉边缘学科。据统计，在人类的经济建设和日常社会生活中，有80%的信息与地理空间相关。GIS作为空间信息的存储、处理、应用的高新技术，其应用领域已经扩展到土地利用、资源管理、环境监测、交通运输、城市规划、经济建设等国民经济建设、规划、管理的方方面面。

最短路径问题作为地理学中一个重要问题，其在GIS中的应用无疑占有重要的地位，无论是交通运输，还是城市规划、物流管理、网络通讯等方面，它都发挥了重要的作用。因此对它的研究不但具有重要的理论价值，而且具有重要的应用价值

研究最短路径问题通常将它们抽象为图论意义下的网络问题，问题的核心就便成了网络图中的最短路径问题。关于最短路径问题，目前所公认的最好的求解方法，是1959年由E.W.Dijkstra提出的标号法，也就是人们长说的以它的名字所命名的Dijkstra算法。

1.2  相近研究课题的特点及优缺点分析

关于最短路径问题，目前所公认的最好的求解方法，是1959年由E.W.Dijkstra提出的标号法。在此算法思想的基础上，人们演绎出了几十种不同的优化算法，效果较好的算法有TQQ(graph growth with two queues)、DKA(the Dijkstra's algorithm implemented with approximate buckets)、DKD(the Dijkstra's algorithm implemented with doublebuckets)、排序优化算法等，前面3种算法将控件存储问题放在了以个重要位置，以牺牲适当的事件效率来换取空间节省，排序优化算法将事件放在了地一位，在提高时间效率方面有较好的应用性。

1.3  本论文的内容和设计目标

1.3.1 本论文的内容

介绍GIS的相关资料。

详细阐述Dijkstra算法的基本思想以及图的存储结构,尤其是图的存储结构，采用十字链表，以适应XML文件存储的顶点与边的数据格式。

详细阐述系统软件的模型。包括视图层、控制层、模型层、数据库层的相互通信。

1.3.2 本论文的设计目标

1.在图的存储结构上做特殊的改动，以提高Dijkstra算法的运算效率。

2.在系统数据的存储结构上，用XML高结构化的格式存储。

3.自定义一个微型数据库，以适应本系统的结构。

4.了解线程并应用线程到本系统中。

5.单鼠标操作完成系统功能。

第2章  需求分析

2.1  功能需求分析

用户能方便地给出起点与终点，给出后系统能相应地计算出最短路径，并形象生动地绘制最短路径，让用户一目了然。

2.2  数据需求分析

本课题与地理数据有关，所以要采集真实地点与虚拟拐点的名称与二维坐标值。计算最短路径，是在图的结构上进行，故要采集一个地点到另一个地点的关联与权值。

2.3  用户界面需求分析

用户界面给人以清晰爽朗，而易操作为主。

第3章  系统分析

3.1  研究设计中要解决的问题

3.1.1 图的存储结构

Dijkstra算法的基础是图，在计算机中如何对图进行存储表示，也直接影响着算法的计算效率。无向图可以用邻接矩阵和邻接多重表表示，而有向图则可以用邻接表和十字链表表示，其优缺点的比较如表3－1所示.

本Dijkstra算法采用十字链表做为图的存储结构。

3.1.2 最短路径的绘制

路径的定位，怎样在XOY坐标系中连接源点与终点，即用图标绘制两点间的直线？

路径的形式，是采用一定粗度的直线还是形象化的图像？直线较简单，只需调用绘制直线的函数即可。形象化的图像较复杂。

绘制的方式，是采用静态绘制还是动态绘制？静态绘制，意味着最短路径在极短的时间内全显现出来。动态绘制，以一种动态的感觉从起始点一步一步绘制到终点。静态绘制较简单，只需调用绘制函数，绘制起始点到终点的直线即可。动态绘制较复杂。

3.1.3 系统数据的格式

系统的相关数据，是存储在Text文本文件中还是存储在像SQLServer这样的数据库中？校园的地理数据小，存储在数据库中，有点小题大做。存储在Text文本文件中，地理数据就失去了结构化。

3.2  关键技术及复杂性分析

3.2.1 十字链表作为图的存储结构

十字链表，可以通过任何一个节点便可以遍历到该顶点的所有边。这样有利于Dijkstra算法效率的提高，只是结构构造较复杂。

3.2.2 形象动态绘制最短路径

在背景图像的上面铺上一层玻璃面板，在玻璃面板上绘制最短路径。路径由领头图像和随后的脚印图像组成，动态生成，就像是一个人走在前面，后面留下一连串脚印，所形成的路径。玻璃面板的铺设与动态生成路径有较大的复杂性。如图3－2为XOY坐标系中两点直线图标的走向算法：   

3.2.3 采用XML格式存储系统数据

将系统数据结构化组织到XML文件中，并同时生成校验文件DTD文档。读取并解析XML文件有一定的复杂性。本系统数据组织化为Vertex.xml和Edge.xml。其结构如下：

Vertex的XML结构：

<ungraph>//根节点

<Vertex>//顶点节点

<RealVertex name="name" id="id">//实点节点

<Coordinate>//二维坐标节点

   <X>X</X> //元素X, x坐标值

   <Y>Y</Y> //元素Y,  y坐标值

   </Coordinate>

   </RealVertex>

<InflVertex name="name" id="id">//拐点节点

<Coordinate>

   <X>X</X> 

   <Y>Y</Y> 

   </Coordinate>

   </InflVertex>

</ungraph>

Edge的XML结构：

<ungraph>//根节点

<Edge id="id">//边节点

   <Start>start</Start> //元素start，边的头顶点名称

<Weight>weight</Weight> //元素weight，边的权值

   <PathNode>D</PathNode> //元素pathnode,边所经拐点名称

   <PathNode>E</PathNode>

   <End>end</End>  //元素end，边的尾顶点名称

   </Edge>

</ungraph>

Vertex.xml 文件存储真实地点的名称与坐标值即节点<RealVertex>,还存储虚拟拐点的id名称与坐标值即节点<InflVertex>。

Edge.xml 文件存储边的相关信息即节点<Edge>，包括首尾顶点、权值 、所途径拐点。

     与之相应的DTD文档为：Vertex.dtd 和 Edge.dtd，系统访问xml文件时要进行相应验证。

  第4章 十字链表与Dijkstra算法分析

 

4.1  十字链表描述与分析

以图4－1作为一无向图例子。

十字链表由顶点列表和边节点组成，顶点列表由顶点数组构成。顶点结构和边节点结构由图4－2中说明了此结构。

遍历一顶点的所有边，可由顶点列表中的该顶点遍历。

例如：遍历顶点D的所有边

从顶点列表中定位顶点D：

从顶点D 横向遍历即NextLink：<4 E>，<5 F>.

从顶点D 纵向遍历即UpLink：<3 2 C>,<3 1 B>,<3 0 A>.

故遍历顶点D的所有边为：E F C B A

4.2 DIJKSTRA算法描述与分析

4.2.1 算法思想描述

设G=(V,E)是一个赋权无向图，即对于图中的每一条边 e=(vi,vj)都赋予了一个权值wij,D(vj)表示点v1和vj之间的最短距离。在图G中指定一个顶点，确定为起点，不妨设V1为起点。

Dijkstra算法的基本思想是：

1.开始，先给v1标上红色标号，且D(v1)=0,其余各点D(vj)=+∞(j!=1),红点是不可改变D值的点，它所具有的D值即为该点至起始点的最短距离。

2.如果刚刚得到的红色标号的点是vi，将从该点进行扩展蓝点集，那么，对于所有这样的点{vj|(vi,vj)<E,而且vj的标号不是红色标号}，将其D(vj)修改为：min[D(vj),D(vi)+wij],并将vj标上蓝色标号，蓝点是具有至起始点临时最短距离的点。

3.从所有标有蓝色标号的顶点中求得D(vi)最小的顶点vi,并将其标上红色标号，转向第2步，如果此步没有发现蓝色标号的顶点，则停止。

 算法的部分核心代码为：

public void compute(){

       int index=0;

       graph.initStart(start);//初始化源点v1,且扩展到红点集中

       do{

       graph.expandBlues();//由lastRed进行蓝点集扩展

       index=graph.findMin();//从蓝点集找出最小权重顶点

       if(index==-1) {  break; }//没有发现蓝色标号的顶点，则停止。

       graph.expandRed(index);//扩展到红点集中

       }while(!graph.find(end));//true找到最短路径  

}

蓝点集的索引域为[0,blueIndex],blueIndex初始化为-1，表示空集。红点集的索引域为[redIndex,capacity),redIndex初始化为capacity,表示空集。中间的白色集为还没有遍历到的顶点集。颜色区域集与顶点列表通过一个映射关系连接，如图4－3 所示。

4.2.2 算法的复杂度分析

a．空间复杂度分析

本算法采用十字链表作为图的存储结构，故S(n)=O(c(m+n))。

其中c 表示节点的平均占用空间数，n表示顶点列表中顶点的个数，m表示边节点的个数。

b．时间复杂度分析

建立十字链表花费的时间为O(m+n)。核心运算花费的时间主要在findMin()操作上，每次findMin()操作平均查找n/4次。寻找终点平均寻找n/2次。总的花费为n/4×n/2,即n×n/8,所以F(n)=O(n*n)。

第5章 系统设计

5.1  系统界面设计

分为两大块：

上方为导航背景图，地点标签动态分布在其上。

下方为文本显示区，显示一些文本数据与测试数据。

上方背景图区隐藏一个玻璃面板区，用于在其上绘制路径。

5.2系统状态与流程设计

如图5－1所示，显示了本系统的整个流程。

5.3  微型数据库设计

着眼于本系统所需数据量较小，数据操作单调，不打算用像SQLServer和Oracle等大中型数据库。鉴于上述情况，本系统自制微型数据库MinDataBase，自定义查询接口Query ,以XML文件作为数据源，以XPath作为查询语言，借此提高I/O 效率和系统效率，如图5－2所示。

5.4  系统模型设计

本系统采用分层模型构造，如图5－3 所示。

第一层GUILayer层，用户界面显示层。其中地点标签由数据库中的地点数据连接生成。

第二层LogicControlLayer层，逻辑控制层，用于控制各组件的逻辑行为以及各组件之间的通信。

第三层KernelComputLayer 层，核心计算层。即Dijkstra引擎，所需初始数据由数据库连接。

第6章 系统实现

6.1  微型数据库实现

自定义微型数据库由3个类组成：

MinDataBase:数据库驱动核心程序，为外界程序提供操纵数据库的公共接口。Query:数据库查询接口，提供数据的一些查询，查询语言为XPath。Table：数据库中的抽象表，为数据源提供一个容器。其实现Query接口，提供对表的查询。

由于该数据库是为本应用程序量身订做的，数据库只提供了本系统所需的功能：查询，仅仅而已。

如图6－1所示为微型数据库包的组件图(已实现)。

6.2  Dijkstra引擎实现

图6－2 为Dijkstra引擎包的组件图(已实现)。

其中OptDijkstra组件为Dijkstra算法的核心组件，也是Dijkstra引擎的公共接口。CrossLinked为十字链表组件，也即图的存储结构。Vertex和Edge 组件为地理数据的封装类，描述地理数据的相关信息。

图6－3 为CrossLinked组件的类图(已实现)。

其中CrossVertex为十字链表的顶点类。CrossNode为十字链表的边节点类。RBWBlock为颜色区域集，与十字链表的顶点列表相映射。Color为颜色的枚举类，标志红，白，蓝三色。CrossLinked为十字链表的主类，其余为内部类。

另外TwoPointQueue是一个只能容纳2个元素的特殊队列，用于存储在界面中鼠标点击所获取的起始点与终点。

6.3  系统界面实现

图6－5为实现用户界面的组件图(已实现)。

DemoJFrame 为界面的主窗体，为其设置了玻璃窗格GlassPane和层叠窗格LayerPane。LayerPane 窗格布置背景图像、地点标签和测试文本组件。GlassPane 窗格安装了Dijkstra引擎，并接收来自于LayerPane的消息，该窗格用于绘制最短路径。

6.4  系统关键状态与流程实现

本系统状态可分为两种：源终点选择状态和绘制路径状态。

系统状态的切换由一个JButton按钮实现，其动作实现为：

public void actionPerformed(ActionEvent e) {  //进入到绘制路径状态

    if (e.getActionCommand().equals("Go")) {

abutton.setText("重新查询");  //切换按钮

abutton.setActionCommand("ReGo");

computeUint.start();  //启动引擎的准备工作

//获得源点

computeUint.setStart(contentpane.getlabQueue().take().getToolTipText());

//获得终点

computeUint.setEnd(contentpane.getlabQueue().take().getToolTipText());

computeUint.compute();  //启动引擎，计算最短路径

setVisible(true);  //显示玻璃面板,切换到绘制路径状态

drawable=true;  //许可绘制

paintPath();  //绘制最短路径           

}else {  //进入到获取源与终点状态

setVisible(false);  //使玻璃面板不可见，切换到选择状态

drawable=false;  //通知所有线程停止绘制 

 computeUint.close();  //关闭引擎

pointpath.clear();  //清除原先的路径

abutton.setText("导航执行");  //切换按钮

contentpane.clearText();  //清除文本框

abutton.setEnabled(false);  //没获得源与终点前，该按钮不可用

abutton.setActionCommand("Go");                                         

System.gc();  //建议垃圾清理          

  }   //end of IF

}

第7章 性能测试与分析

7.1  测试环境

 本系统的测试环境为NetBeans M6.0 .1中文版，JDK 为 1.6版。

 启用JUint 4.1进行测试，启用Profiles进行性能分析。

7.2  实例测试与性能分析(表格与曲线)

 图7－1 为运行时堆分析结果。  

图7－2 为对象生成数存亡分析结果。

Java 中的对象都在堆中分配，如果对象没有任何活的线程到达，则该对象将被JVM 作为垃圾自动回收。Java 中垃圾对象的回收只能由JVM 回收，不能由编程者主动回收，但可以建议JVM 进行垃圾回收。

图7－3为运行时线程数与装入类分析结果。

    线程数主要来自于绘制最短路径的过程中。由于是采用动态绘制最短路径的，所以用数个线程控制绘制路径的顺序与时间，以保证动态的观感。

图7－4 为系统运行的部分效果图。

第8章 结束语

本系统还有少许不足之处，有待改进。不足之处为：

1.动态绘制最短路径时出现的胡乱绘制，是由于数个线程的控制不利和信号量异常所造成的。还需加强对线程和信号量的学习。

2.将系统常量都封装在了常量接口中，而不是写相应的属性文件，可读性与灵活性下降。以后还得了解并应用属性文件。

3.本系统功能单调，仅应用Dijkstra 算法并绘制其结果最短路径。本人侧重于Dijkstra算法的研究与应用。

由于学习Java时间不长，系统的布局与代码规范给读者带来的困扰深表歉意。希望大家批评改正，共同学习进步。

致 谢 

感谢本寝室的同仁给我的帮助与支持，才得以找全参考资料。

感谢指导老师文军与汪涛的指点与支持，才顺利完成毕业论文。

感谢中国农行，才得以完成四年的学业。

感谢母校对我四年的培育与关怀，使我渐渐学会了做人、做事。

十分感谢家人对我的帮助与关怀，才顺利走完大学之路。

参考文献

[1]严蔚敏，吴伟民.数据结构(C 语言版).北京：清华大学出版社，

2005.10

[2][美]Sas Jacobs，Beginning XML with DOM and Ajax.许劲松 杨波

周斌 译. 北京：人民邮电出版社，2007.1

[3][美]Cay S.Horstmann，Gary Cornell，Core JAVA 2. 叶乃文等译.

北京：机械工业出版社，2006.5[电子图书]