基于拓扑原子事件的拓扑关系局部更新技术

夏晨翕，代琬璐，陈 霄，胡 奇

1. 中国人民解放军31680部队，四川 成都 611200；

2. 西南交通大学 地球科学与环境工程学院，四川 成都 611756；

3. 西安椤析时空软件科技有限公司，陕西 西安 710048

0 引 言

空间关系包括度量、顺序和拓扑3种关系，这些基本关系都是空间数据组织、查询、分析和推理的基础。拓扑关系是GIS发展的重要标志，代表了语义层次上最重要的一类空间关系[1]。在GIS中，地理实体间的拓扑关系能清楚地反映实体间的关系和逻辑结构。空间数据存入数据库之后，为了维持数据的现势性和数据质量，需要对原有点、线、面要素数据进行编辑更新操作，常常会引起拓扑关系的改变，在修改空间要素数据后，一般需要对更改后的空间数据进行拓扑重构[2]。

在拓扑的局部更新中，国外学者PAPADIAS和THEODORIDIS提出了空间关系最小边界矩形（MBR）[3]使得空间拓扑关系局部更新理论研究进入新阶段。国内的程双伟在MBR的基础上，结合优化的拓扑生成相关算法，在拓扑关系更新中提出了一种简便、灵活的局部拓扑更新方法，从而使局部拓扑更新成为可能[4]。徐立在对局部拓扑更新中，提出了两种思路，一是确定拓扑发生变化的范围，在变化范围内进行拓扑局部更新；二是将拓扑更新细分为原子事件，根据拓扑编辑实时更新拓扑数据，并对两种算法进行比较，通过实例进行算法验证[5]。

拓扑原子事件是指在进行拓扑编辑过程中对拓扑要素的最基本操作[5]，只能同时编辑一种要素，拓扑原子事件不可再分，并且具有原子性和独立性。地理网络拓扑关系的原子事件分为两大类：结点拓扑原子事件和弧段拓扑原子事件[6-7]。针对结点拓扑原子事件的操作包括：结点的添加、删除、修改；针对弧段拓扑原子事件的操作包括：弧段的添加、删除、修改。本文重点根据地理事件对地理网络拓扑关系的影响规律，研究地理事件（点、线）引起的地理网络拓扑关系局部重构的方法，设计相应算法，并结合实际地理网络数据，进行算法验证。

1 算法原理

几何数据变化能够影响拓扑关系发生变化，所以可以利用几何数据变化规律找出拓扑关系发生变化的要素，进而确定所需要素，再进行拓扑更新操作。

首先对变化要素最小外接矩形范围内的所有要素进行相交断链处理，此时可能会有新的结点产生。然后将编辑要素时新增或删除的结点添加到相交断链产生的结点集合中。与这些结点相关联的弧段及结点本身需要进行拓扑重新构建，与此类结点相邻的其他结点不需要拓扑重构，只需要修改拓扑信息即可。依据此规律很容易确定哪些要素需要进行拓扑更新操作，即变化区域的选定。最后再修改边界要素拓扑数据信息，保证拓扑重构区域和已有拓扑关系保持一致，局部更新完成（图1）。

图1 拓扑局部更新流程Fig.1 Topology local update process

2 变化范围提取

2.1 几何变化影响拓扑变化规律

在网络拓扑更新中，由于几何要素的变化而引起拓扑关系改变，如几何要素新增或删除时，变化结点的相邻结点和变化弧段的关联结点可以终止拓扑关系，变化沿弧段方向延伸。

2.2 结点分类

根据几何变化影响拓扑变化的规律，将参与局部拓扑更新的结点按以下形式分类。拓扑更新过程中，由于结点几何发生变化的结点为第一类结点；当结点拟合到已有结点上，可结点相关联弧段个数发生变化，结点同样归为第一类结点。如结点或弧段几何发生变化引起已有结点拓扑发生变化的结点归为第二类变化点。与第二类相邻但不是第二类或第一类的结点为第三类结点。

2.3 变化要素提取

由于此方式是根据结点要素变化情况提取变化要素，所以需要先确定变化要素区域内的结点分类情况。因此，在局部拓扑更新之前需要对变化要素最小外接矩形范围内的所有几何要素进行相交断链处理，再作结点拟合，根据分类准则依次区分第一类结点、第二类结点及第三类结点。

2.4 变化范围确定

在网络拓扑关系中，有些要素拓扑关系发生变化，需要修改拓扑数据，而有些要素间的拓扑关系发生改变，如结点的邻接、弧段的邻接关系，则不需要更新数据库[8]。按照是否需要更新数据将拓扑关系发生变化的要素分为两类，一是需要更新数据的要素，二是不需要更新数据但部分拓扑关系发生改变的要素。

1）拓扑更新范围确定。依据多边形追踪算法，按照分类的结点，从任意一个第二类结点出发，在弧段不经过第一结点的前提，经过网络中已有弧段，将所有第二类结点相连，变化要素始终位于搜索方向右侧，并且保证搜索区域的最小性，该过程围成的多边形区域为要素拓扑关系发生变化区域，如图2中黄色弧段围成的多边形区域，则此范围内要素拓扑关系需要全部重新构建。

2）参与拓扑更新计算范围确定。在第二类结点及更新数据范围的基础上，依据多边形追踪算法，从任意一个第三类结点出发，且弧段不经过第二类结点确定区域经过的弧段，保证搜索区域最小化的同时，按照拓扑关系更新范围方法确定区域的过程，构建新的范围，如图2中绿色弧段围成的区域，则在此范围内的所有要素拓扑关系发生变化，包括变化要素的相邻关系[9]，但只有部分要素需要更新数据库。

图2 拓扑局部范围图Fig.2 Local range of topology

2.5 范围边界悬垂弧处理操作

在选取要素变化范围时，出现悬垂弧的情况，需要对悬垂弧特殊记录。在后续选择的变化区域中更新拓扑时，悬垂弧需要作为已有要素不需要重新生成。在范围选取时，当变化要素较多时，可能会出现多边形内包含多边形的情况，即岛多边形，此时需要更新的变化要素是在岛内多边形以外的区域。如果岛内只存在单个结点或者是单弧情况，处理方法和悬垂弧相同。

2.6 特殊情况变化要素处理

1）结点移动。在网络拓扑关系中，结点移动前后，与该结点相关联弧段始终不与其他要素相交，则可以判断节点的移动没有影响网络拓扑关系的改变。此种情况只用对结点的几何坐标和属性信息进行修改，不需要更新拓扑关系。若结点的移动使得结点的关联弧段与其他要素相交，即网络拓扑发生变化，则需要将结点移动后的相关联的弧段与其最小外接矩形范围内要素进行相交断链处理，再确定拓扑关系变化区域，并对变化区要素作拓扑关系更新。

多边形拓扑关系中由于结点的移动操作，可能没有影响弧段和结点拓扑关系，但结点移动前后所在区域发生了变化。之前的方法便不能发现拓扑关系的改变，需要做特殊判断。判断的基本思路是：查找到移动结点和相关联弧段所在的最小多边形区域，如图3中左图结点A在多边形B外，右图结点A在多边形B内，当移动完成后再判断该结点和相关弧段所在的最小多边形区域。若两次区域相同，则判定该结点的移动没有引起拓扑变化；否则，多边形拓扑发生变化。当多边形拓扑发生变化时可以按照移动后结点及相关弧段的新增和移动前弧段删除进行拓扑更新操作。结点移动前后，结点所在最小多边形可以使用面积判断法。

图3 结点所在多边形位置确定Fig.3 Determination of polygon position of node

此外，也存在一种特殊情况：结点编辑使得该弧段所在多边形发生改变，弧段的拐点从多边形内移动到多边形外。此时可以使用结点替换操作，将替换的结点看成是第一类结点处理。

2）弧段几何编辑操作。对于弧段的编辑操作主要有对组成弧段的上点的几何位置修改和组成弧段上点的新增和删除。操作完成后，判断该弧段是否与其他要素相交，进而确定拓扑关系是否发生变化。若发生变化，则进行拓扑更新操作，否则不进行，只修改结点的几何坐标和属性信息。

3）弧段的移动操作。弧段的移动涉及至少两个结点的移动，需要确保两个结点在移动前后与关联弧段拓扑关系保持不变，且弧段不与其他要素产生新结点，拓扑才不会变化。实际应用中这种情况较少，所以弧段的移动一般看成是新弧段的添加和旧弧段的删除便可完成拓扑更新。

3 拓扑更新过程

需要更新的范围一经划定，就不必关注拓扑编辑的过程，只需要在范围内按照不同要素类型进行拓扑关系更新即可。此时应将范围内的全部要素进行拓扑关系重新生成，在生成过程中若遇到选定范围的边界处，只需要修改对应结点和弧段的拓扑信息，便能和原拓扑关系保持一致[10]。拓扑更新主要流程如图4所示。

图4 拓扑更新流程图Fig.4 Topology update flow chart

3.1 变化范围内要素处理

1）一般要素处理方法。对于变化区域多边形范围内的要素，主要包括第一类结点和与第一类点直接相关联的弧段要素。由于其几何数据都发生变化，并且引起了拓扑数据的变化，则对于这类要素按照网络拓扑关系进行拓扑构建。按照第一类结点的规定，是新增、删除或拟合操作的结点，则第一类结点中，对于新增和拟合到原有结点，直接相连的所有弧段需要重新生成，并重新生成拓扑关系。处理新增结点如果在已有弧段上，则需要找到新增结点所在的弧段。如新增结点为第一类结点，新增结点所在弧段的首末结点为第二类结点，按照结点分类操作处理即可[11]。对于拟合到已有结点，需要用新结点替换原有结点，给原有结点重新编号，当作第一类结点处理，并进行拓扑重构。

2）删除结点处理方法。弧段编辑过程中，一般相交断链之后会有结点新增，除悬垂弧情况等特殊情况之外，系统会自动删除结点操作，其他结点的删除更多的是手动删除。按照拓扑中对结点删除后的操作处理需要进行炸开操作，故处理方法稍不同于新增和拟合结点处理方法。

对于手动删除的结点，在拓扑关系中，结点的删除意味着该结点相邻的弧段不再连通，那么就应在删除结点处新增对应关联弧段数个结点，并对与删除结点相关联的弧段重新编号。对这类结点做特殊处理方法同结点删除操作一样。此处相当于悬垂弧情况，当需要使得其中的部分弧段相连，必须进行手动操作选择需要连接的弧段。

在删除结点处新增该结点相连弧段数个结点，并对相连的所有弧段重新编号，修改该结点相邻结点拓扑关系，同时删除原结点。其他处理过程和第一类结点拓扑生成相同。

对于变化区域内要素，除删除结点需要特殊处理外，其他所有要素不需要关注拓扑编辑过程，只需将区域内要素拓扑关系重新生成即可。当区域内拓扑重新生成完成后，将变化区域内要素的拓扑关系全部删除。

对于在范围内的第一类结点，需要全部重新生成并编号，并且与第一类结点关联的弧段应全部重新生成并编号，进行结点拟合操作，重构该范围内的拓扑关系，算法同网络拓扑关系生成过程。在变化区域内，存在不和第一类结点直接相连的弧段，即构成边界范围时形成的悬垂弧，则按边界要素处理，不参与拓扑重构。

3.2 变化范围编辑要素处理

在变化范围内的所有要素拓扑重构完成后，应和已有拓扑关系保持一致性，修改边界要素的关联信息。

1）结点修改。在局部拓扑关系发生变化的要素中，结点主要分为三类，变化区域内结点、变化区域边界结点和变化区域外结点。对于第一类结点，重构拓扑关系；第三类结点拓扑关系不需要更新操作；第二类结点没有进行拓扑重构，但关联关系发生了变化，需要进行结点修改操作，即修改结点表中结点关联弧段信息，以便实现变化区域内外拓扑一致性[12]。在网络拓扑关系中边界上存在的第三类结点拓扑信息不用拓扑更新操作。

2）弧段修改。在网络拓扑关系中，由于弧段没有记录左右多边形信息，则变化范围边界的弧段要素拓扑信息不更新。在多边形拓扑关系中，还应进行组成变化范围多边形弧段的修改操作，主要修改边界弧段的左右多边形信息[13]，此处需要注意边界构成中悬垂弧处理方法。当变化区域内重构的拓扑关系与变化范围外要素拓扑关系保持一致时，局部拓扑更新完成。

4 实验分析

拓扑数据更新主要是当局部要素几何信息发生变化后，可能影响范围内要素拓扑信息的变化，就需要对这些拓扑发生变化的要素进行拓扑更新，保证与全局要素的拓扑关系一致性。当一定区域内多个要素发生变化时，需要进行更大范围更新操作，本案例模拟多个局部拓扑要素发生变化后，对拓扑关系影响范围，并按照第3节方法更新拓扑要素。实验数据采用模拟地理网络数据，数据主要包括地理道路线要素。ArcMap中构建出地理网络数据，并新建点要素图层用来存储线弧段的首末结点以及相交断链产生的结点信息。为区分不同弧段，所有的弧段有唯一编号。

当对该区域要素进行相交断链处理后，之前存在相交的弧段会在交点处新建节点，并把弧段分成两部分。对于结点间存在的偏差，需要将小于阈值的结点作预处理操作，当对区域内所有相交断链后产生的结点进行匹配操作，从而构建网络拓扑关系。有关网络拓扑关系构建算法比较完善，此处不再过多赘述。

本例中进行的操作包括弧段添加、弧段删除以及结点删除。确定了变化要素后，将变化要素与其最小外接矩形范围内所有要素进行相交断链处理，过程同弧段相交断链处理。再将新增或删除的结点加入第一类结点中。按照第二类结点分类依据，分别找出所有第二类结点。按照前述的变化范围选取方法，找出所有拓扑关系发生变化并需进行拓扑更新的要素。如图5高亮弧段为变化要素影响的拓扑范围，其中存在的悬垂弧做特殊标记，则高亮范围内所有要素需重新构建拓扑关系。

图5 基于网络数据相交断链的结点分布和拓扑更新范围Fig.5 Distribution of nodes and topology update scope based on network data intersection and chain break

对应变化范围内的所有要素需要全部重新生成，再由拓扑更新算法对区域内所有要素进行拓扑重构。在拓扑构建过程中，遇到更新范围边界时，需要修改第二类结点的关联弧段信息，其他边界弧段在网络多边形生成过程中不需要进行弧段信息修改操作即可完成拓扑更新，并保持更新范围内外拓扑关系的一致性（图6）。

图6 拓扑发生变化后要素分布Fig.6 Feature distribution after topology change

依据局部拓扑变化规律，进行局部拓扑更新要素范围划定，对几种特殊情况进行分述，使得此方法划定范围更准确。实验使用模拟数据进行拓扑关系构建中关键算法实现，对局部拓扑更新区域选择或要素提取进行了示范，更近一步描述拓扑变化范围选取过程和方法。在拓扑范围确定过程中，如果范围出现岛多边形，在内部要素较多时对内部要素特殊标记效率较高，但当内部要素少时，效率反而不高。

5 结 论

本文运用地理网络模拟数据进行拓扑更新过程模拟操作，依据各个要素变化情况进行对比分析，从理论上分析当多种要素发生变化后，更新要素范围的确定过程和拓扑局部更新思路的确定过程。根据地理事件对地理网络拓扑关系影响规律，研究了点、线引起的地理网络拓扑关系局部重构的方法。从地理事件对地理网络拓扑关系影响变化规律出发，利用几何变化引起拓扑关系变化的方法，确定拓扑关系发生变化范围并提取变化要素，结合已有拓扑局部更新理论方法，对已有算法进行相应优化，研究设计出地理网络拓扑局部更新方法。