第7章 多边形拓扑生成

第7章 多边形拓扑生成 张宏 Zhanghong1118@126.com 基本概念 拓扑空间关系是一种对空间结构进行明确定义的 数学方法 具有拓扑关系的矢量数据结构就是拓扑数据结构。 拓扑数据结构描述了基本空间目标点、线、面之 间的关联、邻接和包含关系 拓扑空间关系信息是空间 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 的基础之一 C o v e r a g e 数 据 模 型 Coverage数据模型  Point  Arc/Line  Polygon Coverage数据文件  Tic  Bnd  Arc  AAT, PAT Coverage数据存储  Coverage文件可以管理point, line或polygon  一个Coverage文件可以存储point集合和线集合或线 集合和面集合，但不能同时存储点集合和面集合  Polygon Coverage将覆盖整个区域的，并将区域分隔成 为若干Polygon  Polygon之间不允许相互叠置  Coverage中的所有区域是由Polygon集合中的一部分 或全部构成 Coverage数据的创建  Coverage的创建使用BUILD 和 CLEAN 命令  CLEAN 尝试的去修补拓扑中存在的错误，包括移动点 和线的位置、点的合并、线的合并和打断  BUILD假设被拓扑数据已经是 “clean”，如果在拓扑 中遇到问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 和错误拓扑将失败  创建 Point, Arc和Polygon的基本属性表 拓扑生成算法的一般过程 数据预处理  弧段处理，使整幅图形中的所有弧段，除在端点处相 交外，没有其他交点，即没有相交或自相交的弧段  结点匹配，建立结点、弧段关系 拓扑构建  建立多边形，以左转算法或右转算法跟踪，生成多边 形，建立多边形与弧段的拓扑关系  建立多边形与多边形的拓扑关系 弧段——结点关系表 弧段号 结点号 0A 00N 10N 1A 10N 11N … … nA N0N N1N 结点——弧段关系表 弧段——多边形关系表 多边形——弧段关系表 结点数据结构 结点可以用来检测弧段与弧段的连接关系和多边形特征是 否能正确地完成 结点属性一般包括：  结点号  结点坐标  与该结点连接的弧段集合 结点可以用来描述如管线的交点、道路路口等现实世界的 特征对象 弧段数据结构 拓扑弧段指处于两个结点之间的点序列串 需要给弧段定义一个方向，可以定义为数字化弧 段时从一个结点到另一个结点的采点方向，或者 硬性定义一个方向 定义方向后弧段开始的结点就称为起始结点，弧 段结束的结点就称为结束结点，由起始结点到终 止结点的方向称为“起终方向”，由终止结点到 起始结点的方向称为“终起方向” 弧段起终方向左侧的多边形称为弧段的左多边形， 弧段起终方向右侧的多边形称为弧段的右多边形 空间实体的描述中的完整链 具有结点标识符和左右标识的链 弧段数据结构（续） 弧段一般包括：  弧段号  弧段节点坐标串  弧段起始结点  弧段终止结点  弧段左多边形  弧段右多边形 多边形数据结构 多边形是由一条或若干条弧段首尾相连接而成的 边线所包含的区域 内部包含有其它多边形的多边形一般称为复杂都 边形，被包含的多边形称为岛，没有岛的拓扑面 称为简单面 简单面 岛 复杂面 多边形数据结构（续） 对于多边形也可以定义正反方向，一般定义为：当沿多边 形的边界前进时，被弧段所包围的面域始终处于弧段的右 侧时的方向就是正方向，反之，则是反方向 对于多边形的外边界，顺时针方向是正方向，而对于内边 界逆时针方向就是正方向 多边形数据结构（续） 多边形一般包括：  多边形号  中心点坐标  组成多边形的弧段号集合  多边形岛的信息 考虑到组成弧段的方向和多边形顶点序列的方向存在的可 能的不一致性以及效率问题，可以改为记录下组成多边形 的弧段指针和方向性信息，即弧段与多边形的方向是否一 致 对于岛的信息则通过将构成多边形的边线分块来处理的方 式体现，比如多边形包含岛屿，则可以使多边形的外边界 成为多边形的第一部分，岛屿作为多边形的二、三、四等 部分的方式加以解决 弧段的预处理 拓扑关系自动建立的第一步就是处理弧段，使得弧段不存 在自相交和相交现象  直线段相交的判断方法  自相交弧段处理  弧段相交打断处理 结点匹配 结点匹配就是把一定容差范围内的弧段的结点合并成为一 个结点，其坐标值可以是取多个结点的平均值，或者选中 一个结点作为所有结点的坐标区中心的坐标 悬挂结点 P （ 悬挂结点 ） 悬挂弧段 L （ 悬挂弧段 ） 弧段——结点关系表 弧段号 结点号 0A 00N 10N 1A 10N 11N … … nA N0N N1N 结点——弧段关系表 建立拓扑关系 结点弧段排序 左转算法跟踪多边形 岛的判断  岛的判断是指找出多边形互相包含的情况，即寻找复 杂多边形 结点排序 计算结点关联弧段的方位角，并按由小到大排序 N X 左转算法 从组成多边形边界的某一条弧段开始，如果该弧段与ｘ轴 正向夹角为最大，则从该弧段的同一结点出发的其他弧段 中，方向角最小的弧段是该多边形的后续弧段；如果该弧 段的方向角最小或介于同一结点的其他弧段方向角之间， 则最小夹角偏差所对应的弧段为多边形的后续弧段 2 A 1 A 5 A 4 A 5 N 3 A 2 N 4 N 1 N 3 N 左转算法（续） （1）顺序取一个结点作为起始结点，取完为止；取过该 结点的方位角最小的未使用过的或仅使用过一次，且使用 过的方向与本次相反的弧段作为起始弧段。 （2）取这条弧段的另一个结点，找这个结点关联的弧段 集合中的本条弧段的下一条弧段，如果本条弧段是最后一 条弧段，则取弧段集合的第一条弧段，作为下一条弧段。 （3）判断是否回到起点，如果是则形成了一个多边形， 记录下它，并且根据弧段的方向，设置组成该多边形的左 右多边形信息。否则转（2）。 （4）取起始点上开始的，刚才所形成多边形的最后一条 边作为新的起始弧段，转（2）；若这条弧段已经使用过 两次，即形成了两个多边形，转（1）。 左转算法（续） 2 A 1 A 5 A 4 A 5 N 3 A 2 N 4 N 1 N 3 N 课堂练习 N 1 N 8 N 2 N 9 N 7 N 5 N 4 N 3 N 12 N 11 N 10 N 6 N 16 N 13 N 14 N 15 A 8 A 7 A 2 A 4 A 1 A 10 A 9 A 6 A 5 A 3 N 17 A 11 弧段——多边形关系表 多边形——弧段关系表 岛的判断 根据左转算法，由单条弧段或多条弧段顺序构成 的且不与其他多边形相交的多边形即单多边形会 被追踪两次，形成两个多边形 一个多边形节点方向是顺时针的，另一个多边形 的节点方向是逆时针的 如果一个多边形包含另一个多边形，则必然是顺 时针多边形包含逆时针多边形 岛的判断（续） 岛的判断（续） 基于此岛的判断决定于多边形节点的顺序问题，多边形节 点的顺序问题可以通过计算多边形的面积加以解决 当多边形由顺时针方向构成是，面积为正；否则，面积为 负 岛的判断（续） （a）计算所有多边形的面积 （b）分别对面积为正的多边形和面积为负的多边形排序， 分别形成正多边形和负多边形集合 （c）如果负多边形集合的个数为0，结束程序；否则，从 面积为正的多边形集合中，顺序取出一个多边形，如果正 多边形已经都被访问过则程序结束 （d）依次从负多边形集合中取出负多边形，判断当前取 出的正多边形是否包含该负多边形，如果包含，就将该负 多边形加入当前取出的正多边形中，形成复杂多边形，设 置负多边形的组成弧段的拓扑信息，并从负多边形集合中 删除该负多边形。当所有负多边形都被访问一遍后转（c） 多边形包含关系判断 （a）判断负多边形面积的绝对值是否小于正多边 形的面积，如果不小于，则负多边形必不为正多 边形所包含，结束程序，否则执行下一步 （b）判断负多边形的最小外接矩形是否和正多边 形的最小外接矩形相交或被包含，如果不相交或 不被包含，则负多边形必不被正多边形所包含， 结束程序，否则执行下一步 （c）依次取负多边形上的点，判断点是否在正多 边形中，如果所有点都在正多边形中则负多边形 被正多边形所包含，否则，负多边形不被正多边 形所包含 弧段——多边形关系表 多边形——弧段关系表 小结 拓扑生成 算法 数据预处理 拓扑构造 弧段处理 结点匹配 多边形跟踪 岛的处理 相关算法 结点匹配算法 弧段相交的判断 弧段自相交的判断 多边形面积的计算方法