基于图模犁和拓扑约束的管网数据一致性检测

基于图模犁和拓扑约束的管网数据一致性检测 基于图模犁和拓扑约束的管网数据一致性 检测 2006年2月 第4卷第1期 地理空间信息 GE0SPATIALINFORMATION Feb.,2006 Vo1.4,No.1 中图分类号:P208文献标识码:B文章编号:1672—4623(2006)01—0052—03 基于图模和拓扑约束的管网数据一致性检测 韦人玮,吴小芳,杜清运 (1,武汉大学资源与环境科学学院,湖北武汉430079;2.地理信息系统教育部重点实验室,湖北武汉430079) 摘要:正确可靠的数据是GIS系统的核心.针对管网数据的复杂性,提出利用圈数据模型描述管网拓扑关系,并使用拓 扑约束方法对管网数据一致性进行检测.以确保数据的正确性.该方法吸收了基于连接规则以厦基于拓扑关系约束的方法 的优点,能够更好的描述管网系统的整体结构并对其进行拓扑约束,使得一致性检测更加全面. 关键词:供水管网GIS;圈论;拓扑约束 ConsistencyCheckingofPipelineNetworkBasedon GraphModelandTopologicalConstraint WEIRenwei',WUXiaofang..,DUQingyun'' (1.SchoolofResourceandEnvironmentalScience,WuhanUniversity,Wuhan430079,Chin a; 2.KeyLaboratoryofGIS,MinistryofEducation,WuhanUniversity,Wuhan430079,C]fina) Abstract:ThecorrectandreliabledataiSthecoreofGIS.Inthispaper.thegraphdatamodeliSin troducedto representthetopologicalrelationofpipelinenetworkwithrespecttothecomplexityofpipelin enetworkdata, andthetopologicalconstraintconditioniSusedtocheckthetopologicalrelationinordertokee pthedataCOt. rect.Themethodcombinestheadvantagesofboththeconnectivityrulesmethodandthetopol ogicalconstraint condition,andisabletorepresenttheintegralstructureofpipelinenetworksysteminmoredet ailedway,and detecttheerrorsmorecomprehensively. Keywords:pipelinenetworkGIS;graphtheory;topologicalconstraint 随着城市规模的扩大,传统的档案管理模式已经 不能适应供水管网信息的管理需求,供水管网GIS逐 步成为主要的供水管网信息管理手段.如今基础地理 信息系统软件已经比较成熟而且由于组件技术的广泛 使得二次开发更加便捷,因此在供水管网GIS 采用, 的建设过程中,数据采集并确保数据的正确性成为工 作的重点. 供水管网数据主要有图形数据和属性数据,其中 图形数据不仅采集比较困难,而且容易出现错误.采 集的数据必须经过一致性检测才能投入使用.因此如 何对数据进行有效的检验,确保数据的正确性至关重 要.常见的图形数据一致性检验方法有两种:一种方 法是检测各种图形要素之间的关系是否符合连接规 则;另外一种是建立拓扑关系,并检测拓扑关系是否 正确.所谓连接规则是指实际管网中的管件之间以及 管件与管线之间的连接关系,例如_一通接头必须和三 段管线连接等等.该方法通常运用于专门的数据采集 模块,在图形的矢量化阶段控制数据的质量.在ES— RI公司的Arc/Info系列软件巾,拓扑关系是检测数据 质量的基础.从ArcGIS83开始.用户可以通过选择 若干规则的组合指定空间数据必须满足的拓扑关系约 束,发现可能存在的拓扑关系错误.这种方法必须在 图形矢量化完毕以后才能建立拓扑关系并检测错误 上述两种方法共同的缺陷是只描述了单个图形要 收稿日期:2005—04—18 素的性质,而没有反映管网的整体属性,因此对图形 数据一致性的检测不够严密.为此,本文提出用图来 描述管网拓扑关系,通过检测该拓扑关系是否符合拓 扑约束,并 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 了一套相应的拓扑约束规则. 1管网图形的拓扑结构及其图论描述 1.1管网数据的要素构成 供水管网信息系统中的管网图形要素主要有管 线,管件,抽象元素,相关设施和设备,按几何类型 分类可以分成:点状要素和线状要素.点状要素主要 有:井,水 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf ,阀门,用户节点,压力表,盲板,消 火栓等.其中井,水表,压力表等对应的是实际管网 巾的部件;用户节点等是根据实际情况进行抽象后得 到的一种点状要素.线状要素主要是管线. 管网系统中的要素种类众多,为了方便描述. 本文对管网系统中的点状要素进行一些简化,并在 此基础上进行阐述.本文讨论的点状要素有:(1) 用户节点.用户节点是一种抽象元素,它描述了供 水管网中的用户,其属性主要是用户的相关信息; (2)管线联通交点.管线联通交点是一种抽象节点, 它的实际对应管件是各种规格的管线接头,如三通 接头,四通接头等;(3)阀门.为简化描述,这里 的阀门仅代表双向的截止阀门.不包括三通,四通 阀门以及减压阀门等其他类型阀f1;(4)水表; 第4卷第1期韦人玮等:基于围棋型和拓扑约束的管网数据一致性检测?53? (5)压力表;(6)水源,既可以是水厂,也可以是 水库;(7)盲板. 1.2管网拓扑关系的图描述 将供水管网记为G=(V,E),其中代表管网中 的所有点状要素,称为顶点集,包括了压力表,阀门 等,E代表管网中的所有管道,称为边集.如果顶点 和,之间有管道连接,则称和有邻接关系.实 际管网中的水流方向比较复杂且可能因为水压的变化 而变化,因此必须通过测压点采集水压数据并进行水 力计算才能确定.而水流方向信息对管网图形数据一 致性检测没有实质性的作用,因此可以认为和之 间的弧段是无方向的,即G是无向图.实际管网中任 意点要素之间必然存在通路,因此G是连通图.这 样.管网的点状要素之间的拓扑邻接关系可以表示成 一 个无向连通图. 拓扑关系的建立算法比较成熟,这里就不再详 述.图在计算机中一般用邻接矩阵或者邻接表两种数 据结构来表示.当图中的顶点的数目较多.而边的数 目相对较少的情况下.用邻接矩阵表示会浪费很多内 存空间.因此,采用邻接表来表示图.图1是供水管 网图形的一个片断.由图1生成的拓扑关系用邻接表 的形式可以表示为图2. 《DwMl J_ )jCs1vElU @水表冈『JI}厦 ?服埘史点_? 图1管网图形片断 图2拓扑关系的邻接表表示 2拓扑约束的检测 2.1局部与整体拓扑约束 管网图形中要素之间复杂的连接关系和管网的整 体性质町以用以下两种拓扑约束描述: (1)局部拓扑约束.局部拓扑约束主要描述管线 和管件,管件和管件之间的连接关系.局部拓扑约束 是与连接规则等价的,是连接规则在拓扑关系中的反 映.如:根据连接规则,盲板只能位于管线的末端, 则在用邻接表表示的拓扑关系中盲板的邻接元素的个 数只能为1. (2)整体拓扑约束.整体拓扑约束是管网的整体 性质在拓扑关系中的反映.如:管网系统是连通的. 即管网中的任意两个元素之间存在通路,相应的,在 邻接表中的任意元素应该能够遍历其他的所有元素. 只有用图数据模型来描述管网拓扑关系才能对管网的 整体性质进行描述,进而进行整体拓扑约束的检测. 2.2拓扑约束规则 根据供水管网的实际情况.本文总结出以下的拓 扑约束规则用于管网图形数据一致性的检测. 2.2.1局部拓扑约束 (1)盲板,用户节点的邻接元素的个数为1,即 deg(V)=1,其中为盲板或片j户节点. (2)阀门,水表,压力表位于单根管线上,在邻 接表中这些元素的邻接元素个数为2,~lldeg(V)=2, 其中为阀门,水表或者压力表. (3)管线联通交点位于管线的交汇处,在邻接表 中,与它邻接的元素个数必须大于或等于3.即deg ()?3,其中为管线联通交点; (4)水源的邻接元素个数大于或等于1,即deg (V)?1,其中为水源. 2.2.2整体拓扑约束 (1)所有的管线都必须在边集中出现. (2)生成的图是连通冈. 2.3基于拓扑约束规则的一致性检测 检测某点状要素是否符合局部拓扑约束的方法 是:统计邻接表中该顶点的邻接元素的数目.即该顶 点的度,是否与局部拓扑约束一致.检测生成的拓扑 关系是否符合整体拓扑约束的方法是:(1)在生成 拓扑关系时, 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 管线图形和拓扑弧段(即图中的 边)的关系,~NPL1管线生成了0,b,c拓扑弧段.最 后统计没有出现在边集中的图形管线;(2)从任意 一 个顶点出发,对图进行深度优先或广度优先遍历. 并记录遍历到的节点.如果遍历的节点集合等于所有 顶点集合,则生成的图是连通图,满足整体拓扑约 束.如果生成的拓扑关系不能满足上述的拓扑约束. 则说明图形中存在错误.在很多情况下,一个图形错 误会引起多个拓扑关系错误,冈此数据一致性检测时 应该依次对各类要素进行局部拓扑约束检测并修正错 误,最后进行整体拓扑约束检测.下面的讨论将给出 一 些引起拓扑约束错误的可能原因. 造成拓扑关系不满足局部拓扑约束的原因有:(1) 元素图形的位置错误.如图3.若将管线联通交qXCS1 置于管线的中段而不是管线相交的位置,.~lJdeg(CS1) <3,不满足拓扑约束;(2)遗漏某些元素.如图3所 示.如果遗漏了用户节点USl,StJdeg(VE1)=1.不满 足拓扑约束;(3)两段管线图形之间没有咬合. ? 54?地理空间信息2006年 3结语 (DwM1 ?- -一 S1vEI【)IC @水表阀门l自板 ?联通交点一川』''1点 图3局部拓扑约束错误的图形 引起某些管线没有出现在边集中的原因有:(1) 如图4所示.盲板ED1的位置错误.没 图形位置错误. 有位于管线末端,则ED1L边的一段管线将不会出现 在图的边集中,不满足整体拓扑约束.但是在邻接表 r~deg(ED1)=1,满足局部拓扑约束,因此,仅仅靠 检测局部拓扑约束是不能检测出这类错误的;(2)两 段管线图形之间没有咬合.引起生成的图是非连通图 的原因有:遗漏了某些管线联通交点或者位置错误 如图4,由于两条管线相交处遗漏了一个管线联通交 点,使得从WM1开始无法遍历~IJVE1,ED1和US1.而 在这种情况下,各个元素都是满足局部拓扑约束的, 只有对整体拓扑约束进行检测才能排除这类错误. 《DwM1 '' EDlVElIJ @水表冈阀fJl亩板 ?联通交点一,l】,节点 图4整体拓扑约束错误的图形 本文提出的方法具有很好的可扩展性.在加入新 类型的要素后,建立拓扑关系和检测拓扑约束的方法 不用进行大的改动.通过用图数据模型来描述管网拓 扑结构不仅能够描述单个图形要素的性质,而且使得 管网的整体结构得到更好的表达.因此能够进行更加 严格的约束,保障数据质量.该方法生成的图数据模 型描述的管网拓扑关系不仅能作为数据质量检测的基 础,而且还可以在此基础上进行网络分析.在新疆克 拉玛依市供水管网地理信息系统的数据管网数据处理 中,该方法准确性和可靠性得到了验证. 参考文献 [1]GB/T50106-2001.中华人民共和国国家标准给水排水 制图标准『s] 周晓运,何涛,等.基于对偶点和扩展图结 [2]于铁峰, 构的化工厂管网建模[.1].计算机,1998,21(1): 47-54 [3]张斌,黄永红,常红星.等.二三维共享图结构的工 厂管网建模研究[J].计算机辅助 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 与图形学, 2000,12(4):255~261 [4]姜永发,张书亮,曾巧玲,等,基于图论的城市排水管 网GIS空间数据模型研究[A].2004年地理信息系统博 士学术论坛论文集『C].2004.93102 作者简介:韦人玮,男,硕士研究生,主要研究方向为电子地 图和GIS应用.