《空间数据拓扑关系的自动生成.doc》由会员分享，可在线阅读，更多相关《空间数据拓扑关系的自动生成.doc（14页珍藏版）》请在金锄头文库上搜索。
1、空间数据拓扑关系的自动生成冯文钊拓扑空间关系是一种对空间结构进行明确定义的数学方法，具有拓扑关系的矢量数据结构就是拓扑数据结构。矢量数据拓扑关系在空间数据的查询和分析过程中非常重要，拓扑数据结构是地理信息系统分析和应用功能所必需的，它描述了基本空间目标点、线、面之间的关联、邻接和包含关系。拓扑空间关系信息是空间分析、辅助决策的等的基础，也是GIS区别于CAD（计算机辅助设计）等的主要标志。拓扑空间关系的自动建立算法是GIS中的关键和难点算法之一，国内外对该问题一直在进行研究。而且，由于拓扑关系自动生成与维护的复杂性，GIS学术界研究人员针对GIS是否需要拓扑关系，问题是以一种什么样的方式来进行
2、拓扑空间关系表达。对于拓扑关系的自动建立问题，研究的焦点是如何提高算法与过程的效率和自动化程度，本章将讲述其实现的基本步骤和要点。拓扑关系自动生成算法的一般过程为：1 弧段处理，使整幅图形中的所有弧段，除在端点处相交外，没有其他交点，即没有相交或自相交的弧段。2 结点匹配，建立结点、弧段关系。3 建立多边形，以左转算法或右转算法跟踪，生成多边形，建立多边形与弧段的拓扑关系。4 建立多边形与多边形的拓扑关系。5 调整弧段的左右多边形标识号。6 多边形内部标识号的自动生成。事实上，拓扑关系的生成过程中还涉及到许多工作，例如弧段两端角度的计算、悬挂结点和悬线的标识、多边形面积计算、点在多边性内外的判
3、别等。第一节拓扑关系的计算机表达一、 拓扑结点结点用来描述如管线的交点、道路路口等现实世界的特征对象，结点可以用来检测弧段与弧段的连接关系和多边形特征是否能正确地完成。只与一条弧段相连接的起点或终点叫做悬挂结点。如图1所示P点就是悬挂结点：P（悬挂结点）图1 结点一般包括：结点号、结点坐标、与该结点连接的弧段集合，结点的数据结构可以表示如下：class Node private: long _ID; /结点号 Point * _Point; /指向结点坐标的指针 vectorArc * ArcCollection ; /与该结点相联接的弧段集合指/针 public: Node() ; /构造函
4、数 Node() ; /析构函数 other Method; /其他公共操作 二、 拓扑弧段及其表示拓扑弧段指处于两个结点之间的点序列串，可以给弧段定义一个方向，或者定义为数字化弧段时从一个结点到另一个结点的采点方向，或者硬性定义一个方向，定义方向后弧段开始的结点就称为起始结点，弧段结束的结点就称为结束结点，由起始结点到终止结点的方向称为“起终方向”，由终止结点到起始结点的方向称为“终起方向”。弧段起终方向左侧的多边形称为弧段的左多边形，弧段起终方向右侧的多边形称为弧段的右多边形，如果弧段的起始结点或终止结点只与一条弧段相关联，则该弧段称为悬挂弧段，如图2所示弧段L为悬挂弧段。一般可以通过标识
5、悬挂弧段来检测原始矢量数据的质量。 L（悬挂弧段） 图2 图1 弧段一般包括：弧段号、弧段节点坐标串、弧段起始和终止结点、弧段左右多边形，弧段的数据结构可以表示如下：class Arc private: long _ID; /弧段号 vector _Points; /弧段节点坐标串指针 Node * _start; /起始结点指针 Node * _end; /终止结点指针 Polygon * _LeftPolygon; /弧段左多边形指针 Polygon * _RightPolygon; /弧段右多边形指针 public: Arc() ; /构造函数 Arc() ; /析构函数 OtherMe
6、thod; /其他公共操作三、 拓扑面及其表示拓扑面是由一条或若干条弧段首尾相连接而成的边线所包含的区域，内部包含有其它拓扑面的拓扑面一般称为复杂面，被包含的拓扑面称为岛，没有岛的拓扑面称为简单面，如图3所示。对于拓扑面也可以定义正反方向，一般定义为：当沿拓扑面的边界前进时，被弧段所包围的面域始终处于弧段的右侧时的方向就是正方向，反之，则是反方向，如图4所示，箭头所指向的方向就是正方向，可以看出对于拓扑面的外边界，顺时针方向是正方向，而对于内边界逆时针方向就是正方向。 岛 简单面 复杂面图3 图4多边形一般包括：多边形号、中心点坐标、多边形属性数据、多边形的组成弧段号、多边形岛的信息，考虑到组
7、成弧段的方向和多边形顶点序列的方向存在的可能的不一致性以及效率问题，可以改为记录下组成多边形的弧段指针和方向性信息，即弧段与多边形的方向是否一致，对于岛的信息则通过将构成变形的边线分块来处理的方式体现，比如多边形包含岛屿，则可以使多边形的外边界成为多边形的第一部分，岛屿作为多边形的二、三、四等部分的方式加以解决。多边形的数据结构可以表示如下： class Polygon public: class Part private: typedef pairArc * ,bool ArcElement; vector _Arcs; public: Part() ; Part() ; OtherMeth
8、od() ; private: long _PolygonID; Point _CenterPoint; vector _Parts;public: Polygon() ; Polygon() ; OtherMethod() ; OtherProperty() ; 四、 拓扑结点、弧段和面之间的关系拓扑关系生成后，拓扑结点，拓扑弧段和拓扑面之间的关系如下几张表所示： 弧段号结点号A0A1.AnN00 N10N10 N11.NN0 NN1表1 弧段结点关系表结点号弧段号NiAi A j Ak 表2 结点弧段关系表弧段号左多边形号右多边形号A0A1.An PL0PL1.PLnPR0PR1.PRn表
9、3 弧段多边形关系表多边形号弧段号PiAi A j Ak 表4 多边形弧段关系表第二节 弧段处理算法拓扑关系自动建立的第一步就是处理弧段，使得弧段不存在自相交和相交现象。本小节主要解决弧段的处理问题。一、直线段相交的判断方法直线相交的判定方法有很多种，这里介绍较快的一种算法。设直线L过点和点，则直线L的方程可以表示为：，将直线方程化为参数方程有：其中。设有两条直线L1和L2，它们的参数方程分别为： 和 判断两线段有无交点的关键变为判断和是否符合不等式 且 。令：，有：，如果=0，说明两线段平行或者重合，没有交点，或者交点在两线段的头或尾上，否则如果满足不等式 且 ，两线段有交点，交点在两线段的
10、中间。二、自相交弧段处理具有自相交特征的弧段至少具有四个（结）节点，由三个点或两个点组成的弧段不可能自相交。依次取出每一条弧段，如果弧段的（结）节点个数不少于四个，就利用直线段相交的方法，对组成弧段的各直线段进行判断，如果相交，将线段断开为两条，自相交的弧段可能不止有一处相交，可以通过递归的方法来将弧段分开，算法如下：List Arcs；/ 弧段集合List NewArcs；/ 处理后的弧段集合void BreakArc(Arc *arc) Arc * first=0； /打断后的第一部分 Arc * second=0； /打断后的第一部分 bool IsSelfCross=false； in
11、t LineCountofArc=弧段所包含的直线段数目； for(int i=0；iLineCountofArc-2；i+) for(int j=i+2；jLineCountofArc；j+) if(直线段i 和 直线段 j 相交) 将交点插如弧段，并在处将弧段断为两截，分别存入first 和second 中； IsSelfCross=true； Break； if(IsSelfCross) break； if(！IsSelfCross) NewArcs.push_back(arc)； else SelfCrossDeal(first)； SelfCrossDeal(second)； void DealSelfCross() typedef list:iterator Position; for(Position ite=Arcs.begin()；ite!=Ar
