留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

利用有向图进行排水管网自动化流向分析

陈义 王建辉 张蒙

陈义, 王建辉, 张蒙. 利用有向图进行排水管网自动化流向分析[J]. 武汉大学学报 ● 信息科学版, 2019, 44(1): 62-67. doi: 10.13203/j.whugis20180341
引用本文: 陈义, 王建辉, 张蒙. 利用有向图进行排水管网自动化流向分析[J]. 武汉大学学报 ● 信息科学版, 2019, 44(1): 62-67. doi: 10.13203/j.whugis20180341
CHEN Yi, WANG Jianhui, ZHANG Meng. Automatic Flow Analysis of Drainage Pipe Network Based on Directed Graph[J]. Geomatics and Information Science of Wuhan University, 2019, 44(1): 62-67. doi: 10.13203/j.whugis20180341
Citation: CHEN Yi, WANG Jianhui, ZHANG Meng. Automatic Flow Analysis of Drainage Pipe Network Based on Directed Graph[J]. Geomatics and Information Science of Wuhan University, 2019, 44(1): 62-67. doi: 10.13203/j.whugis20180341

利用有向图进行排水管网自动化流向分析

doi: 10.13203/j.whugis20180341
基金项目: 

中国工程院重点咨询研究项目 2017-XZ-13

江苏省测绘地理信息科研项目 JSCHKY201718

详细信息
    作者简介:

    陈义, 教授, 主要从事大地测量、工程测量、GNSS、测量数据处理的研究工作。chenyi@tongji.edu.cn

  • 中图分类号: P208

Automatic Flow Analysis of Drainage Pipe Network Based on Directed Graph

Funds: 

The Key Projects of Consultation and Research of the Chinese Academy of Engineering 2017-XZ-13

the Science and Technology Research Plan Project of Surveying, Mapping and Geoinformation of Jiangsu Province JSCHKY201718

More Information
    Author Bio:

    CHEN Yi, professor, majors in geodesy, engineering survey, GNSS and measurement data processing method. E-mail: chenyi@tongji.edu.cn

图(7) / 表(3)
计量
  • 文章访问数:  2417
  • HTML全文浏览量:  196
  • PDF下载量:  239
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-09-08
  • 刊出日期:  2019-01-05

利用有向图进行排水管网自动化流向分析

doi: 10.13203/j.whugis20180341
    基金项目:

    中国工程院重点咨询研究项目 2017-XZ-13

    江苏省测绘地理信息科研项目 JSCHKY201718

    作者简介:

    陈义, 教授, 主要从事大地测量、工程测量、GNSS、测量数据处理的研究工作。chenyi@tongji.edu.cn

  • 中图分类号: P208

摘要: 超标排放是城市排水系统中面临的问题之一,为了高效准确地获取超标水体的流径及最终排放口,提出一种基于有向图的流向分析算法。在分析管网有向几何模型、流向与管线一致性后,利用正向广度优先搜索、缓冲区分析及跨管种混接点搜索进行算法设计,实现在步进搜索过程中自动获取超标水体所流经的管线,并通过实例验证了算法的有效性。与传统方法比较,提出的算法在海量数据下大幅提高了分析效率。

English Abstract

陈义, 王建辉, 张蒙. 利用有向图进行排水管网自动化流向分析[J]. 武汉大学学报 ● 信息科学版, 2019, 44(1): 62-67. doi: 10.13203/j.whugis20180341
引用本文: 陈义, 王建辉, 张蒙. 利用有向图进行排水管网自动化流向分析[J]. 武汉大学学报 ● 信息科学版, 2019, 44(1): 62-67. doi: 10.13203/j.whugis20180341
CHEN Yi, WANG Jianhui, ZHANG Meng. Automatic Flow Analysis of Drainage Pipe Network Based on Directed Graph[J]. Geomatics and Information Science of Wuhan University, 2019, 44(1): 62-67. doi: 10.13203/j.whugis20180341
Citation: CHEN Yi, WANG Jianhui, ZHANG Meng. Automatic Flow Analysis of Drainage Pipe Network Based on Directed Graph[J]. Geomatics and Information Science of Wuhan University, 2019, 44(1): 62-67. doi: 10.13203/j.whugis20180341
  • 城市排水系统是城市的废水处理、水质改善、排涝减灾、环境保护、资源再生循环利用的基础设施,是城市可持续发展及生态保护不可或缺的部分。而偷排漏排的超标水体未经处理直接排放到河流中,破坏了河流水质,渗透后污染了地下水,挥发的废气污染了大气,严重危害人们的健康,尤其是在饮用水水源保护区,其影响更加恶劣。城市规模的扩大使得排水管网愈加庞大,面对日益复杂、深埋地下的排水系统,传统的依托经验、图纸去分析查找超标水体的流径及最终流向费时、费力,雨污管道的混接使得分析更加困难。针对海量排水管网数据,准确高效的流向分析算法的应用对于防治城市水污染具有重要意义。

    国内地下管线信息系统基本上采用“两点一线”的数据结构[1],即管线由相互连接的管段组成,每个线段由管点相连,在此基础上形成了“管点-管段”数学建模方式。对于管网的分析集中于煤气及供水等的爆管分析(关阀搜索),更多的研究将管网抽象为无向图几何网络模型后采用常规的广度优先搜索(breadth-first search,BFS)或深度优先搜索(depth-first search,DFS)。在有向图几何网络模型方面,李平等[2]结合流向采用DFS对传统的爆管分析算法进行了改进;曾文等[3]对网络模型进行优化,提出供水管网U-V图模型,并设计了面向多施工点的关阀分析算法。分析中一般采用点线简单连接的数组集合模型、二分结构网络[4]、Leader-following一致性跟踪等[5]。而这些方法执行前通常需要将点线要素实例化后建立关联索引。

    本文将有向图的思想应用在排水管网流向分析中。首先,在考虑了雨污水管线混接的情况下,构建排水管网的有向图几何网络模型,并对数据准确性及有效性方面进行了分析;然后,采用正向广度优先搜索,通过缓冲区分析获取图面中与检索管点(段)关联的管段(点),并在步进搜索过程中逐步构建有效管线数据的遍历序列;最后,在计算机辅助设计(computer aided design,CAD)环境中实现本算法,并通过实例验证了该算法在海量数据下能够快速高效地获取流径及最终排放口。

    • 排水管网按照管种分为雨水、污水、雨污合流及其他管线等[6]。管线数据包括了管线图及管线数据库,按数据类型可分为管点、管段及注记等,包括管线空间信息、空间关联信息和属性信息,如图 1所示。

      图  1  排水管网逻辑结构

      Figure 1.  Logical Structure of Drainage Network

      有向图作为图论中的一种数据结构,视为由顶点组成的几何网络,网络中的各顶点由边实现彼此的连接,且每条边都有方向。排水管网因排水的方向性可以抽象为有向图,从而利用管段分段的方式建立管网的有向图几何网络模型G[7](G为一个有序的偶对,G=<PT, LN>),其中,顶点集PT={pt1, pt2ptn}是非空集合,其元素为管点,管点数N>2;边集LN={ln1, ln2lnn}是有序积PT×PT的一个子集合,其元素为管段,管段数M>0。与一条管段相连接的两个管点具有一定的次序关系,即管段ln=(pt1, pt2)是管点pt1pt2的有序对,称之为lnpt1为起点、pt2为终点,pt1pt2通过ln相互关联。按照该思想,将图 2(a)中的排水管网抽象化为图 2(b)中的有向图。

      图  2  管网模型

      Figure 2.  Pipe Network Model

    • 正确的流向是流向分析结果与实地相符合的前提。管线流向根据起终点的高差落差定义,包括正向(起点指向终点)及反向(终点指向起点),如图 3所示。在数据生产阶段需对流向进行检查[8],包括管段流向与起终点相对高差一致性、管点类型与连接管段流向一致性。

      图  3  流向类型

      Figure 3.  Flow Direction Types

      1) 管段流向与起终点相对高差一致性。对于有压管,由管段流向标识获取;对于无压管,通过比较同位置高程后确定,如图 4所示。

      图  4  无压管示意图

      Figure 4.  Schematic Diagram of Non-pressure Pipeline

      利用起终点位置的地面高程h、埋深或净空高度d计算高程h',按照如下规则进行判断:①计算起终点同一起算位置高程。针对不同埋设方式,地下管线计算内底高程(h'=h-d);架空管段计算外底高程(h'=h+d)。②判断管段流向与高程一致性。管段流向为正向,需满足h1'+Δhh2'(Δh为判断阈值);管段流向为反向,需满足h2'+Δhh1'。

      2) 管点类型与连接管段流向一致性。与管点连接的管段数定义为度k,从其他管点指向该管点的管段数为入度k+,反之为出度k-[9]。根据不同类型的管点连接管段及流向指向的不同,定义出入度判断的规则,如“出水口”作为排放口有且仅有1条管段与之连接,且流向指向该管点,即为出水口的入度k+=1,出度k-=0。为了防止出现“汇聚点”或管点类型与流向不一致的情况,根据表 1的判断规则进行管点类型与连接管段流向一致性判断。

      表 1  流向正确性判断规则

      Table 1.  Check Rules of Flow Direction

      管点类型 判断规则
      出水口,… k+=1 & k-=0
      预留口,… k+=1||k-=1
      进水口,… k+=0 & k-=1
      泵站,… k+=1 & k-=1
      其他(篦子,…) k+≥0 & k-≥0 & k++k->1
    • 在进行流向分析时,根据流向的指向判断管点、管段的有效性,判断原则如下:①有效管段:与检索管点相连接,使用状态不为废弃,流向方向从检索管点指向另一管点;②有效管点:检索管段中流向方向从另一管点指向的,且使用状态不为废弃的管点,即为该管点的出度k->0。根据流向的指向判断管段是否有效的规则见表 2

      表 2  管段有效性分析规则

      Table 2.  Analysis Rules of Valid Pipeline

      流向类型 检索点 流向指向 管段有效性
      正向 起点 另一管点 有效
      正向 终点 检索点 无效
      反向 起点 检索点 无效
      反向 终点 另一管点 有效
    • 采用正向广度优先搜索(forward BFS,F-BFS)方法,在步进搜索过程中逐步构建遍历序列模型。BFS作为一种图遍历算法,通过类似于树的按层次遍历,基本思想是:首先,以起始检索点为出发点,依次遍历所有未被访问过的邻接点集,并标记为已遍历;其次,以邻接点集中各顶点为出发点,依次遍历所有未被访问的顶点并标记;以此类推,直至图中所有与起始检索点联通的顶点均遍历[10]。结合有向图的指向性,遍历出度k->0的管点及管段,即为F-BFS。

      图 2中排水管网的雨水管点YS2为初始检索点进行搜索,并将网状结构变为树形结构,构建遍历序列的抽象模型,如图 5所示。由图 5可知,管点YS2流经管段为YS2-YS3-YS4-WS5-WS6,与管网中实际的流向一致。

      图  5  遍历序列抽象模型

      Figure 5.  Abstract Model of Ergodic Sequence

    • 在几何网络模型中,采用两点一线的数据结构将一条管线对象化处理为1个线要素和2个点要素,并定义管点类及管段类,详见表 3。从空间拓扑关系上看,点要素与线要素的端点重叠。

      表 3  管线数据结构

      Table 3.  Data Structure of Pipelines

      管线类型 管线属性
      管点(CPipPt) CString csPipType; //管线类型
      ObjectID pID; //管点标识符
      CString csPtName; //管点点名
      double dx, dy; //坐标
      bool bIsHyjtSitt; //混接点标识
      管段(CPipLn) CString csPipType; //管线类型
      ObjectID pID; //管段标识符
      CPipPtIn ptSt, ptEd; //起终点信息
      CStringcsDir; //流向
      管段端点(CPipPtInLn) CString csPtName; //点名
      double dx, dy; //端点坐标
    • 利用点要素缓冲区分析获取管线要素集合,通过要素类型、管线关联性及出度k-的判断获取与管点(段)关联的有效管段(点)。

      1) 有效管段提取算法伪代码如下:

      输入:pPt,dr

      输出:pIDMap,pPts,pLns

      pPts+=pPt;

      if pPt.pID∉pIDMap

        pIDMap+=pPt.pID;

      else return;

      GetEntsByPos(pPt.dx,pPt.dy,dr,pIDs);

      if pPtbIsHyjtSitt= true

        GetHyjtSitt(pPt,pIDs,pPtHS);

        pPts+=pPtHS;

      for i←0 to pIDs.Len

        if pIDs[i]∉pIDMap

          pIDMap+=pIDs[i];

          if pIDs[i] is LineID

            GetLnByID(pIDs[i],pLn);

            ptSt←pLn.ptSt;ptEd←pLn. ptEd;

      if (IsSame(ptSt,pPts) & kptSt-=1) ||

        (IsSame(ptEd, pPts) & kptEd-=1)

          pLns+=pLn;

      函数为GetLnsByPt(),主要步骤为:将管点pPt加入至检索集合pPts中,并以其点位为中心、定距dr为缓冲半径,操作函数GetEntsByPos()获取缓冲区内的要素集合pIDs;若pPt为混接点,操作函数GetHyjtSitt()获取对应跨管种混接点pPtHS并加入pPts;从pIDs中获取管段并操作函数GetLnByID()实例化pLn后,利用函数IsSame()判断管段端点与pPt属性的一致性,若一致,且k-=1,将pLn加入管段集合pLns中。为了防止出现重复判断,已访问要素存储在pIDMap容器。

      2) 有效管点的提取算法伪代码如下:

      输入:pLn,dr

      输出:pIDMap,pPt

      if pLn.pID∉pIDMap

        pIDMap+=pLn.pID;

      else return;

      if k(ptSt)-=1

        pPtIn=pLn.ptEd

      else

          pPtIn=pLn.ptSt;

      GetEntsByPos(pPtIn.dx,pPtIn.dy,dr,pIDs);

      for i←0 to pIDs.Len

        if pIDs[i]∉pIDMap

          pIDMap+=pIDs[i];

        if pIDs[i] is PointID

            GetPtByID(pIDs[i],pPtTmp);

            if IsSame(ptStIn,pPtTmp)=true

              pPt=pPtTmp;

              return

      函数为GetPtByLn()。与管点类似,以管段pLn流向指向的端点坐标为检索中心获取与之关联的管点pPt。

    • 由于涉及到“管点检索有效关联管段”、“管段检索有效关联管点”的循环嵌套,算法设计时,以管点检索为外层循环,管段检索为内层循环。对于初始检索为管段pLn,操作函数GetPtByLn()获取该管段流向指向的管点pPt为检索点进行分析。

      采用“点-段-点-段…”嵌套循环的递归方式对管线数据进行遍历,通过点段的连接关系及流向获取有效管线数据。自动搜索算法的伪代码如下:

      输入:pPt

      输出:pPtVids,pLnVids

          pIDMap←null;

          pPtSels+=pPt;

      do

        pLnSels←null;

          for i←0 to pPtSels.Len

            GetLnsByPt(pPtSels[i], pIDMap,pPts, pLns);

            pPtVids+=pPts;

        if pLns≠null

          pLnSels+=pLns;

          if pLns≠null

          pLnVids+=pLns;

        pPtSels←null;

          for i←0 to pLns.Len

            GetPtByLn(pLns[i], pIDMap,pPtSel);

            pPtSels+=pPtSel;

      while pPtSels≠null

        pIDMap←null;

      该算法的输入为检索管点pPt,输出为有效管线集合pPtVids、pLnVids。首先,初始化遍历容器PIDMap用于标记已访问要素,并将初始检索点pPt加入至选择集合pPtSels中;其次,采用do-while后测试循环语句为外层循环,获取pPtSels中管点有效连接管段pLns加入集合pLnVids中,并将访问到的检索管点加入集合pPtVids中;最后,以for-next为内层循环,将与管段集合pLns相连接的有效管点加入选择集合pPtSels中;重复上述嵌套循环步骤, 直至选择集合pPtSels为空,结束搜索。

    • 采用C++语言调用ado及ObjectArx在AutoCAD 2010中实现本算法。开发环境为Visual Studio 2008,运行环境为Windows 7,硬件设备采用3.2 GHz四核Intel CPU和16.0 GB RAM。实验数据为中国某东部城市真实的排水管网数据,包括污水管线448.71 km,管段14 762条,管点13 851个; 雨水管线1 022.84 km,管段70 765条,管点74 542个,其中,混接点4 382个。

    • 采用自动随机抽样的方式选取管点进行算法结果验证,通过相关性及对比分析总结规律,包括:①在总管线数据不变的情况下,分析运行时间与遍历管线记录数(管点及管段数)的相关性;②在不同总管段、采用不同方法,对比各方法下访问相同管点运行时间与总管线记录数的关系。并以每次同等条件下,取20次实验结果的平均值作为最终实验结果。

      分析运行时间与遍历记录数的相关性。根据最终实验结果,以遍历记录数50个为单位绘制遍历记录数-运行时间的折线图,见图 6(a)。可以看出,该方法在总管线固定的情况下,运行时间与遍历记录数近似为线性关系,且随着遍历记录数的减小而耗时缩短。

      图  6  运行效率对比

      Figure 6.  Comparison of Time Complexity

      采用传统的数据库实例化网格模型分析、数据库结构化查询语言(structured query language,SQL)查询分析及基于图形缓冲区分析的方法,以遍历记录数500个为恒定单位,获取在不同管线记录数下的运行时间。根据最终实验结果,以总管线记录数3万个为单位绘制总记录数-运行时间的折线图,见图 6(b)。可以看出,本文算法耗时始终小于其他算法,在遍历记录数恒定的情况下,与整个管网中总管线记录数无相关性,特别是随着管线数增多时,本文算法比其他两种分析算法的效率明显提高。

    • 在分析过程中,对获取的有效管线进行重绘设色并高亮渲染。以图 7中右侧的污水进水口为起始搜索管点进行流向分析,共搜索出最终流向位置2处,获取有效管线8.47 km,管段169条,管点171个。由图 7可知,通过对有效管线的渲染, 在海量数据下可以更加直观地对分析结果进行展示,进一步方便对数据的分析应用。

      图  7  结果展示(局部)

      Figure 7.  Display of Result(Part)

    • 本文提出的排水管网自动化流向分析方法,引入有向图及F-BFS的设计思想,考虑了雨污水管线混接的情况,通过在步进搜索过程中利用点要素缓冲区获取管线要素,并对有效关联的管线数据进行实例化,能够尽可能减少无关管线的获取。特别是在海量数据中,这种直接对原始图形中实体的操作能够快速搜索到有效流径集合,降低时间及空间复杂度。

      本文算法结构清晰、简单,方便转换为计算机语言,具有实际应用意义。基于本算法的分析功能已应用于某市排水管网项目中,实现了确定水污染源头后对受污染管线的准确监控。同时,采用反向广度搜索算法可以解决诸如给水及燃气管网的爆管分析、关阀搜索等类似问题。另一方面,通过确定有效管线集合,结合管线的径流面积、承载力等,可应用到优化流体类管网设计中。

参考文献 (10)

目录

    /

    返回文章
    返回