拓扑关系

数字地图中拓扑关系的分析摘要：数字地图中数据的存储方式涉及到它的邻近关系的分析也就是地理信息系统中拓扑关系的分析，又数字地图是GIS输入、输出的主要形式，数字地图通过内业矢量化或全野外采集的方式形成后，数据的关系依靠拓扑技术进行处理。因此，生产高质量、符合GIS要求的数字地图产品是GIS的一项重要基础工作。本文论述了数据中点、线、面之间的关系，制定判定法则判定它们的拓扑关系或添加一定的关系，使大量杂乱无章的数据建立或转换成另一种拓扑关系达到处理信息的目的。特别就“交点计数检验法”进行了完善，保证了各种特殊情况处理方法的正确性。根据判别规则和方法，可以实现“缓冲区分析”、“自动裁剪线”、“自动形成封面”等拓扑处理功能。关键词：数字地图；GIS软件；拓扑关系；交点计数检验法引言我主要系统地介绍局部拓扑技术中用到的概念、结论及其判定法则。1拓扑技术的基本概念拓扑关系中数据只有点、线、面3种实体，其主要关系有：点与点、点与线、点与面、线与线的关系。以及由此派生的关系：线与面、面与面的关系。点是指具有三维坐标的空间点位；线是带有方向性的线段；面是多边形表示的封闭区。2拓扑关系（1）点与点的关系有：①重合；②不重合。（2）点与线的关系主要有：①点在线上，点在线上又包含有a.点在线的两个端点之一，b.点在线中间，c.点在线的延长线上；②点在线的左（右）侧。（3）点与面的关系有：①点在面内；②点在面外；③点在面的边界线上。（4）线与线的关系有：①平行，线与线平行包含有a.完全重合，b.部分重合，c.包含，d.不重合；②相交，线与线相交包含有a.实交，b.半虚交，c.完全虚交。（5）线与面的关系有：①相交；②相离；③包含。（6）面与面的关系有：①相交；②相离；③包含。3拓扑关系判定法则怎样使一些比较杂乱的数字化数据整理成符合GIS格式的数据的过程，以及其它拓扑处理的过程，就是判定点、线、面的拓扑关系及添加一定的点、线、面，或者把一种拓扑关系转变成另一种拓扑关系，或者增加一些拓扑关系的过程（下面用到的“ε”表示极小的正数。)（1）点与点的关系判定法。计算A、B两点的距离S，①如果s＜ε，则点A、B重合；②如果s＞ε，则点A、B不重合。（2）点与线的关系判定法。需要计算点P到线AB的距离S，计算顺时针夹角α=∠PAB、β=∠ABP，①s＞ε和0＜α＜180，则点P在线AB的左侧；②s＞ε和180＜α＜360，则点P在线AB的右侧（图1a）；③s1＜ε，则点P与点A重合,s2＜ε，则点P与点B重合。点在线上的判定：需求点P到线AB的垂足点P1，计算点P到点P1的距离S1、点P1到点A的距离S2、点P1到点B的距离S3、点A到点B的距离S4；④S1＜ε和|S2＋S3-S4|≤ε，则点P在线AB的中间（图1b）；⑤S1＜ε和|S2＋S3－S4|≥ε，则点P在线AB的延长线上（图1c）。（3）线与线的关系判定法。A平行。用上面“点与线的关系判定法”判别、A、B两点与线CD的关系。①完全重合：点A与点B重合且点C与点D重合，则线AB与线CD同相完全重合；点A与点D、点B与点C重合，则线AB与线CD反相完全重合（图2a）②平行部分重合：点A（B）位于线CD中间且点B（A）位于线CD延长线上，则线AB与CD平行部分重合（图2b）；③包含：点A、B（C、D）均位于线CD（AB）中间，则线CD（AB）包含线AB(CD)(2c图；)④平行且不重合：以上三项都不成立时，求取线AB与线CD的方位角αAB、αCD，|Αab—αCD|≤ε或|αAB－αCD±180°|≤ε，则线AB与线CD平行（图3a）。B相交。判定线AB与线CD不平行，则相交，求出交点坐标P，根据“点与线的关系判定法”判定点P与线AB和线CD的关系。⑤实交：点P在线AB与线CD的中间，不包含点P与点A、B、C、D任一点重合（如图3b）；⑥半虚交：点P不同时在线AB和线CD上，即包含线相接（图3c）；⑦完全虚交：点P同时不在线AB和线CD上（图3d）。（４）点与面的关系判定法。这种判断法，可参见《地矿测绘》2000年第3期15页“点与多边形的求交算法”：①夹角之和检验法，②交点计数检验法。但“交点计数检验法”不够完善。其论点为：“求射线与多边形边的交点个数。若个数为奇数时点在多边形内，否则，点在多边形外。”我们认为：这个论点不适合于各种特殊情况，所作的射线与多边形的某个顶点相交时，无论是否把该点记入交点个数之内其结论都是不正确的，现举例如下：①当把射线与多边形线的顶点相交的点不计入交点个数内时，则会把如图4a的点P判断为不属于面内。不计顶点A时交点个数为3-1=2是偶数，判出点P不属于多边形内，显然是错误的；②当把射线与多边形线的顶点相交的点计入交点个数内时，其判断法则也不正确（图4bA）。当把顶点计入交点个数时，其交点个数为4，根据其判别法则判定点P在多边形之外，显然也是错误的。我认为：应在“交点计数检验法”后面附加二项条件：①多边形的某条边包含在射线内，判定与此边相连的前后线段位于射线的同一侧还是两侧，同一侧时计交点数为2，否则为1；②多边形的顶点而非边在射线上，判定与此点相连的两边位于射线的同一侧还是两侧，同一侧时计交点数为21，否则为1。该法可适合于任何复杂的多边形情况，分析如下：①如图4aA，多边形中与顶点A相连的两线段分居射线PF两侧，则该交点计数为1，B、C两点分别记数1，则交点总数为1＋1＋1=3为奇数，判定点P在多边形内；②如图4b，多边形中与顶点A相连的两线段居射线PF的同一侧，则记该交点个数为2，B、C、D点分别记数1，交点总数为2＋1＋1＋1=5，判定点P在多边形内；③如图4c，多边形中线段AB的前后线段位于射线同一侧，则记该交线的交点数为2，C、D、E点分别记交数1，交点总数为2＋1＋1+1=5为奇数，判定点PD多边形内；④如图，4d多边形中线段AB的前后段位于射线两侧，则记该交线的交点数为1，C、D点分别记交点个数1，交点总数为1+1＋1=3，为奇数，判定点在多边形内。综合上述几个特例可以看出，该判别法对任何特殊情况均可使用，不致于使编制的程序在特殊情况下会出现意想不到的错误或是死循环。（５）线与面的关系判定法。判别线与面的关系，其实就是判别线与多边形边界所有点线的关系，所以只要利用上面的点线关系判定法进行判别即可判别线与面的：“①相交；②相离；③包含”关系。（６）判别面与面的关系。判别面与面的关系，其实就是判别一个面的多边形边界点线与另一个面上多边形的边界点线的关系：①相交，即只要判定一个多边形的线与另一个多边形的线有实交点即可；②相离，即只要判定一个多边形的所有点均在另一个多边形之外及另一个多边形的所有点均在这个多边形之外，且这个多边形的所有线段与另一个多边形的所有线没有实交点；③内含，即只要判定一个多边形的所有点在另一个多边形内，且两个多边形之间的所有线没有实交点即可。4结论通过以上拓扑关系的分析，可以实现如“缓冲区分析”、“自动裁剪线”、“自动形成封闭面”等拓扑处理功能，从而达到数据以及信息处理的目的。