拓扑数据结构.ppt

12023年3月2日18时39分拓扑型数据结构Topological Data Structure 最广泛使用的矢量数据模型，借用了拓扑学（Topology）的原理来描述空间事物。 通过拓扑关系，识别地图中的空间数据关系。不仅记录空间位置和几何特性，还记录空间关系自身自身邻接邻接相交相交相离相离包含包含重合重合点点-点点点点-线线点点-面面线线-线线线线-面面面面-面面22023年3月2日18时39分拓扑:移动结点无拓扑:移动结点32023年3月2日18时39分拓扑数据结构42023年3月2日18时39分链节点的拓扑数据结构(chain-node topological data structure）线节点式拓扑结构的四原则：方向性（线必定从起结点开始到终结点结束）连接性（线和线的连接处必定是结点）围合性（面必定是由线围合而成）相邻性（线必定有左多边形、右多边形）52023年3月2日18时39分起点中间点弧段3弧段2终点弧段1点面线点、线、面之间的拓扑关系点：孤立点、线的节点node、中间点Vertex 线：两节点之间的有序弧段 面：若干弧段组成的多边形62023年3月2日18时39分ebc41325ABC76Dada: 结点号A: 多边形号1: 弧段号弧段数字化方向链拓扑表链右面左面起点终点1Aca2BAbc3CAba4Cda5BCdb6BDee7Bdc多边形拓扑表（面-链关系）多边形链数链A3-1,-2,3B42,-7,5,0,-6C3-3,-5,4D16节点拓扑表（点和链的关系）结点链a1,3,4b2,3,5c1,2,7d4,5,7e672023年3月2日18时39分网络的拓扑结构线段号 起结点 终结点 1 A D 2 B F 3 C D 4 D E 5 E F 6 F G 7 E J 8 F J 9 H I 10 I J 11 D I 12 I K 13 J L结点号 线段号 A 1 B 2 C 3 D 1, 3, 4, 1, 1 E 4, 5, 7 F 2, 5, 6, 8 G 6 H 9 I 9, 10, 11, 12 K 12 L 13ABCDEFGHIJKL1234567891011121382023年3月2日18时39分拓扑数据结构的优缺点拓扑数据结构特点：空间关系明确，不完全依赖于具体的坐标位置。多边形的公共边界、网络的结点表达简单，便于分析、查询，尤其是点、线、面之间的相邻关系的查询和分析。优缺点：图形的修改方便，可由软件检查数据输入的错误，容易保证数据质量便于叠合分析、网络分析等数据结构复杂，软件复杂建立拓扑关系需花计算时间（当地图覆盖范围很大，数据量很大时）