基于有向无环图的立交结构构建方法

王宇昆，曹 力，赵 洋，李 琳

基于有向无环图的立交结构构建方法

王宇昆1,2，曹 力1,2，赵 洋1,2，李 琳1,2

(1. 合肥工业大计算机与信息学院，安徽 合肥 230601；2. 工业安全与应急技术安徽省重点实验室，安徽 合肥 230009)

道路信息是数字城市中的重要元素，道路网中的立交结构建模对于城市交通三维仿真、交通优化、城市规划等诸多领域均有重要意义。当前已有大量针对城市道路网建模技术的研究工作，但对立交结构的处理尚未有针对性的表达方法。通过对立交结构的观察分析，提出一种基于有向无环图的立交结构构建方法，期望达到高效、高质量建模的目的。首先对二维栅格数据进行预处理，提取有效道路信息；其次依据提取的信息构建有向无环图(DAG)，用于表达立交结构拓扑关系；再次基于提出的立交桥道路高度自动估算方法，利用DAG结合道路的结构特性、功能特性及相关先验知识，计算得到道路控制点的高度；最终依据计算得到的道路高度和拓扑信息进行立交结构三维模型构建。实验选取了华东地区3个典型立交结构进行测试，结果证明该方法在数据获取、计算正确率方面有一定优势，有助于简化立交结构建模流程。

计算机辅助建模；启发式建模；城市道路网；立交结构；有向无环图

在虚拟三维数字城市中，道路网是至关重要的部分，立交桥则是城市道路网中的连接枢纽。近年来，城区场景仿真在城市规划、交通仿真、电影、游戏等领域应用广泛[1-2]。其中，对具有显著三维特征的城市立交桥快速建模已成为该领域的重要应用课题[3]，具有一定的理论意义和重要实用价值。目前在主流的移动端地图软件中，会出现立交桥模型与实际情况不符的情况，表现为白模没有下穿隧道、道路间层级关系错乱等。如图1所示白模道路层级关系与实际情况恰恰相反。

当前已有大量针对城市路网、交通路网建模技术的研究工作[1-2,4-6]。针对城区尺度的道路网，研究者提出不同方法用于快速生成真实的城区规模道路网。如PARISH和MÜLLER[7]采用L-system并以二维地图数据作为输入同时添加约束条件生成道路网；SUN等[8]提出基于模版的方法；VANEGAS等[9]提出前向反向建模相结合的方法；NISHIDA等[10]提出基于实例的方法；SONG和WHITEHEAD[11]以基于代理的方法从GIS数据中提取道路信息进行建模等。但这些工作并不涉及城区道路网中立交结构的生成。

立交结构是城市交通网络中比较复杂的部分，一般由主体、交叉构件、空间连接件组成，具有显著的三维特征和复杂的拓扑结构[3]。已有大量针对立交结构图形表达及快速建模的研究。胡碧松和龚建华[12]给出了基于高分辨率遥感影像的大型立交结构建模流程；陈卓和马洪超[13]提出一种基于机载激光雷达数据(light detection and ranging，LIDAR)的立交桥建模方法。这些方法在参数设置、数据处理等方面对用户的专业素养要求较高且成本高昂。文献[14-16]提出了针对立交结构拓扑关系的抽象表达，并应用于对特定形态的立交结构提取分类；文献[17-18]提出了基于二维地图数据的立交结构快速建模方法，但对层数较多的复杂立交结构建模效果不理想。

综上，对城区道路网中的立交结构的描述和建模还存在很多不足，本文提出一种立交结构快速构建的方法，并通过生成实际的城市立交桥模型验证方法的有效性，主要贡献为：①提出基于有向无环图(directed acyclic graphs，DAG)的立交结构拓扑关系的抽象描述；②提出一种基于立交桥道路的空间特性、功能特性的道路高度计算方法。

1 相关工作

1.1 立交结构构建

近年来，针对立交结构建模方法的研究可根据数据来源分为2类：①基于高分辨率的航空影像、卫星遥感影像图、高精度三维点云数据直接获取目标区域的拓扑关系和精确的高度信息进行建模。如胡碧松和龚建华[12]根据高分辨率航空影像提出了建立立交桥的三维数据结构和空间拓扑关系，以及大型立交桥三维建模的具体流程。陈卓和马洪超[13]提出一种基于LIDAR数据的立交结构建模方法，可直接获取地物表面高精度、高密度的三维点云。YANG等[19]提出了一种从大规模移动激光扫描点云中识别道路边缘点，提取并构建其三维模型。这类方法数据采集成本较高，数据解析难度较大，建模结果的好坏依赖于对数据的前处理，无法实时建模，对非专业用户不友好。②基于更易获取的二维地图数据确定拓扑关系和计算高度信息，再提供一定的交互方式由用户手动调整计算错误的结果。该方法更依赖计算完成的后处理，需要设计友好的用户交互方式。如文献[17]基于二维栅格数据提出一种包括立交桥道路中心线提取、交叉点检测、道路三维建模的立交桥快速构建方法。该方法需要检测道路交点再去掉大量共线点，导致构建的曲线道路不够平滑，且限定了立交桥层数不能超过3层，无法构建更复杂的立交桥。文献[18]提出将描述二维道路中心线的GIS数据转换为三维道路网模型的方法，从而实现多种立交桥的参数化构建，但由于数据模型限制，对于层次较多的立交结构，最终构建的模型正确率不高。

1.2 立交结构抽象描述

针对在大尺度道路网中快速提取立交结构的难点问题，提出立交结构拓扑关系的不同抽象化描述。如文献[14]利用有向属性关系图描述具有典型平面结构的立交桥，构建立交结构模版库，采用图匹配技术从道路网中快速匹配立交结构；文献[15]提出基于立交结构的几何特征构建量化表达式，对不同立交结构进行抽象化描述。文献[16]提出一种基于特征的3层数据模型，用于立交结构的交通仿真，可描述简单立交结构的拓扑关系和层级关系，但对较复杂的立交结构缺乏深入研究。这些抽象化描述方法并未用于立交结构的建模，且在应用时均存在一定的局限性。

1.3 城市道路网建模

过程式建模方法被认为是构建大尺度道路网的有效方法。文献[7]最早在L-system的基础上以二维地图数据作输入并添加约束条件，计算生成城市道路网及有约束地生成道路周围的建筑群。随后诸多研究者在此基础上提出了改进的道路网生成方法。如LINDORFER等[20]利用最小生成树算法将人口密度高的区域连接起来作为快速路，并在快速路围成的封闭区域中利用L-system生成区域内的道路。CHEN等[21]首先提出允许用户编辑的路网生成模型，提升了建模的真实性；SUN等[8]以模版的规则生成系统的路网生成模型；文献[9]提出前向和反向建模相结合的方法，应用参数估计(避免提供明确的参数输入)并支持交互式的路网模型生成和编辑。文献[10]引入一种基于实例的方法，由用户在OSM (OpenStreetMap)中自主选择一到多个局部实例定义要生成的道路样式，该系统无需设定输入参数，但选择的局部实例限制了生成的道路网的多样性；文献[22]提出一种新的基于语义的过程式建模方法，将基于实例和参数输入的方法相结合，提供一种“回退”机制，当用户找不到合适的实例时可自行设置输入参数构建道路网；文献[11]根据交通仿真的需要，提出一个基于代理的道路网生成系统，且可分析生成的道路网的方向性、连通性、曲率等参数。

立交结构相比普通道路，具有显著的三维特征和复杂的拓扑结构，其模型各个部分的参数更为复杂，现有的道路网生成方法需要用户设置各种参数输入，并不适用于目标区域的立交结构模型生成。

综上所述，目前针对城市道路网建模、立交结构构建及抽象化描述的研究较为广泛。但所述方法在数据源获取的难易性、层级关系计算及应用范围等方面均存在一定的局限，这是本文主要的研究动机。本文的研究内容主要是依托易于获取的二维地图数据、基于DAG快速得到立交桥子道路的拓扑结构和高度信息，从而进行高效、高质量建模。

2 基于有向无环图的立交桥描述

2.1 问题描述

空间结构的形式化描述方法主要有串文法、树文法、图文法等。图作为一种常用的数据结构，常被用于描述各种事物基元之间的拓扑关系，是一种有效的结构特征信息描述方式。在对立交桥拓扑结构进行抽象化描述时，直接参考平面道路的拓扑关系，如图2(a)所示，仅能描述无匝道和引桥的平面交叉道路。研究者尝试利用有向图(directed graph，DG)对道路结构进行描述，如文献[14]提出了描述立交结构的有向属性关系图，即用DG描述立交结构的拓扑关系，再引入相关属性描述其空间结构；文献[15]根据立交结构的拓扑关系和几何形态，将立交结构抽象为具有不同拓扑关系的DG，建立典型的量化表达式模板库，通过对比量化表达式达到识别目的；文献[17]在数据处理阶段将二维栅格地图抽象为点和线构成的DG再进行分析。

使用DG描述立交桥拓扑关系时在图中会形成环路，甚至形成全连通图，如图2(b)所示。立交结构拓扑关系、空间结构复杂，计算高度信息时，需要多次迭代。形成环路势必会对相应的算法设计产生限制，如文献[17]的算法在设计之初就限定立交桥层数不超过3层，就是出于这种考虑。

综上所述，基于DG设计立交结构的高度计算方法有很大局限性。本文提出将具有拓扑表达优势的DAG用于立交结构道路拓扑关系的描述，以解决环路带来的限制，并以此为基础设计相应的高度计算方法。

2.2 立交桥的有向无环图描述

一个完整的立交结构可以抽象为由若干道路中心线、道路控制点组成的图形结构。本文采用DAG的=(,)描述，其中为所有道路控制点的集合，为道路中心线的集合，用(1,2,···,P)Î表示从控制点1到控制点的道路。本文方法所采用的控制点数据结构为：

图2是采用DG和DAG对十字形道路交叉口描述的对比，为了使对比效果更明显，这里仅画出DAG部分连接关系。按照车辆行驶方向将一条道路分为方向相反的2个方向，由+/–号代表不同车流方向。按照车流右行规则，图2(c)所示是十字路口的DAG部分描述。全部的拓扑关系见图3(a)。从图2中可以看出，图2(a)所描述的拓扑结构无法描述更多方向之间的拓扑关系；图2(b)会形成环路；图2(c)的描述可以克服前2种方法的不足，更为合理。

图2 有向图与有向无环图的对比

Fig. 2 Comparison between DG and DAG

2.3 立交桥的典型结构

立交桥所处的交叉口根据形态分类主要有T形、Y形、十字形、X形等形式[23]，图3是十字形路口及T形路口的DAG描述。

图3 典型交叉口的有向无环图描述

参考道路桥梁专业中立交桥的分类方法[24]，可根据二维形态对立交结构分类。首先根据道路交汇个数将立交桥分为三肢和四肢2类，再根据其中包含的弧段个数对其继续细分为喇叭口形、苜蓿叶形、环形、单圈形、多圈形、十字形6类。由此可将典型立交桥分为11类，如图4所示。

图4 典型立交结构

同时可结合道路的功能及形态特点将立交桥道路分为3类，见表1。

表1 立交桥道路分类

3 立交结构分层方法

立交结构模型构建前需要获取道路间的拓扑关系和层级关系。从原始数据中利用DAG对其进行结构化描述，可以确定拓扑关系。层级关系可以根据立交桥道路的功能特性、几何特点、相关先验知识并结合DAG推导得到。根据计算得到的图元参数结合基本组件可生成模型。对于产生冲突的情况可回退至高度计算环节重新计算确定道路的层级关系。图5为本文方法核心流程。

图5 核心流程

3.1 DAG的构造

根据上述，DAG在表达立交桥拓扑关系、设计道路高度计算算法方面有诸多优越性，本文提出一种立交桥DAG描述构建方法。

方法1. 立交桥DAG描述构建方法

输入：和，道路控制点数组、道路中心线数组；

输出：={，} 立交桥对应的DAG描述，为控制点集合，为道路中心线集合。

3.2 立交桥道路分层

从原始数据的道路中心线和控制点构造相应DAG描述，很容易得到控制点之间的拓扑关系。并根据道路中心线进行道路分类。由2.3节所述，匝道弯曲较大，主桥更接近直线。通过已知控制点进行曲线拟合，再计算道路中心线上控制点相对于拟合曲线的平均残差以区分主桥和匝道。引桥的作用是减缓主桥上、下桥坡度，跨度较小且接近直线，因此可以根据曲率变化区分匝道和引桥。本文提出以下方法对立交桥子道路进行分类。

方法2.立交桥道路分类方法

输入：={,}，立交桥的DAG描述；

输出：，，，分别代表主桥、匝道、引桥集合。

方法2中曲线拟合过程需要根据实际情况选择不同的拟合曲线。在主桥接近直线形时，可采用最小二乘法进行直线拟合；在主桥弯曲程度较大时，选择阶贝塞尔曲线拟合效果更好。

3.3 道路控制点高度计算

通过前述方法可得到不同道路的拓扑关系以及确定道路所属功能类别。计算道路控制点高度可以确定道路的层级关系。坡度常用来描述道路高度变化的趋势。本文方法根据道路功能特性、相关先验知识估算道路控制点高度，并结合DAG的结构特性对估算结果进行自动调整。按照主桥、匝道、引桥的顺序依次计算道路高度。主桥作用是实现主方向上的车辆流通，定义了立交结构的主方向。相对于匝道、引桥，主桥在高度上往往不存在上升和下降的变化。因此可根据道路桥梁建设标准[25]，直接对各方向上主桥赋予不同的高度层级，具体的高度层级需程序预设。引桥作用是减缓道路坡度变化，其高度变化只存在递增和递减2种情况。匝道的高度变化根据实际情况变化更加复杂，但同一条匝道高度变化最多只会出现上升、下降2次趋势的变化。同时，匝道和引桥的起点、终点都在主桥上。因此可根据起始点高度，结合不同种类道路高度变化趋势的不同以及坡度依次计算道路控制点的高度。在《城市道路设计规范》[25]中，针对立交桥坡度范围做了明确规定。冰冻地区最大纵坡度为4%，非冰冻区域最大纵坡度为5%。本文调研了华东地区不同城区立交桥道路坡度情况，最终将实验计算过程中坡度范围定为2.5%~3.5%。并通过方法3估算主桥、匝道、引桥控制点高度，以此估算层级关系。

方法3.匝道、引桥控制点高度计算方法

输入：,,，分别代表主桥、匝道、引桥集合；和上升坡度和下降坡度；

输出：匝道、引桥控制点的高度。

4 建模及分析

本文基于Unity3D 2018.2.10f1开发了道路的拓扑关系、层级关系自动计算、模型生成软件工具。将目标区域二维栅格地图数据处理得到立交结构道路中心线及道路控制点数据作为系统输入数据，经系统自动计算可确定各条道路的拓扑关系和高度信息。最后利用基本组件结合上一步得到拓扑及层级关系进行建模。

4.1 数据处理

首先从栅格地图数据中提取有效信息，图6为华东某城区立交桥的二维栅格地图数据及相对应的地图数据，图中蓝色区域及其边界线代表道路周围的建筑物及其轮廓，非建筑物处的线段代表道路，线段上的点代表道路控制点。

图6 地图数据及栅格地图

对栅格地图数据预处理的目标是提取立交桥子道路的中心线及控制点坐标。预处理操作主要包括：①读取栅格地图，并进行灰度化；②依据灰度化的结果，采用图像二值化方法将地图数据分隔成道路和建筑物区域，并只保留道路数据；③由于立交桥结构复杂，道路的控制点数目多，且立交结构周围往往存在建筑物群落及内道路，经二值化并不能完全去除不必要的道路、建筑物信息，因此还需要去除噪声数据；④根据像素点坐标将道路和控制点转化为更平滑的数据。经以上步骤可提取目标区域立交桥道路中心线及控制点信息，如图7所示。

图7 数据预处理流程

按图7所示的操作步骤，可从二维栅格地图中提取出立交桥的道路中心线和控制点，再根据点、线基本图元的信息推导出该立交结构相应的DAG表达，至此得到该区域全部的拓扑关系。以图6所示区域为例，结合2.2节所述，将一条道路上所有车辆流通方向定义为2个相反方向。对于数据处理所得的最终结果(图7)，可以将道路控制点抽象为DAG节点，将2个控制点之间的道路中心线抽象为DAG的一条边，将道路车流方向抽象为DAG有向边的方向。以一组+/–号表示经过一个道路控制点的2个相反的车流方向。首先确定主路对应的边的方向，再按照车流右行规则，可确定连接不同方向的主路的匝道对应的有向边的方向。经过迭代推导最终可得到图8所示的DAG表达结果。这里隐去了中间控制点，仅保留了每条道路的起始点及不同道路相交的点。

图8 推导所得的DAG表达示意图

4.2 基于基本组件建模

立交桥是由各种基本组件构成的具有复杂空间结构的建筑物。完整的立交桥除了道路，还包括桥墩以及各种辅助物(路灯、交通辅助线等)。李尚林等[26]提出一种基于基本组件的多层参数建模方法。本文定义立交结构的高层参数是道路的拓扑关系及层级关系，低层基本参数包括道路长度、宽度、跨度、曲率等均可由道路中心线及控制点数据计算得出。构建立交结构的基本组件库，结合上述方法得到的高层及低层参数，可快速生成真实的立交结构模型。图9是立交结构基本组件示例，图10是利用基本组件的立交结构建模过程示例。4.3节给出了多组实验建模结果。

图9 立交结构基本组件示例

图10 建模过程示例

4.3 建模结果

本文选取了华东地区的3个典型立交结构进行数据计算并建模。表2依次给出选取区域的卫星图、计算及建模结果。计算结果示意图是三维场景下带有高度信息的道路中心线及控制点展示。为了突出表现道路层级的不同，本文还设置了特定的高度-RGB值计算公式，将道路中心线和控制点的高度信息映射为限定范围内唯一RGB值，表2中红色点代表高度为0的控制点。同时从每个控制点中心向地面射一条直线，作为表现控制点高度的参照物。对建模结果进行渲染可以得到真实的渲染结果。图11是区域3的包含建模结果及周边建筑场景的渲染结果。

表3为本文方法对于不同实验区域的计算正确率。其结果表明，对于具有典型形态特征的立交结构，本文方法得出的道路分层结果正确率较高。模型生成时间包括数据处理时间、DAG构建时间、通过DAG描述道路分类及高度计算时间、建模时间及必要的交互时间。如实验区域1的模型构建流程用时为：数据处理耗时约15.0 s，DAG生成约0.8 s，道路分类及高度计算26.2 s，模型构建过程约53.0 s，交互操作约14.0 s。

表2 建模效果对比

图11 区域3渲染图

可以看出，利用DAG的拓扑描述优势能够在较短时间内完成模型构建的工作，3个区域的自动建模过程时间均在200.0 s以内，相比手工建模大大节省了时间。本文方法使得领域外用户也可以对层级关系复杂的立交桥快速构建出符合大致要求的高精度模型。本文方法尚不能自动解决立交结构中下穿隧道的分层处理，需要在自动计算之后由用户手动对计算结果进行调整。

表3 本文方法对于不同实验区域的计算正确率

4.4 对比分析

对立交结构进行建模在城市规划、交通仿真等领域有着重要的应用价值[1-3]。应用价值决定了衡量建模方法的优劣可从建模效率、建成模型准确程度等方面评价。当前立交桥模型构建的方法主要数据来源包括，带有高度信息的高精度卫星遥感数据和无高度信息的二维地图数据2类。文献[13]和[17]属于这2类方法的典型工作。

本文从数据来源、计算结果、应用范围3个方面与文献[13]和[17]进行了对比。从数据来源方面比较，文献[13]方法的数据源为高精度LIDAR数据，文献[17]及本文方法均为二维栅格数据，相比文献[13]数据更易获取及处理，对于领域外的普通用户更加友好。在建模结果正确性方面，文献[13]数据源本身提供了高精度的高度信息，因此正确率最高。文献[17]显示其高度计算结果正确率较高，但由于算法限制，所能解决的立交结构层数被限定在3层，应用有限制。而本文方法由于采用了DAG描述立交结构的拓扑关系，不会出现环路情形，在后续的高度计算过程中对于立交桥层级没有限制。表3结果表明，本文方法对于典型立交桥的道路分层计算结果正确率较高。通过对比3种方法(表4)，本文方法所需数据获取简单，在保证计算结果正确合理的基础上，能对更多不同形态的立交桥进行道路的层级关系推算。

表4 3种方法对比

5 结 论

本文提出将具有拓扑表达优势的DAG用于立交结构拓扑关系的描述。以二维栅格地图作为输入数据，将立交结构道路抽象为DAG，可以方便地获取道路之间的拓扑关系。根据道路的形态特点和功能特性，结合领域先验知识，进行道路高度计算，最后通过基本组件的参数化建模方法，构建城市立交结构模型。对比现有方法，本文方法数据源易获取、计算过程较为简单。实验结果表明本文方法对于典型立交结构的道路高度自动计算结果正确率较高，简化了立交结构三维模型构建的流程。

然而立交桥设计及建造之初就受到诸多因素的限制，因此有相当部分的立交桥并不能用严格的分类方法对其进行划分。对于非典型形态的立交桥，本文方法计算效果不够理想，后续的研究重点将在针对非典型形态的立交桥扩充推算其道路层级关系的方法。

[1] 王华, 徐明亮, 毛天露, 等. 三维汽车群组动画仿真研究综述[J]. 计算机辅助设计与图形学学报, 2017, 29(2): 211-220. WANG H, XU M L, MAO T L et al. Survey of three-dimension traffic animation[J]. Journal of Computer-Aided Design & Computer Graphics, 2017, 29(2): 211-220 (in Chinese).

[2] SHEN J J, JIN X G. Detailed traffic animation for urban road networks[J]. Graphical Models, 2012, 74(5): 265-282.

[3] 刘耀丹. 立体交通三维道路网快速构建算法研究[D]. 郑州: 郑州大学, 2017. LIU Y D. Fast construction algorithm of the three-dimensional road network[D]. Zhengzhou: Zhengzhou University, 2017 (in Chinese).

[4] CHAO Q W, SHEN J J, JIN X G. Video-based personalized traffic learning[J]. Graphical Models, 2013, 75(6): 305-317.

[5] CHAO Q, JIN X, HUANG H W, et al. Force-based heterogeneous traffic simulation for autonomous vehicle testing[C]//2019 International Conference on Robotics and Automation (ICRA). New York: IEEE Press, 2019: 8298-8304.

[6] CHAO Q W, DENG Z G, REN J P, et al. Realistic data-driven traffic flow animation using texture synthesis[J]. IEEE Transactions on Visualization and Computer Graphics, 2018, 24(2): 1167-1178.

[7] PARISH Y I H, MÜLLER P. Procedural modeling of cities[C]//The 28th Annual Conference on Computer Graphics and Interactive Techniques – SIGGRAPH’01. New York: ACM Press, 2001: 301-308.

[8] SUN J, YU X B, BACIU G, et al. Template-based generation of road networks for virtual city modeling[C]//Proceedings of the ACM Symposium on Virtual Reality Software and Technology – VRST’02. New York: ACM Press, 2002: 33-40.

[9] VANEGAS C A, GARCIA-DORADO I, ALIAGA D G, et al. Inverse design of urban procedural models[J]. ACM Transactions on Graphics (TOG), 2012, 31(6): 168.

[10] NISHIDA G, GARCIA-DORADO I, ALIAGA D G. Example-driven procedural urban roads[J]. Computer Graphics Forum, 2016, 35(6): 5-17.

[11] SONG A, WHITEHEAD J. TownSim: agent-based city evolution for naturalistic road network generation[C]// The 14th International Conference on the Foundations of Digital Games. New York: ACM Press, 2019: 1-9.

[12] 胡碧松, 龚建华. 大型立交桥三维建模方法研究[J]. 测绘科学, 2008, 33(1): 100-102, 87, 248-249. HU B S, GONG J H. Research on 3D modeling method of large-scale overpass[J]. Surveying and Mapping Science, 2008, 33(1): 100-102, 87, 248-249 (in Chinese).

[13] 陈卓, 马洪超. 基于机载LiDAR数据的大型立交桥自动提取与建模方法[J]. 测绘学报, 2012, 41(2): 252-258.CHEN Z, MA H C. Automatic extracting and modeling approach of city cloverleaf from airborne LiDAR data[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(2): 252-258 (in Chinese).

[14] 徐柱, 蒙艳姿, 李志林, 等. 基于有向属性关系图的典型道路交叉口结构识别方法[J]. 测绘学报, 2011, 40(1): 125-131.XU Z, MENG Y Z, LI Z L, et al. Recognition of structures of typical road junctions based on directed attributed relational graph[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(1): 125-131 (in Chinese).

[15] 王骁, 钱海忠, 丁雅莉, 等. 采用拓扑关系与道路分类的立交桥整体识别方法[J]. 测绘科学技术学报, 2013, 30(3): 324-328. WANG X, QIAN H Z, DING Y L, et al. The integral identification method of cloverleaf junction based on topology and road classification[J]. Journal of Geomatics Science andTechnology, 2013, 30(3): 324-328 (in Chinese).

[16] DENG M, FEI L. Research on modeling the overpasses for mapping and navigation[C]//Geoinformatics 2008 and Joint Conference on GIS and Built Environment: The Built Environment and Its Dynamics. Bellingham: International Society for Optics and Photonics (SPIE), 2008: 71442L.

[17] ZHAO X C, LIU Y D, WANG Y P. Automatic extraction and construction algorithm of overpass from raster maps[M]//Lecture Notes in Computer Science. Cham: Springer International Publishing, 2016: 479-489.

[18] WANG J, LAWSON G, SHEN Y Z. Automatic high-fidelity 3D road network modeling based on 2D GIS data[J]. Advances in Engineering Software, 2014, 76: 86-98.

[19] YANG B S, FANG L N, LI J. Semi-automated extraction and delineation of 3D roads of street scene from mobile laser scanning point clouds[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2013, 79: 80-93.

[20] LINDORFER M, BACKFRIEDER C, KIESLICH C, et al. Environmental-sensitive generation of street networks for traffic simulations[C]//2013 European Modelling Symposium. New York: IEEE Press, 2013: 457-462.

[21] CHEN G N, ESCH G, WONKA P, et al. Interactive procedural street modeling[C]//ACM SIGGRAPH 2008 Papers on – SIGGRAPH’08. New York: ACM Press, 2008: 1-10.

[22] TENG E, BIDARRA R. A semantic approach to patch-based procedural generation of urban road networks[C]//The International Conference on the Foundations of Digital Games – FDG’17. New York: ACM Press, 2017: 1-10.

[23] 李晋, 赵之仲, 黎奎. 公路设计新理念与案例分析[M]. 徐州: 中国矿业大学出版社, 2014: 220-222. LI P, ZHAO Z Z, LI K, et al. New concept of highway design and case analysis[M]. Xuzhou: China University of Mining and Technology Press, 2014: 220-222 (in Chinese).

[24] 宋培抗. 城市道路交叉口规划与设计[M]. 天津: 天津大学出版社, 1995: 132-135. SONG P K. Urban Road intersection planning and design[M]. Tianjin: Tianjin University Press, 1995: 132-135 (in Chinese).

[25] 北京市市政设计研究院. 城市道路设计规范[EB/OL].(2006-06-20) [2020-04-20]. https://wenku.baidu.com/view/d2f32584e53a580216fcfef1.html. Beijing Municipal Design and Research Institute. Code for design of urban roads[EB/OL]. (2006-06-20)[2020-04-20]. https://wenku.baidu.com/view/d2f32584e53a580216fcfef1.html (in Chinese).

[26] 李尚林, 李琳, 曹明伟, 等. 面向真实构建的徽州建筑快速建模方法[J]. 软件学报, 2016, 27(10): 2542-2556. LI S L, LI L, CAO M W, et al. Construction-oriented rapid modeling method on Huizhou architectures[J]. Journal of Software, 2016, 27(10): 2542-2556 (in Chinese).

Construction method of overpass structure based on directed acyclic graph

WANG Yu-kun1,2, CAO Li1,2, ZHAO Yang1,2, LI Lin1,2

(1. School of Computer Science and Information Technology, Hefei University of Technology, Hefei Anhui 230601, China; 2. Anhui Province Key Laboratory of Industry Safety and Emergency Technology, Hefei Anhui 230009, China)

Road information is an important element for a digital city. Modeling the overpass structure is of great significance to many areas, such as the simulation of urban traffic, traffic optimization, and urban planning. Although a great amount of research was conducted on the modeling of urban road networks, a targeted solution for the treatment of overpass structures remained to be put forward. Through the analysis of the overpass structure, a method for constructing overpass structures is proposed based on the directed acyclic graph, with the purpose of realizing efficient and high-quality modeling. Firstly, the two-dimensional raster data was preprocessed to extract effective road information. Secondly, a directed acyclic graphs (DAG) was constructed to express the topological relationship of overpass structure. Then, the height of each control point was calculated using the proposed height calculation method designed according to the structural characteristics, functional characteristics and related prior knowledge of the road. Finally, the overpass structure was constructed, based on the calculated road height and topological information with component units. The experiments selected three typical overpass structures in East China for testing. The results prove that the proposed method is advantageous in data acquisition and calculation accuracy and can help simplify the modeling process of overpass structures.

computer-aided modeling;heuristic modeling; urban road network; overpass structure; directed acyclic graph

TP 391

10.11996/JG.j.2095-302X.2020040583

A

2095-302X(2020)04-0583-10

2020-03-20；

2020-04-26

26 April，2020

20 March，2020；

国家重点研发计划基金项目(2016YFC0800106)；国家自然科学基金项目(61602146)；中央高校基本科研业务费专项资金项目(JZ2019YYPY0011)

National Key Research and Development Program of China (2016YFC0800106); National Natural Science Foundation of China (61602146); Fundamental Research Funds for the Central Universities (JZ2019YYPY0011)

王宇昆(1994-)，男，安徽安庆人，硕士研究生。主要研究方向为计算机图形与可视化。E-mail：wykhfut@163.com

WANG Yu-kun (1994-), male, master student. His main research interests cover computer graphics and visualization. E-mail：wykhfut@163.com

曹 力(1982-)，男，安徽绩溪人，副教授，硕士。主要研究方向为计算机图形、计算几何及数据可视化。E-mail：lcao@hfut.edu.cn

CAO Li (1982-), male, associate professor, master. His main research interests cover computer graphics, computational geometry and data visualization. E-mail：lcao@hfut.edu.cn