（计算机应用技术专业论文）三防决策支持系统中空间索引结构与空间查询算法研究.pdf

河南大学硕士研究生学位论文第1 页 摘要 随着计算机技术的快速发展和社会需求的急剧增长，空间信息系统技术飞速 发展，其应用领域在不断扩大。面对海量的空间数据及其复杂的数据特征，如何 提高空间数据的查询效率成为当前空间信息系统应用领域研究的重要课题。针对 以上问题，本文以三防决策支持系统为背景，在系统空间索引结构以及系统空间 查询算法上做了如下工作和贡献： 1 ) 系统空间索引的改进。空间索引效率的好环往往从索引的存储效率、查询 效率和更新效率等几个方面来衡量。然而，很难设计一种空间索引结构同时使得 以上几个方面全部高效。本文根据系统的空间数据类型和功能特性，分析研究各 空间索引的效率，通过理论分析构造了一种适合三防决策支持系统的空间索引结 构基于h i l b e r t 编码的固定网格索引。实验证明，该索引结构提高了系统的 空间查询效率，优化了系统性能。 2 ) 系统空间索引的构建算法设计。系统空间索引结构的构建算法共分三步： 划分网格，把整幅地图根据实际情况划分为2 的n 次方个网格；建立网格索引表， 在存储索引信息时，根据网格的行号和列号产生该网格的h i l b e r t 编码作为该网 格的唯一标识；遍历所有的图形对象，取出其坐标信息，判断其所在的网格或与 之相交的网格，并将相应索引记录插入索引文件。 3 ) 最短路径查询算法( d i j k s t r a ) 的改进。d i j k s t r a 算法的主要缺点为存储结 构和待查询的下一个最近节点。本文主要从以下两方面改进：一是存储结构的改 进，采用j a v a 框架提供的集合类h a s h t a b l e 来存储数据，压缩了数据的存储空间； 二是执行效率的提高，每次只需更新中间结点所记录的后续点的距离即可，这样 可快速提高原算法的执行效率。系统当中只需要得到从起点到终点的最短路径， 通过减少循环执行次数，进一步加快空间查询操作的速度。 关键词：空间索引；网格索引；h i l b e r t 曲线；d i j k s t r a 算法； 第1 i 页河南大学硕士研究生学位论文 a b s t r a c t w i t hr a p i dd e v e l o p m e n to fc o m p u t e rt e c h n o l o g ya n de x p l o s i o no fs o c i a ln e e d s ， s p m i a li n f o r m a t i o ns y s t e mt e c h n o l o g yh a sd e v e l o p e dr a p i d l ya n di t sa p p l i c a t i o na r e ai s i n c r e a s i n g l ye x p a n d i n g t h ef a c eo fm a s s i v ea n dc o m p l e xs p a t i a ld a t am a k e si ta n i m p o r t a n tr e s e a r c ha r e af o rr e c e n ts p a t i a li n f o r m a t i o n - s y s t e mt oi m p r o v et h ee f f i c i e n c y o fq u e r y i n gi n f o r m a t i o n t h e r e f o r e ，s e t t i n gt h es u p p o r t i n gs y s t e mo ft h r e er e s i s t a n c e sa s b a c k g r o u n d , t h ep r e s e n tp a p e rh a ss e l e c t e dt h ei n d e xs t r u c t u r ea n dq u e r ya l g o r i t h m si n t h es p a c es y s t e ma st h es u b j e c ta n dm a d et h ef o l l o w i n gc o n t r i b u t i o n s ： 1 ) i m p r o v e m e n to fs p a t i a ls y s t e mi n d e x s p a t i a li n d e x i n ge f f i c i e n c yi s o f t e n e v a l u a t e db ys e v e r a la s p e c t sa st h ei n d e x ss t o r a g ee f f i c i e n c y , q u e r ye f f i c i e n c ya n d u p d a t ee f f i c i e n c y b u tt h et r u t hi st h a ti t sd i f f i c u l tt od e s i g nas p a t i a li n d e xs t r u c t u r ei n w h i c ha l lt h ea b o v ea s p e c t sc a i lb ef u l l yf u l f i l l e d b a s e ，do nt h et y p e so f s p a t i a ld a t aa n d i t sf u n c t i o n a lc h a r a c t e r i s t i c ，a sw e l la sa na n a l y s i s 。o f t h ee f f i c i e n c yo f e a c hs p a t i a li n d e x ， t h ep r e s e n tp a p e rh a st h e o r e t i c a l l yc o n s t r u c t e d as p a t i a li n d e xs t r u c t u r e ，ah i l b e r t c o d i n g b a s e df i x e dg r i di n d e x ，w h i c hw o u l db es u i t a b l ef o rt h es u p p o r t i n gs y s t e mo f t h r e er e s i s t a n c e s e x p e r i m e n t sh a v es h o w e dt h a tt h i si n d e xs t r u c t u r ec a l li m p r o v et h e e f f i c i e n c yo fs p a t i a lq u e r ys y s t e ma n do p t i m i z et h es y s t e mp e r f o r m a n c e 2 ) d e s i g no ft h ec o n s t r u c t i o no ft h es y s t e ms p a t i a li n d e xa l g o r i t h m t h ed e s i g no f t h ec o n s t r u c t i o no ft h es y s t e ms p a t i a li n d e xa l g o r i t h mh a sf o l l o w e dt h r e es t e p s f i r s t ， d i v i d et h eg r d a c c o r d i n gt ot h ea c t u a ls i t u a t i o n ，t h e = 画v h o l em a ph a sb e e nd i v i d e di n t o t w ot ot h e2n - t hp o w e r 酣d s s e c o n d ，e s t a b l i s ht h e 每r i di n d e xt a b l e i ns t o r i n gi n d e x i n f o r m a t i o n , t h eh i l b e r tc o d ew h i c hi sg e n e r a t e df r o mt h el i n en u m b e ra n dc o h m m n u m b e rw o u l db et a k e na st h ee x c l u s i v ei d e n t i f i c a t i o nf o rt h eg i r d t h i r d ，s c a na l l g r a p h i c so b j e c t s ，a n dr e m o v et h ec o o r d i n a t e si n f o r m a t i o n t h e nj u d g ei t sp r o p e rg r i d a n di t si n t e r s e c t i o ng r i d s ，a n df i n a l l yi n s e r tt h ec o r r e s p o n d i n gi n d e xi n t oi n d e xf i l e s 3 ) i m p r o v e m e n to ft h es h o r t e s tp a t hd i j k s t r aa l g o r i t h m t h em a i nd r a w b a c k so f d i j k s t r aa l g o r i t h ma r ei nt h ef i e l d so fs t o r a g es t r u c t u r ea n dt h en e x tn e a r e s tq u e r yn o d e t h ep r e s e n tp a p e rm a i n l ym a d ei m p r o v e m e n t sf r o mt h ef o l l o w i n gt w oa s p e c t s o n ei s t h ei m p r o v e m e n to ft h es t o r a g es t r u c t u r e t h eh a s h t a b l ei nt h ef r a m e w o r ko fj a v ah a s 河南大学硕士研究生学位论文第1 i i 页 b e e ne m p l o y e dt oc o m p r e s sd a t as t o r a g es p a c e t h eo t h e ri st h ei m p r o v e m e n to ft h e e x e c u t i v ee f f i c i e n c y o n l yt h a tu p d a t i n gt h er e c o r do ff o l l o w - u pp o i n t sd i s t a n c ei s r e q u i r e d i nt h i sw a y , t h ee x e c u t i v ee f f i c i e n c yc a l lb er a p i d l yi m p r o v e d s y s t e mo n l y n e e d st h es h o r t e s td i s t a n c eb e t w e e nt h eb e g i n n i n ga n dt h ee n d i n t h i sw a yt h ec y c l i n g e x e c u t i v et i m e sc a nb er e d u c e d ，t h e r e f o r et h es p e e do fs p a t i a lq u e r yc a nb ef u r t h e r a c c e l e r a t e d k e y w o r d s ：s p a t i a li n d e x ；g r i di n d e x ；h i l b e r tc u r v e ；d i j k s t r aa l g o r i t h m ； 关于学位论文独立完成和内容创新的声明 硼删说篡笺鲻篮淼l 。 磷满箩；? ，藿彩 学位申请凡，学位论克作者釜名：c 二f 碰蹩： 一 懋霸黼携答， 饕，关于学位论文著作权使用授权书；霪 甏参彬鬣：盛糍蔑滚囊。毒多i 毳赢矽爹 学位获得者( 学位论文作者) 釜名：二寻二址 2 1 ) k 年 ，兔| 5 b 学位论文指导教师鍪名： 1 1 0l o 年兔l n 河南大学硕士研究生学位论文第l 页 1 1 课题背景与意义 第1 章绪论 随着计算机技术和信息技术的迅速发展，空间信息系统技术将在国民经济建 设中发挥更加重要、更加积极的作用。空间信息系统的诞生改变了传统的信息处 理方式，使信息处理由数值领域步入空间领域。空间信息系统在自然灾害预测和 灾情监控，自然资源的调查、开发与利用，区域和城市的规划与管理，环境监测 与治理等诸多方面都有着十分广泛的应用“吲。 空间信息系统是空间数据库发展的主体，在空间信息系统中检索和查询是使 用频率最高的功能之一。在实际应用当中，用户提出的很多问题都需要借助于暴。， 统的查询操作才能给予解决。查询操作速度的快慢直接影响用户体验，可以说它 是系统面向用户的一个窗口h 一1 。近几年来，随着空间数据的不断增多，广大用户 对空间查询提出了越来越高的要求，一些简单的查询已经远远不能满足用户的需 求。目前，如何提高空间查询效率已成为广大用户关心的一个重要问题，为了解 决该问题，很多专家学者都在致力于这方面的研究悖1 们。 本课题来源于河南大学横向联合研发的三防决策支持系统，该系统能够快速 准确地对分布于各地域的设备等情况进行直观一致的显示，提供对地图进行放大、 缩小、整图显示、漫游、测距、信息查询，以及信息的动态显示、目标定位及查 询等操作，还可借助空间信息系统的空间分析功能实现基于防洪救灾信息的一些 重要的分析，进而大大的提高系统的实用性。 数据查询速度的快慢直接影响到系统的性能和效率，因此如何提高系统查询 效率是该系统必须解决的关键问题。空间索引性能的好坏直接影响到空间查询效 率的高低，进而影响到三防决策支持系统的功能与效率，它是三防决策支持系统 的关键技术之一3 1 。因此本课题的研究目的之一就是旨在找到适合本系统的一种 空间索引结构，从而更大程度的提高系统的空间查询效率。 由于最短路径问题常常用于各种应急决策系统，这些系统一般对时间的要求 比较高，往往要求在l - - 3 s 时间内响应客户，所以最短路径查询问题的实现应该是 高效的。在最短路径问题当中，不管是距离最短、费用最低还是时间最快，它们 第2 页河南大学硕士研究生学位论文 都是以最短路径算法为基础。目前，大多数系统解决最短路径问题都把d i j k s t r a 算 法作为理论基础。本文涉及到的是一个三防决策支持系统，为了提高系统空间查 询速度，算法要尽可能的高效，尽可能少占内存，也就是要尽可能降低算法的空 间复杂度和时间复杂度 埔1 。因此，必须结合本系统的特点对此算法进行改进，使 其能满足系统的要求。 1 2 国内外研究现状 近年来，空间查询己逐步成为空间数据技术领域的一个研究热点。在国外， 有许多大学、研究机构、公司对空间数据库技术进行研究。例如，当前市场中的 m a p i n f o ，a r c g i s 等实用g i s 系统；o r a c l e ，s y b a s e ，i n f o r m i x 等一些主流的关系 型数据库系统都开始提供空间数据的处理功能n 吼删。 在空间索引技术的应用方面，目前常用的空间索引结构主要是网格、四叉树 与r 树这三类空间索引结构幢。上述常用三类空间索引技术各有所长，但网格类 空间索引以其简单、高效、易于实现的优势，得到了十分广泛的应用。在应用方 面比较成功的是：达梦公司的d m 3 利用网格索引技术实现了地图的空间检索系统。 自1 9 8 4 年j n i e v e r g e k 、h h i n t e r b e r g e r 和k c s e v c i k 提出网格空间索引技术以 后，很多专家学者对此做了大量研究乜羽。一些改进的网格索引结构相继被提出，比 如固定网格索引1 2 3 、层次网格索引1 等等，这些索引结构都是根据网格索引的基本 思想，在原有的基础上对网格索引进行了一定的改进，使其性能得到了很大的提 高。但是在实际应用中，不同系统的空间数据类型差别很大其功能特性也各有特 色，因此要根据系统的特点选择合适的空间索引结构。 近些年来，空间信息系统在交通、公安、土地资源管理、救灾等方面都得到 了广泛且深入的应用，这些应用领域中的空间信息系统经常涉及最短路径搜索问 题拉引。国内外大量专家学者都曾对最短路径问题进行深入的研究和探讨，目前基于 空间信息系统的最短路径搜索算法研究很多，后人在此算法的基础上进行了大量 的优化，从核心算法和数据存储结构两方面进行了改进啪朋1 。由于这些算法主要源 于计算机科学及运筹学领域，在算法的设计过程中只考虑了抽象网络的拓扑特性， 力求通过各种新型的计算机数据结构和运筹学方法，从理论上减少算法的时间复 杂度，而忽略了具体的网络可能具有的空间分布特性。根据经验，两点间的路径 河南大学硕士研究生学位论文第3 页 不仅可以表示长度，还可以表示花费时间以及费用开销等各种属性，从通用性和 完备性的上来说，d i j k s t r a 算法是非常优秀的，然而在实际运用中针对某些特殊 的问题，无疑应该有更加高效的算法。因此，本文针对三防决策支持系统在应用 中的具体情况对d i j k s m a 算法进行改进是有必要的。 1 3 论文的主要内容及组织结构 本文着重研究了三防决策支持系统的空间索引结构和空间查询算法。空间索 引性能的好坏直接影响到空间查询效率的高低，进而影响到三防决策支持系统的 功能与效率。本文在分析系统的空间数据类型和功能特性的基础上比较各空间索 引的优缺点，找到了一个适合本系统的空间索引结构。空间索引结构仅仅是影响 系统整体性能的一个方面，良好的空间查询算法也对系统整体性能的提高起着关 键作用。最短路径查询是三防决策支持系统的一个核心任务，本文以d i j k s t r a 算 法思想为基础，对其存储结构和算法本身进行了改进，为决策层提供可靠、准确 的信息服务。本文内容组织如下： 第一章，主要介绍了论文研究的背景和意义、国内外对于空间索引及其关键 技术、最短路径查询的研究现状以及本文的研究内容。 第二章，介绍本文研究内容的课题背景三防决策支持系统，介绍了系统 的总体框架、逻辑结构以及体系结构。 第三章，讨论了本文应用于三防决策支持系统的相关技术。首先介绍空间数 据的分类，主要有栅格数据和空间矢量数据。其次讨论了现有的空间索引技术， 并对这些技术进行了分析；最后介绍空间查询的有关知识。 第四章，通过研究分析各空间索引的效率，得出一种适合三防决策支持系统 的空间索引结构，并给出该空间索引结构的构建算法设计。首先，分析了该系统 的空间数据类型和功能特性，得出影响本系统索引结构效率的因素主要是查询效 率，系统的空间数据类型主要是点数据和线数据；然后主要基于点数据和线数据 从查询效率方面来分析研究各空间索引的性能，通过理论分析得出一种适合三防 决策支持系统的空间索引结构基于h i i b e r t 编码的固定网格索引结构，实验 证明该空间索引结构提高了系统的空间查询效率，优化了系统性能；最后给出了 该系统空间索引结构的构建算法设计。 第五章，分析研究系统中空间查询的核心算法，其中包括点查询和区域查询、 第4 页河南大学硕士研究生学位论文 最短路径查询，并对传统的d i j k s t r a 算法进行改进。分析了传统的d i j k s t r a 算 法的主要缺点为存储结构和待查询的下一个最近节点，并针对以上两个缺点改进 传统的d i j k s t r a 算法。最后，通过时分析时间复杂度和空间复杂度来对改进后的 算法与原算法进行比较，实验表明改进后的算法较原算法在性能上有明显提高。 结束语，对整篇论文的工作进行了总结，并对下一步的工作进行展望。 河南大学硕士研究生学位论文第5 页 2 1 项目背景 第2 章三防决策支持系统 近年来，国外发达国家的防汛信息服务系统的研究和应用水平都比较高，如 美国、日本等都建立了较完备的防汛决策支持系统。国内，在国家防汛指挥系统 总体设计框架下，各级三防部门在决策支持系统的建设和管理方面作了大量的基 础性工作，初步建成了水情信息采集报汛网络，制定了各堤垸、乡镇以及防洪、 防风和防涝预案等，在防汛工作中发挥了重要作用。但是，由于缺少调度及工情 与灾情分析的软件，尚未形成能为三防指挥和各项防汛工作提供决策支持的系统， 并在水利信息化和三防信息系统建设方面缺乏统一规划、统一管理，在标准化和 规范化方面也做得很不够。目前，洪水预报大部分是人工查阅有关图表来完成， 经验成分居多，而且自动化程度低，完成_ 次预报大约需要2 至3 小时。根据现 有报汛站的信息和传统的手工操作方法进行预报，其精度和现时性己不能满足三 防指挥工作的需要，对洪水拦蓄、分流演算更为困难。因此，急需建立现代化的 通信、计算机网络系统，以便迅速、全面地收集和处理水情、工情、灾情信息， 并用计算机作出精度高，预见期长的水情预报，并辅助三防科学决策。为此，我 们河南大学研发了三防决策支持系统，实现因地制宜，整体推进，有效提高信息 采集和传输处理的实时性和准确性，增长三防灾害预测预见期，加强防灾救灾的 科学性和有效性。 2 2 系统结构 2 2 1 系统总体框架 系统的总体框架如图2 1 所示： 第6 页河南大学硕士研究生学位论文 三防孚动办公 i 玩场三防孬处薯 2 三i 疗信息蠢询 ，移动柏挥调度 通信调度和管震平台 ，。叛撂和业务应用艨务 嚣毫务 i 防汛防风信毒蠢询 2 防摹信息蠹询 ，。信毫发布内摩捌件 三防簿蔑希 ，系毵譬蕞雏妒 誊篝度 1 调度方囊摸投仿真 2 调度方囊发布 ，三防插拜百搅调度 ，蟹怎锋应急插褥 决蘸套商 t 信怠愤羲汇羹 2 蓑囊方囊汇曩 ，抢i 金拨灾方羹纠戈 调度方羹生成 ，套羹套谈警震 。蓑援赛麓敦镭 、_ _ 一， 爱缓成果、 调度方羹、模报 重秉、抡蹬敏灾 当蠢、灾害评链 防汛葑 土套 t 汛繁茂蜻塞键 2 。洪水颡擎分析计霉 ，。撩窆防洪调度穷羹 。投定抡隆较灾方囊 ，洪水蒗选淹没仿真横投 6 防洪悫沓分析 旱情譬薯 l 。抗罩僚惠蠢询 2 晕蕾童溺 3 晕餐娩计分析 抗卑措施舅定 睢笙魂蓉统 1 ，重要水嗣工翟皇撬 2 ，移动霜缘皇搅 赛对信毫秉囊蓉笺 l 。气基信惠跃取与采鬃 2 。水蕾信惠采鬃 ，两蕾馇惠菜鬟 度慵倍患蔹取董采囊 ，罩簟信患皇溯 6 水震信息泉曩 7 。工麓信怠暮鬟 1 灾繁信息互澜 圈攥信惠盘视 = - 塞璧丝查苎篓二 气象、，i c 羹、 再蕾，j 随慵。摹、 水、工簟、灾簟、 7 三防基碹敦播 一， 工程、凋站、防讯 确资、社会照 j k 地理 空闷、鼍感彩氢萋撮 曩基、三防爱羹。历史 气“瓷氛| 懿氓i i a 奴 现场囊攘工灾i i 卑簟 图2 1 三防决策支持系统总体框架 奠夏售毒手台 l 。二三镕霸霹卅伟 2 。炮圈瑟奉援伟功麓 ，囊筑警曩镶妒功麓 信息巫示分析功麓 ，变闷分新譬嚣劝麓 6 工程防洪模报仿真 7 - e 基_ c l s 功瑟 河南大学硕士研究生学位论文第7 页 2 2 2 系统逻辑结构 系统的逻辑结构所图2 - 2 所示。 防汛掰魏监务子系统 旱情管理子系统 互防会商予系统 指挥调度子系统 2 2 3 软件体系结构 图2 2 决策支持系统逻辑结构 本系统将采用b a s + c s 的混合结构。如图2 - 3 所示，b a s 体系结构包括 浏览层、服务器组件层和资源管理层。在三防决策支持系统业务应用子系统的建 设中，采用三层b a s 技术体系结构，可以很好地提高系统的稳定性、可扩展性 和可维护性，方便系统扩容和新业务开发，提高服务质量。在此体系结构的基础 上，对整个软件体系进行多层划分，整个系统可划分为系统软件层、中间件层、 支撑软件层和应用框架层、应用系统层。 在网络环境下对地理数据的操作和分析是w e b g i s 今后发展的重要方向之 一。但w e b 环境下开发和运行三防指挥系统的主要瓶颈在于对地理数据的存储 和计算。目前，桌面g i s 中可以提供对数据非常复杂的操作，包括对图形数据( 点、 线、面) 和属性数据的增加、删除、修改等基本操作。另外，通过g i s 提供的空 间分析功能，用户可以从已知的地理数据中得出隐含的重要结论，这对于许多 第8 页河南大学硕士研究生学位论文 应用领域是至关重要的。但是，目前在网络环境下对数据的这些操作 图2 - 3b s 的三层的软件体系结构 还无法实现。上述w e b g i s 产品主要还是对于数据的查询、浏览，无一能较好地解 决空间数据的分析问题。而在三防决策支持系统中，有大量的统计、分析都是基 于空间分析的，如洪水预警和分析计算、抢险救灾等就需要大量的空间分析。对 于洪水模拟仿真系统等基于三维地理空间数据的系统，其计算需要访问大量的数 据，所以可以考虑采用直接访问本地存储的数据文件方式避免网络上的大数据量 访问。另一方面，三防决策支持系统中的许多分析是在反复更改配置参数反复进 行空间分析之后才得到成果数据的，这些中间的分析结果都只需要临时存储，而 不入库，更不可能存储在远程的数据库服务器中。所以在现有条件下，三防决策 支持系统建设中有必要借助基于c s 架构的系统高效解决计算、分析、及显示等 方面的问题。 2 3 系统功能 三防决策支持系统目的是为防洪、防风、防旱提供工程运用与抢险维护、防 汛物资调度与分配、洪水与水库的指挥调度等决策支持，并对三防信息进行处理， 进行汛情分析、洪水分析计算、调度、旱情、灾情等分析计算，提供历史范例和 经验，辅助决策者制订三防方案，同时对方案后果进行模拟仿真和评价，它集中 地体现为对三防指挥决策过程的支持。 三防决策支持系统主要完成如下功能： 1 信息接收、处理入库 河南大学硕士研究生学位论文第9 页 在三防工作中，常见的信息主要包括气象、水情、工情、旱情、灾情、险情、 社会经济、地理等信息。为了更好的完成三防决策支持系统的各种功能，第一要 务就是要把这些信息通过人工或自动接收、处理后进入各有关数据库或形成各类 报表。 2 暴雨预报 暴雨预报处于防洪决策的前期，它的主要任务是预测预报未来某个时期内暴 雨的时空分布，为洪水分析计算和防洪决策提供依据或参考。 3 洪水分析计算 洪水分析计算的任务是在生成暴雨预报产品后或发生降雨后，根据实际测量 或预报的降雨、水位、流量、防洪工程运用等信息作出东江、寒溪河、石马河等 重点站( 断面) 的洪水过程、特征预报，为防洪调度提供决策支持。 4 热带气旋及台风预报预警 热带气旋及台风登陆前的运动和变化要及时发报，并通过系统仿真模拟出其 将要行进的路径，以尽早通知台风途径地区，及早采取积极有效的防范措施。 5 防洪工程调度 防洪工程调度的主要任务是依据雨水工灾情实况和暴雨、洪水分析计算，设 计切实可行的水库与河道等联动防洪调度方案，以保证防洪工程和防洪地区的安 全，将灾害损失减少到最低限度。 6 灾情统计、分析 对实际或已发生的灾情进行统计分析或核实，并进行定性或定量方面的评估， 报送有关部门。 7 旱情分析预测 综合分析各类干旱指标，分析预测旱情，对旱灾和抗旱效益作出评估，提出 抗旱对策，协助组织抗旱人力、物资和资金等。 8 险情、灾情等紧急事务处理 险情、灾情等紧急事务外理主要是对突发的洪水、工程险情、灾情进行处理， 包括制定各种对策，批复请示，组织人员、物力实施方案等。 9 三防工程管理、组织管理以及日常事务处理 主要进行防汛抗旱的有关文档管理、工程管理、组织管理、物资资金管理及 三防决策实施、新闻发布等，处理各类日常事务。 第1 0 页河南大学硕士研究生学位论文 三防综合数据库、三防指挥调度业务系统、三防办公和信息服务系统、下属 单位的三防业务管理系统等4 个子系统组成了三防决策支持系统。 三防指挥调度业务系统又包括防汛防风业务、旱情管理、决策会商和指挥调 度等4 个子系统。三防办公和信息服务系统包括三防移动办公、信息服务、兰防 办公管理等3 个子系统。所以决策支持系统系统建设内容包括： 1 ) 三防综合数据库； 2 ) 三防指挥调度业务系统，以地理信息基础平台为基础平台。它包括以 下4 个子系统： a ) 防汛防风业务子系统 b ) 旱情管理子系统 c ) 决策会商子系统 d ) 指挥调度子系统 3 ) 三防办公和信息服务系统，包括以下3 个子系统： a ) 三防移动办公子系统 b ) 信息服务子系统 c ) 三防办公管理系统 4 ) 下属单位的三防业务管理子系统。包括： a ) 数据库管理与维护模块 b ) 三防业务管理模块 河南大学硕士研究生学位论文第1 1 页 第3 章三防决策支持系统相关技术概述 3 1 空间数据结构 一般来说，空间数据是指与二维、三维或更高维空间的空间坐标及空间范围 相关的数据，常用于表示空间物体的位置、形状、大小和分布特征等方面的信息。 空间数据除了具有一般数据所具有的可靠性、选择性、详细性等特征之外，还具 有一些自己独有的性质鼢1 ： ( 1 ) 较为复杂的空间对象：通常情况下，一个空间对象可以由一个点甚至是由 几千个多边形组成，并且在空间中可以任意分布。如果用一个关系表，以定长长 元组的形式来存储这类对象的集合通常是不大现实的。相对来说，一些空间操作 要比标准的关系数据库操作复杂的多。 ( 2 ) 空间数据海量化：一个城市空间信息系统的数据量往往是海量的，通常达 到几十g b ，甚至达到几百g b 。这样的数据量在其它数据库中是很少见的。 ( 3 ) 空间数据动态性：由于空间数据在随着人们的需求不断增多，删除和插入 是以更新操作交叉存储的，对象频繁的删除、插入、更新、查询等操作要求空间 数据结构要有健壮性。 ( 4 ) 不标准的空间算法：在过去的几年里一些空间数据算法相继被提出，但是 经过这几年的发展，仍然没有一个标准的算法。没有一个标准化的基础算子集合 导致算子严重依赖于特定空间数据库的应用程序。 ( 5 ) 空间运算符是不闭合的：在两个空间实体相交的情况下，其返回结果并不 是唯一的，点集、线集、面集都有可能是返回的结果。 ( 6 ) 较为昂贵的计算代价：根据所采用的空间算子不同，空间数据的计算代价 会随之变化，但即便是这样，仍然要比标准的关系运算代价高。 3 1 1 栅格数据 栅格结构是一种简单直观的空间数据结构，又叫网格结构( g r i dc e l l ) 或象元结 构( p i x e l ) ，通常是将地图图幅划分为大小规则的网格阵列，其中每个网格就是一个 象元或象素，每一个象元采用( x ，y ) 坐标标识来表示该象素的一些属性数据或量 值，或者只是包含指向其属性记录的指针嘲1 。栅格结构表示的是一些离散的、不连 第1 2 页河南大学硕士研究生学位论文 续的数据。由此看来，栅格结构的一个显著特点便是属性明显，定位隐含。如图 3 - 1 所示的线、面数据的栅格结构表示，其中口表示一个面实体，b 表示一个线实 体。在栅格结构中，一个点( 如水库) 由单个象元表达，一条线( 如河流) 由具 有相同取值的一组线状象元表达，一个面状地物( 如旱地) 由若干行和列组成的 一片具有相同取值的像元表达。 b h b aa aa a h a a b牡 a b a 秘 a a勰 b 襁谚农尔 图3 - 1 线、面数据的栅格结构表示 对于空间数据而言，栅格数据通常包括各种对地观测得到的图像数据，如遥 感影像数据、航空数据、各种摄影的图像数据，以及经过网格化的一些地图图像 数据。遥感影像数据就是一个典型的栅格结构，每个象元的数字表示影像的灰度 等级。从数据类型上看，栅格数据通常被分为：灰度图、二值图、2 5 6 色索引和分 类图等等。常用的数据格式有b m p 、p c x 、g i f 、孤即、j p e g 等。栅格结构 数据的获取一般主要采用以下几种方法：目读法、扫描数字化方法、数字化跟踪 仪或数字化地图方法。栅格数据的编码方法通常有以下几种方法：压缩编码，链 码( 弗里曼链码) 比较适合存储图形数据；直接栅格编码，通常是把栅格数据当 作一个数据矩阵，按照逐行或者是逐列的形式一个一个记录代码；游程长度编码 是通过记录行或列上相邻若干属性相同点的代码来实现；块码是游程长度编码扩 展到二维的情况，一般采用方形区域为记录单元；四叉树编码能够提高图形操作 效率，其分辨率是可以调整变化的，具有可变性，它是最有效的栅格数据压缩编 码方法之一。栅格数据的优点为数据结构简单，容易为计算机存储、操作和显示， 因此这种结构容易实现，便于空间分析和地表模拟，现势性较强，给地理空间数 河南大学硕士研究生学位论文第1 3 页 据处理带来了极大的方便，受到普遍欢迎，许多系统都部分和全部采取了栅格结 构；其缺点为数据量大，投影转换比较复杂。 3 1 2 空间矢量数据 三防决策支持系统中另一种最常见的空间数据为矢量数据。矢量数据结构是 是利用欧几里得几何学中的点、线、面及其组合体来表示地理实体空间分布 的一种数据组织方式。它是通过记录空间对象坐标的方式来表示点、线、面等地 理对象的几何位置1 。点通常用一对空间坐标( x ，y ) 来表示。点对象是空间上不 可再分的地理实体，它可以是具体的，也可以是抽象的，如雨量站、测站、文本 位置点等。为了方便存储和管理，存储在数据库中的点数据可以基于直接测量或 者通过转换测量得到的数据而产生出来。线目标是由一串坐标对组成，通常线目 标主要用来表示线状地物，如河流、水利工程等。面目标是由线形成的闭合多边 形，是带有位置和边界的空间范围。 矢量数据结构这种数据组织方式能更好地表达地理实体的空间分布特征， 数据精度高，数据存储的冗余度低，便于进行地理实体的网络分析，但对于 多层空间数据的叠合分析比较困难。由此看来，矢量数据的主要特点是定位明 显和属性隐含，允许最复杂的数据以最小的数据冗余进行存储，数据精度高，所 占空间小，是一种高效的空间数据结构。 3 2 空间索引结构 空间数据通常是基于数据对象的空间位置和属性的值来进行获取和更新，对 空间数据的查询与获取经常需要执行一些快速的几何搜索运算，要支持这些查询 操作必须引进索引机制。由于空间数据的特殊性，传统的索引机制在这里是不适 用的。因此，需要为空间数据库引进专门的索引机制即空间索引。所谓的空间索 引是指存储空间数据时根据空间对象的位置和形状或空间对象之间的某种空间关 系，按一定的顺序排列的一种数据结构，它一般包括外接矩形、指向地理对象的 指针以及地理对象的标识等三部分。通过空间索引的筛选，可以排除大量与特定 空间操作无关的空间对象，从而提高空间查询操作的速度协。， 空间索引作为一种辅助性的空间数据结构，它介于空间对象和空间操作算法 之间，目的是为了在空间数据库中准确快速的查找到所选中的空间对象。空间索 第1 4 页河南大学硕士研究生学位论文 引是快速、高效地查询、检索和显示空间数据的重要指标，其性能的好坏直接影 响到空间信息系统的功能与效率，它是空间数据库和空间信息系统的一项关键技 术，直都是广大专家学者研究的热点。为了提高索引效率，目前人们在索引领 域做了很多工作，提出了许多种较好的索引方法，其中比较有代表性的索引方法 包括网格及其改进型索引m 、r 树及其改进型索引m 羽、四叉树索引啪，等。每一 种索引算法都有其自身的特点，适用于不同的应用场合。下面分别将按空间分割 方法一一基于区域划分的索引结构和基于对象划分的索引结构来分类介绍一些典 型的空间索引方法，并分析其各自的优势和不足。 3 2 1 基于规则网格的索引结构 基于规则网格分割方法的代表索引结构是固定网格索引，其基本思想是用横 竖线将研究区域划分为大小相等或不等的网格，通常研究区域被划分成m 行n 列， 从而得到m x n 个小矩形网格区域，其中每个网格区域代表一个索引项，每个索 引项中记录了所有完全或部分落在该矩形区域内的几何实体的标识号，表示每一 个网格所包含的地理对象怕7 侧。如图3 - 2 所示，图中有两个空间对象a 和b ，其中 对象a 是一个点对象，对象b 是一个线对象，每一个小矩形块表示了一个空间索 引项，箭头后面的矩形框表示该索引项所对应的动态内存块，每个索引块都记录 了全部或部分落在该矩形区域内的空间实体的标识，记录每个网格所包含的空间 对象，当用户进行空间查询时，首先计算出用户查询的空间对象所在的网格，然 后再从该网格中快速查询所选中的空间对象。 ， a | | 白| | f 图3 - 2 网格索引示意图 河南大学硕士研究生学位论文第1 5 页 固定网格空间索引的优点显而易见： 1 、索引的速度比较快。从上面可以看出，固定网格空间索引的索引空间划分 是比较规则的，在查询过程中根据标识号可以直接定位到相应的空间对象上。 2 、查询方式不唯一。在查询操作中，查询区域可以是任意的_ 个点、一条线 或者是一个任意形状的区域。 3 、网格大小可以调整。可以通过不断调整m 和的值来改变网格的大小， 从而达到提高索引效率的目的。 4 、索引的操作算法简单。网格空间索引的相关操作算法便于计算机编程实现， 固定网格索引除了上述优点之外，还有一个缺点就是固定网格索引是一种多 对多的索引，这样存储数据时往往会导致冗余。 3 2 2 基于对象的索引结构 g u t t m a n 于1 9 8 4 年提出了r 树的概念，目前r 树已被广泛应用1 。在基于对 象的索引结构中r 树是最具有代表性的，通常用空间对象的最d , j l - 接矩形( m b r ) 来近似表达空间对象。r 树是一个高度平衡树，通常是由根结点、叶子结点和非叶 子结点组成。其结点结构可描述如下： 叶子结点：【c d 明订，l e v e l ，( ，m b r l ) ，( 研2 ，m b r ) ，。( o l u ，m b r m ) j 中间结点：印u n t ，l e v e l ，( c 只，m b r l ) ，( c b ，m b r ) ，( c p m ，m b r u ) j 其中，( c e , ，m b r 。) 代表的是索引项，c e , 是一个指针，指向子树的根结点，m b r ，表 示其子树索引空间，为包围其子树根结点中用到的索引项或数据项个数， ( o l ，m b r ，) 代表的数据项，优，为空间对象的标识，m b r 。是该对象在k 维空间中 的最小包围矩形。l e v e l 0 表示该结点在树中的层数。因为整数和指针不但可 以相互转换，而且所占存储空间也相同，所以r 树的中间结点和叶子结点在结构 上是一样的。由此可以归纳出r 树具有以下几个特征( m 为结点包含数据项的最 小数目) ： ( 1 ) 每个中间结点( 除根结点之外) 均至少有m 个子树，至多有m 个子树。 ( 2 ) 每个叶子结点均有m 至m 个数据项。 ( 3 ) 如果根结点不是叶子结点，那么它至少有两棵子树。 ( 4 ) 所有的结点都需要同样的存储空间，通常为一个磁盘页。 第1 6 页河南大学硕士研究生学位论文 ( 5 ) 是一棵高度平衡树，其所有的叶子结点都是在同一层。 如图3 3 给出了r 树的平面示意图和结构示意图。从图中可以很容易看出，a 和b 这两个结点的最小包围矩形是重叠的。在r 树中，其兄弟结点对应的空间区域可 以重叠，因而插入和删除操作比较容易。但正是由于区域之间存在重叠的可能性， 从而导致了查询路径的不唯一。如果查询路径不唯一，r 树的查询效率会大大降低， 在最坏情况下，其时间复杂度可能会由对树搜索退化成线性搜索。 | 臼图 ! - ai b ( a ) 平面图 曰 ( b ) r 树索引表示图 图3 - 3r 树索引示例图 近二十多年来，许多国内外专家对r 树做了大量的研究，并取得了大量的研 究成果。在r 树的基础上衍生出了许多变种，比较典型的有l h 树，r 树，压缩r 树等。 3 2 3 四叉树索引 四叉树是建立在对区域循环分解的原则之上的一种索引机制，它的基本思想 河南大学硕士研究生学位论文第1 7 页 是将已知范围的空间划分成四个相等的子空间，根据实际需要还可以将每个或其 中几个子空间继续一分为四划分下去。这祥就形成了一个基于四叉树的空间划分。 四叉树有一个根节点，其中的每个中间节点要么没有孩子，要么有且仅有四个孩 图3 - 4 四叉树及其对应的子划分 子。图3 4 给出了四叉树的一个示例及相应的划分。四叉树索引有点四叉树索引和 面四叉树索引。在一个四叉树中，每一个内结点都对应于二维空间中的一个正方 形区域，或者是七维空间上的k 维立方体。 3 3 空间查询 空间查询是空间数据库的一项重要操作之一，所谓的空间查询就是按照特定 的条件对空间对象的空间数据和属性数据进行查询，从而形成一个满足用户需求 的一个数据集合。如查找某一区域相交的所有空间目标等等，很多应用领域中， 空间查询操作无处不在，数据查询速度的快慢直接影响到系统的性能和效率，是 这些应用系统成功的关键所在。 一般的空间数据库中查询操作主要包括精确匹配查询、点查询、区域查询、 最短路径查询、方位查询和空间连接等，与一般关系数据库相比，空间数据库在 查询处理方面的还具有以下特点嘧卿： ( 1 ) 空间数据库没有标准的空间代数和空间查询语言，空间算子也非常依赖 于应用程序范围，因此对每种具体空间查询的设计与处理