第三章+空间数据结构

1、矢量结构和栅格结构 Real worldGridPointLineAreaValue=0=1=2=3RowColumnTrianglesHexagons 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 6

2、 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 7 4 4 4 4 4 4 7 7 7 7 4 7 7 7 4 4 4 4 8 7 7 8 0 8 4 0 8 7 7 8 0 8 8 0 0 8 0 0 8 8 7 8 8 8 8 8 0 0 0 0 8 8 8 8 0 0 0 0 0 8 8 8 （a）点 （b）线 （c）面1 pixel = 10mX10m 分辨率分辨率 = 10m10M10M1 Pixel例如：中心点O落在代码为C的地物范围内，按中心点法的规则，该矩形区域相应的栅格单元代码为C例如：所示的例子中，显见B类地物所占面积最大，故相应栅格代码定为B 。例如

3、：假设A类最重要的地物类型，即A比B和C类更为重要，则栅格单元的代码应为A例如：可记面积最大的两类BA，也可以根据B类和A类所占面积百分比数在代码中加入数字 0000000200010000203300000203330022220302022222002002222222000022220330020000333320000033332000000000n链式编码又称为弗里曼链码弗里曼链码（Freeman，1961）或边界链码边界链码。主要记录线状地物或面状地物的边界,忽略空白区域。它把线状地物或面状地物的边界表示为：由某一起始点开始并按某些基本方向确定的单位矢量链。前两个数字表示起点的行列

4、号，从第三个数字开始的每个数字表示单位矢量的方向。n例如，确定原点为像元（10，1），则某个多边形边界按顺时针方向的链式编码为：10，1，7，0，1，0，7，1，7，0，0，2，3，2，2，1，0，7，0，0，0，0，2，4，3，4，4，3，4，4，5，4，5，4，5，4，5，4，6，6。其中前两个数字10 和1 表示起点为第十行第一列，从第三个数字开始每个数字表示单位矢量的方向，八个方向以07 的整数代表。n优点：链式编码对多边形的表示具有很强的数据压缩能力，且具有一定的运算功能，如面积和周长计算等，类似于矢量数据结构，比较适合于存储线和面图形数据。探测边界急弯和凹进部分等都比较容易，比较适

5、于存储图形数据。n缺点：对叠置运算如组合、相交等则很难实施，对局部修改将改变整体结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的公共边界被重复存储会产生冗余。按第一种编码方法，代码,个数，代码,个数此数据游程长度编码：（0，1），（4，2），（7，5）； 4，5），（7，3）；（4，4），（8，2），（7，2）；（0，2），（4，1），（8，3），（7，2）；（0，2），（8，4），（7，1），（8，1）； (0，3)， (8，5)； (0，4)， (8，4)； (0，5)， (8，3)。用44个整数表达了原始数据中的64个栅格。按第二种编码方法，代码代码,（终止）位置，代码（

6、终止）位置，代码, （终止）位置（终止）位置此数据游程长度编码（沿列方向）：（0，1），（4，3），（7，8）（4，5），（7，8）；（4，4），（8，6），（7，8 ）；（0，2），（4, 3）（8，6），（7，8）（0，2），（8，6），（7，7），（8，8）；（0，3），（8，8）；（0，4，（8，8）；（0，5），（8，8）n属性的变化愈少，行程愈长，压缩比例越大，即压缩属性的变化愈少，行程愈长，压缩比例越大，即压缩比的大小与图的复杂程度成反比。比的大小与图的复杂程度成反比。n优点优点n压缩效率较高（保证原始数据不丢失），易于检索，叠加、合并等操作，运算简单。n缺点缺点n只顾及单行单列

7、，没有考虑周围的其他方向的代码值是否相同。n对于图斑破碎，属性和边界多变的数据压缩效率较低，甚至压缩后的数据量比原始数据还大。 0 4 4 4 4 4 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 8 4 4 4 8 8 8 8 8 7 7 4 4 7 7 7 7 7 7 7 7 7 7 8 8 8 8 0 8 0 0 8 7 8 8 8 8 8 8 8 8 8 8 其块码编码为：(1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7),(1,6,2,7),(1,8,1,7),(2,1,1,4),(2,4,1,4),(2,5,1,4),(2,8,1,7),(

8、3,1,1,4),(3,2,1,4),(3,3,1,4),(3,4,1,4),(3,5,2,8),(3,7,2,7),(4,1,2,0),(4,3,1,4),(4,4,1,8),(5,3,1,8),(5,4,2,8),(5,6,1,8),(5,7,1,7),(5,8,1,8),(6,1,3,0),(6,6,3,8),(7,4,1,0),(7,5,1,8),(8,4,1,0),(8,5,1,0)。特点：特点： 具有可变分辨率，即当属性变化小时图块大，对于大块图斑记录单元大，分辨率低，压缩比高。小块图斑记录单元小，分辨率高，压缩比低,所以，与游程长度编码类似，随图形复杂程度的提高而分辩率降低。将一

9、幅栅格图象等分为四等分，逐块检查其格网属性值（或灰度）。如果某一子区的所有栅格的具有相同的值，则这个子区不再继续分割，否则还要把这个子区再分割为四个子区。这样依此地分割，直到每个子区都有相同的属性值或灰度为止。四叉树的树形表示：四叉树的树形表示： 用一倒立树表示这种分割和分割用一倒立树表示这种分割和分割结果。结果。根：整个区域根：整个区域高：深度、分几级，几次分割高：深度、分几级，几次分割叶：不能再分割的块叶：不能再分割的块树叉：还需分割的块树叉：还需分割的块 每个树叉均有每个树叉均有4 4个分叉，叫四叉个分叉，叫四叉树。树。A AA AA AA AA AB BB BB BA AA AB BB

10、 BA AA AB BB B0 01 12 23 3 其中最上面的结点叫根结点，它对应整个图形。此树共有4层结点，每个结点对应一个象限，如第2层4个结点分别对应于整个图形的四个象限，排列次序依次为南西（SW）、南东（SE）、北西（NW）和北东（NE），不能再分的结点称为终止结点（又称叶子结点），可能落在不同的层上，该结点代表的子象限具有单一的代码，所有终止结点所代表的方形区域覆盖了整个图形。从上到下，从左到右为叶子结点编号，共有40个叶子结点，也就是原图被划分为40个大小不等的方形子区（最下面的一排数字表示各子区的代码）。 0 4 4 7 7 7 7 7 4 4 4 4 4 7 7 7 4 4

11、 4 4 8 8 7 7 0 0 4 8 8 8 7 7 0 0 8 8 8 8 7 8 0 0 0 8 8 8 8 8 0 0 0 0 8 8 8 8 0 0 0 0 0 8 8 8 矢量数据的类型Buildings. PolygonStreams, LineWells, PointRoads, LineZoning, PolygonMAP SHEETS矢量表达形式矢量表达形式点：点：单独一对坐标(x、y)表示线：线：两对以上的坐标对(x1、y1)， (x2、y2), (xn、yn)表示。（弧、链）面：面：两对以上的坐标对(x1、y1)， (x2、y2), (xn、yn), (x1、y1)表

12、示。适合于表达有精确的形状和边界离散的实体适合于表达有精确的形状和边界离散的实体 (X,Y)(X2,Y2)(X3,Y3)(X4,Y4)(X5,Y5)LinePoint(X5,Y5)(X,Y)(X2,Y2)(X4,Y4)(X3,Y3)Polygon(X,Y)唯一标识码是系统排列序号；线标识码可以标识线的类型；起始点和终止点号可直接用坐标表示；显示信息是显示时的文本或符号等；与线相联系的非几何属性可以直接存储于线文件中，也可单独存储，而由标识码联接查找。 图形数据线与多边形之间的树状索引点与边界线之间的树状索引 形成的文件记录 树状索引编码消除了相邻多边形边界的数据冗余和不一致的问题，在简化过于复

13、杂的边界线或合并相邻多边形时可不必改造索引表，邻域信息和岛状信息可以通过对多边形文件的线索引处理得到，但是比较繁琐，因而给相邻函数运算，消除无用边，处理岛状信息以及检查拓扑关系带来一定的困难，而且两个编码表都需要以人工方式建立，工作量大且容易出错。 应用节点号节点号坐标坐标1x,y2x,y3x,y4x,y5x,y6x,y7x,y8x,y9x,y弧段弧段号号起始起始节点节点起始起始节点节点左多左多边形边形右多右多边形边形112012230234513456245783068940714108473092521105843113602126904节点表节点表弧段表弧段表12345678912345

14、69107812341112三个四个节点号节点号坐标坐标1x,y2x,y3x,y4x,y5x,y6x,y7x,y8x,y9x,y弧段弧段号号起始起始节点节点起始起始节点节点左多左多边形边形右多右多边形边形中间中间点点11201p122302p234513456245783068940714108473092521105843113602126904p12节点文件节点文件弧段文件弧段文件1234567891234569107812341112POLYVRT（Polygon-Converter)结构结构:多边形多边形号号弧段号弧段号面面积积周周长长11, 9, 3, 722, 11, 4, 933

15、, 10, 5, 844, 12, 6, 10多边形文件多边形文件ID坐标坐标12弧段坐标文件弧段坐标文件POLYVRTPOLYVRT（Polygon-Converter)Polygon-Converter)结构结构: :美国计算机图形及空间分析实验室研制，是美国计算机图形及空间分析实验室研制，是当今各种图形数据结构的基本框架（链状双当今各种图形数据结构的基本框架（链状双重独立式重独立式 ）。优点优点缺点缺点矢量矢量数据数据结构结构1. 数据结构严密，冗余度小，数据量小2. 空间拓扑关系清晰，易于网络分析；3. 面向对象目标的，不仅能表达属性编码，而 且能方便地记录每个目标的具体的属性描述 信

16、息；4. 能够实现图形数据的恢复、更新和综合；5、图形显示质量好、精度高。1. 数据结构处理算法复杂2. 叠置分析与栅格图组合比较难；3. 数学模拟比较困难；4. 空间分析技术上比较复杂，需要更复杂的软、硬件条件；5. 显示与绘图成本比较高。栅格栅格数据数据结构结构1. 数据结构简单，易于算法实现；2. 空间数据的叠置和组合容易，有利于与遥感数据的匹配应用和分析；3. 各类空间分析，地理现象模拟均较为容易；4. 输出方法快速简易，成本低廉。1. 图形数据量大，用大像元减小数据量时，精度和信息量受损失；2. 难以建立空间网络连接关系；3. 投影变化实现困难；4. 图形数据质量低，地图输出不精美。

17、二、数据转换二、数据转换1 1、矢量、矢量栅格转换栅格转换1、射线算法单个多边形的转换多个多边形的转换 2、栅格、栅格矢量转化矢量转化第四节第四节 其他数据结构其他数据结构1、矢栅一体化数据结构2、镶嵌数据结构3、三维数据结构 概念：概念：将矢量面向地理实体的方法和栅格像元充填的方法结合起来表达地理实体的数据结构。从本质上说，是一种以矢量的方式来组织栅格数据的数据结构。基本思路：基本思路：面状实体的边界采用矢量数据结构描述，而其内部采用栅格数据结构表达；线状实体一般采用矢量数据结构表达，同时将线所经过位置以栅格单元填充。实体点则同时描述其空间坐标和栅格单元位置。理论基础：理论基础：多级格网方法

18、三个基本约定线性四叉树编码（1 1）地面上的点状地物是地球表面上的点，）地面上的点状地物是地球表面上的点，它仅有空间位置，没有形状和面积，在计算机它仅有空间位置，没有形状和面积，在计算机内部仅有一个位置数据。内部仅有一个位置数据。（2 2）地面上的线状地物是地球表面的空地面上的线状地物是地球表面的空间曲线，它有形状但没有面积，它在平间曲线，它有形状但没有面积，它在平面上的投影是一连续不间断的直线或曲面上的投影是一连续不间断的直线或曲线，在计算机内部需要用一组元子填满线，在计算机内部需要用一组元子填满整个路径。整个路径。（3 3）地面上的面状地物是地球表面的）地面上的面状地物是地球表面的空间曲面

19、，并具有形状和面积，它在平空间曲面，并具有形状和面积，它在平面上的投影是由边界包围的空间和一组面上的投影是由边界包围的空间和一组填满路径的元子表达的边界组成。填满路径的元子表达的边界组成。 （1）它保留了矢量的全部性质，以目标为单元直接聚集所有的位置信息，并能建立拓扑关系；（2）它建立了栅格与地物的关系，即路径上的任一点都直接与目标建立了联系。矢栅一体化数据结构域的特征矢栅一体化数据结构域的特征3 33 34 43 33 34 44 42 23 33 34 44 44 42 23 33 34 44 42 23 34 44 42 22 22 21 12 2提问：请说出上述两种方法的坐标记录上的差异提问：请说出上述两种方法的坐标记录上的差异TIN(Triangulated Irregular Networks)TIN(Triangulated Irregular Networks)表表达形式达形式 213131212131312112131312111)()(yxyxxzxzyyzyzyxxZZ(X1,Y1,Z1)(X2,Y2,Z2)(X3,Y3,Z3)P(X,Y,Z);1331122113311221133112