空间数据结构

第四章空间数据结构数据结构即数据的组织形式，是适用于计算机存储、管理、处理的数据逻辑表达。换句话说，是指数据以什么形式在计算机中存储和处理。空间数据结构是空间逻辑数据模型在计算机中的组织关系和编排方式。包括基于矢量模型的矢量数据结构、基于栅格模型的栅格数据结构和基于不规那么镶嵌模型的TIN的曲面数据结构等。4.1矢量数据结构矢量数据结构是对矢量数据模型进行数据的组织，通过记录坐标的方式尽可能精确地表示点、线、多边形等地理实体，坐标空间设为连续，允许任意位置、长度和面积的精确定义。其精度仅受数字化设备的精度和数值记录字长的限制。矢量数据矢量数据的类型Buildings.PolygonStreams,LineWells,PointRoads,LineZoning, PolygonMAPSHEETS 矢量结构允许最复杂的数据以最小的数据冗余进行存储，相对栅格结构来说，数据精度高，数据存储的冗余小，是高效的空间数据结构。分为实体数据结构和拓扑数据结构。实体数据结构实体数据结构中，空间数据按照根本的空间对象〔点、线或多边形〕为单元进行单独的组织，其中不包含拓扑关系信息，最典型的是所谓的面条〔spaghetti〕结构，又称为坐标序列法。常采用这种数据结构的有ArcGIS中的Shape文件和MapInfo的Tab文件等。〔49页〕点的表示线的表示面的表示矢量数据模型中单一空间实体的表达坐标序列法〔Spaghetti方式〕例如图形数据10：x1,y1；x2,y2；x3,y3；x4,y4；x5,y5；x6,y6；x7,y7；x8,y8；x9,y9；x10,y10；x11,y11；x1,y1。20：x1,y1；x12,y12；x13,y13；x14,y14；x15,y15；x16,y16；x17,y17；x18,y18；x19,y19；x20,y20；x21,y21；x22,y22；x23,y23；x8,y8；x9,y9；x10,y10；x11,y11；x1,y1。编码数据坐标序列法的优缺点优点：文件结构简单，易于实现以多边形为单位的运算和显示缺点：对于相连的线，交叉点要重复输入和存储；对于多边形其公共边也要重复输入和存储，从而产生数据冗余和分析处理不便的问题；对于复杂多边形，不能解决多边形中“岛〞、“洞〞之类的镶套问题，“岛〞或“洞〞只能作为单个的多边形来构造，没有和周围的多边形建立关系；很难检查多边形的边界正确与否，即多边形的完整性；每个多边形自成体系，缺少有关邻域的信息，使拓扑关系，即相邻关系很难跟踪。适用范围：制图及一般查询，不适合复杂的空间分析4.1.2拓扑结构编码法具有拓扑关系的矢量数据结构就是拓扑数据结构。拓扑数据模型是一种基于矢量的比较有效的数据模型，ArcGIS的Coverage就是一种拓扑数据结构。拓扑数据结构包括树状索引编码法、双重独立编码结构、链状双重独立编码结构等。其实质是通过地理实体之间的空间关系表示来线和多边形。根本概念弧段：构成多边形的线称为弧段，每个弧段可以有许多中间点。节点：两条以上弧段相交的点称为节点岛：由一条弧段组成的多边形称为岛或洞。简单多边形：多边形图中不含岛的多边形称为简单多边形。复合多边形：含岛的多边形称为复合多边形，包括为边界和内边界，岛可以看做复合多边形的内边界。1树状索引编码法〔层次索引法、索引式结构〕采用树状索引以减少数据冗余并间接增加邻域信息，方法是对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构树状索引编码法例如图形数据树状索引编码法例如线与多边形之间的树状索引树状索引编码法例如点与边界线之间的树状索引树状索引编码法例如形成的文件记录索引式

线与多边形之间的树状索引

点与多边形之间的树状索引

树状索引编码消除了相邻多边形边界的数据冗余和不一致的问题，在简化过于复杂的边界线或合并相邻多边形时可不必改造索引表，邻域信息和岛状信息可以通过对多边形文件的线索引处理得到，但是比较繁琐，因而给相邻函数运算，消除无用边，处理岛状信息以及检查拓扑关系带来一定的困难，而且两个编码表都需要以人工方式建立，工作量大且容易出错。2.双重独立编码结构美国人口调查局于1980年建立的双重独立地图编码系统。简称DIME(DualIndependentMapEncoding)，这种结构最适合于城市地理信息系统。线文件是双重独立编码结构的根本对象。线文件由线标识码、起始节点、终止节点、左多边形和右多边形组成；节点文件由节点的标识码、节点坐标及与该节点连接的线的标识码等；多边形文件由多边形标识码、组成该多边形的线标识码组成。C4N4C8C6P3C7N6C10N3C3N1P1C2N2C1P2C5N5P4P5C9N7线号起结点终结点左多边形右多边形C1N1N2P2P1C2N3N2P1P4C3N1N3P1ØC4N1N4ØP2C5N2N5P2P4C6N4N5P3P2多边形：多边形由一系列的相互连结的线组成，并通过其内部的唯一标识点来标识。标识点的标识码和该多边形属性表中的标识码相一致，由此建立的多边形空间信息和属性信息的关系。多边形线IDP1C1,C2,C3P2C1,C5,C4P3C6,C7,C8P4C5,C7,C10,C2….C4N4C8C6P3C7N6C10N3C3N1P1C2N2C1P2C5N5P4P5C9N7面拓扑节点坐标线N1X1,y1C1,C4,C3N2X2,y2C1,C5,C2N3X3,y3C2,C3,C10N4X4,y4C4,C6,C8….C4N4C8C6P3C7N6C10N3C3N1P1C2N2C1P2C5N5P4P5C9N7点拓扑补充：基于双重独立编码的拓扑检查从线文件中，找出与当前编辑的多边形相关的所有记录。如对上例中的P1进行检查，先在线文件中找出与p1有关的所有记录：线号起结点终结点左多边形右多边形C1N1N2P2P1C2N3N2P1P4C3N1N3P1ØC4N4C8C6P3C7N6C10N3C3N1P1C2N2C1P2C5N5P4P5C9N7补充：基于双重独立编码的拓扑检查2.如果P1在左〔右〕多边形的位置，将之与处在右〔左〕多边形处位置的多边形号相交换，同时也将该记录的节点号位置相应的交换；反之，顺序不变。线号起结点终结点左多边形右多边形C1N1N2P2P1C2N2N3P4P1C3N3N1ØP1C4N4C8C6P3C7N6C10N3C3N1P1C2N2C1P2C5N5P4P5C9N7补充：基于双重独立编码的拓扑检查从经过代码位置转换的记录中，任取一个起始节点作为起点，顺序连接各节点，使得节点能自行封闭，即N1N2N3N1。如果不能自动封闭，那么说明出现记录缺损或多余，线文件有错误。线号起结点终结点左多边形右多边形C1N1N2P2P1C2N2N3P4P1C3N3N1ØP1C4N4C8C6P3C7N6C10N3C3N1P1C2N2C1P2C5N5P4P5C9N73.链式双重独立编码结构链式双重独立编码是DIME数据结构的一种改进。在DIME中，一条边只能用直线两端点的序号及相邻多边形表示，而在链状数据结构中，将假设干条直线段合为一个弧段〔或链段〕，每个弧段可以有许多中间点。ARCGIS中的Coverage数据模型就是采用链式双重独立编码结构。拓扑结构的特点是:除结点外，每个空间对象都是由更根本的对象组成的。只有点的坐标是被实际存储的，其他复杂空间对象的坐标信息实际上是逻辑构成的。任一复杂对象能分解为一组结点及其拓扑关系的定义。这样，一个图层中存储的全部坐标信息就是结点的坐标，建立其他对象只是建立对这些坐标的引用。虽然建立拓扑结构需要额外的存储数据，但对坐标数据的存储却没有数据冗余的问题。拓扑结构编码是某些空间分析的根底。小结矢量数据结构特点：定位明显，属性隐含。其定位是根据坐标直接存储的，无需任何推算；属性那么一般存于文件头或数据结构中某些特定的位置上。这种特点使得矢量数据结构在图形运算的算法总体上比栅格数据结构复杂的多，在叠加运算、邻域搜索等操作时比较困难，有些甚至难以实现，但其也有便利和独到之处，在计算长度、面积、形状和图形编辑、几何变换操作中，矢量结构有很高的效率和精度。4.2栅格数据结构栅格结构是最简单最直接的空间数据结构，是指将地球外表划分为大小均匀紧密相邻的网格阵列，每个网格作为一个象元或象素由行、列定义，并包含一个代码表示该象素的属性类型或量值，或仅仅包括指向其属性记录的指针。栅格数据编码方法分为两大类：直接栅格编码〔完全栅格数据结构〕压缩编码方法〔压缩栅格数据结构〕链码游程长度编码块码四叉树二维行程编码4.2.1直接栅格编码直接编码就是将栅格数据看作一个数据矩阵，逐行〔或逐列〕逐个记录代码，可以每行都从左到右逐个象元进行记录，也可以奇数行地从左到右而偶数行地从右向左记录，为了特定目的还可采用其他特殊的顺序一些常用的栅格排列顺序4.2.2压缩编码方式压缩编码的目的就是用尽可能少的数据量记录尽可能多的信息，其类型分为信息无损编码:编码过程中没有任何信息损失，通过解码操作可以完全恢复原来的信息 信息有损编码:为了提高编码效率，最大限度地压缩数据，在压缩过程中损失一局部相对不太重要的信息，解码时这局部难以恢复

在地理信息系统中的压缩编码多采用信息无损编码，而对原始遥感影像进行压缩时也可以采取有损压缩编码方法。链码〔ChainCodes〕链式编码又称为弗里曼链码(Freeman，1961〕或边界链码。该编码方法将数据表示为由某一原点开始并按某些根本方向确定的单位矢量链。如：根本方向可定义为：东＝0，东南＝1，南＝2，西南＝3，西＝4，西北＝5，北＝6，东北＝7等八个根本方向。例如，确定原点为像元〔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表示起点为第十行第一列，从第三个数字开始每个数字表示单位矢量的方向，八个方向以0—7的整数代表。5555443355554432555553225555552276614433777144332221111122555551练习链码〔ChainCodes〕优缺点优点： 链式编码对多边形的表示具有很强的数据压缩能力，且具有一定的运算功能，如面积和周长计算等，探测边界急弯和凹进局部等都比较容易，比较适于存储图形数据。缺点： 对叠置运算如组合、相交等那么很难实施，对局部修改将改变整体结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的公共边界被重复存储会产生冗余。游程长度编码〔Run-LengthCodes〕 它的根本思路是：对于一幅栅格图像，常常有行〔或列〕方向上相邻的假设干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。所谓的游程〔行程〕是指栅格矩阵内相邻同值栅格的数量。游程长度编码〔Run-LengthCodes〕其实现方法有两种一种编码方案是，只在各行〔或列〕数据的代码发生变化时依次记录该代码以及相同的代码重复的个数，从而实现数据的压缩。另一种游程长度编码方案就是逐个记录各行〔或列〕代码发生变化的位置和相应代码

游程长度编码例如按第一种编码方法〔左上角坐标，沿行方向〕，此数据游程长度编码：〔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个栅格。游程长度编码例如〔1，0〕，〔2，4〕，〔4，0〕；〔1，4〕，〔4，0〕；〔1，4〕，〔5，8〕，〔6，0〕；〔1，7〕，〔2，4〕，〔4，8〕，〔7，0〕；〔1，7〕，〔2，4〕，〔3，8〕，〔8，0〕；〔1，7〕，〔3，8〕；〔1，7〕，〔6，8〕；〔1，7〕，〔5，8〕。按第二种编码方法，记录各行〔或列〕代码发生变化的位置和相应代码此数据游程长度编码〔左上角坐标，沿列方向〕：游程编码能否压缩数据量，主要取决于栅格数据的性质，通常可以通过事先测试，估计数据冗余度Re：Re=1-Q/mn式中：Q表示相邻属性值变化次数的累加和m表示行数n表示列数

当Re的值大于1/5时，表示栅格数据的压缩可取的明显的效果其压缩效果可以由压缩比来表征：S=m×n/K式中：K为游程总数m表示行数n表示列数

压缩比越大，表示压缩效果越好游程长度编码优缺点优点压缩效率较高，且易于进行检索，叠加合并等操作，运算简单，适用于机器存储容量小，数据需大量压缩，而又要防止复杂的编码解码运算增加处理和操作时间的情况缺点对于图斑破碎，属性和边界多变的数据压缩效率较低，甚至压缩后的数据量比原始数据还大。

块码〔ChainCodes〕 块码是游程长度编码扩展到二维的情况，采用方形区域作为记录单元，每个记录单元包括相邻的假设干栅格，数据结构由初始位置〔行、列号〕和半径，再加上记录单位的代码组成。块码编码例如其块码编码为：(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),(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)。四叉树编码 四叉树编码将整个图像区逐步分解为一系列仅包含单一类型的方形区域，最小的方形区域为一个栅格象元。

四叉树编码 其根本分割方法是将一幅栅格地图或图像等分为四局部。逐块检查其栅格属性值(或灰度)。如果某个子区的所有栅格值都具有相同的值。那么这个子区就不再继续分割，否那么还要把这个子区再分割成四个子区。这样依次地分割，直到每个子块都只含有相同的属性值或灰度为止。 四叉树编码例如

四叉树编码要求

采用四叉树编码时，为了保证四叉树分解能不断地进行下去，要求图像必须为2n×2n的栅格阵列，对于非标准尺寸的图像需首先通过增加背景的方法将图像扩充为2n×2n的图像。

生成四叉树主要有两种方法，即自上而下〔top-down〕和自下而上〔bottton-up〕。由上而下的方法运算量大，耗时较长。因而实践中可以采用从下而上的方法建立四叉树编码。对栅格数据按Morton码的顺序进行检测：如果每相邻四个栅格值相同那么进行合并，逐次往上递归合并，直到符合四叉树的原那么为止。这种方法重复计算较少，运算速度较快。四叉树的生成四叉树结构的编码方式四叉树结构按其编码的方法不同分为常规四叉树和线性四叉树：常规四叉树：除了记录叶结点之外，还要记录中间结点。结点之间借助指针联系，每个结点需要用六个量表达：四个叶结点指针，一个父结点指针和一个结点的属性或灰度值。这些指针不仅增加了数据贮存量，而且增加了操作的复杂性。常规四叉树主要在数据索引和图幅索引等方面应用。四叉树结构的编码方式线性四叉树：只存贮最后叶结点的信息。包括叶结点的位置〔莫顿码值〕、深度和本结点的属性或灰度值。所谓深度是指处于四叉树的第几层上。由深度可推知子区的大小。线性四叉树叶结点的编号需要遵循一定的规那么，这种编号称为地址码，它隐含了叶结点的位置和深度信息。最常用的地址码是二进制或十进制的Morton码。美国马里兰大学地理信息系统中采用的编码方式：该方法记录了叶子结点的地址和值，值就是子区域的代码，而地址码包括两个局部，由32位来表示〔二进制〕，最右边4位记录该叶子结点的深度，即处于四叉树的第几层上，有了深度即可推知子区域的大小；从右边第5位开始2n个字节记录叶子结点的路径，用以描述叶子结点的位置，0，1，2，3分别表示SW,SE,NW,NE；其余各位用0补齐。上图空白处叶子结点5，深度为3；路径为3，0，0；用马里兰大学的编码方式可以记为：0…….0〔22位〕；110000〔6位〕；0011〔四位〕栅格数据编码练习二维行程编码在生成线性四叉树之后，仍然存在前后叶节点的值相同的情况，因而可以进一步压缩数据，将前后值相同的叶节点合并，行程新的线性列表。〔见P101图4.14〕栅格数据压缩存储的编码方法AAAAARAAARAAARAARAAAAAAAAAGGAAGGGGGGGAGGGAGGAAAAAARAAAARAAARRAAA143258761234567801234567起点行列号，单位矢量R:(1,5),3,2,2,3,3,2,3链式编码游程长度编码逐行编码数据结构:行号,属性,重复次数1,A,4,R,1,A,4块状编码正方形区域为记录单元数据结构:初始位置,半径,属性(1,1,3,A),(1,4,1,A),(1,5,1,R),(1,6,2,A),…NESWNWSEGGGGAGGAAGAAA四叉树编码常见栅格压缩编码方法总结：链码的压缩效率较高，已经近矢量结构，对边界的运算比较方便，但不具有区域的性质，区域空间分析运算困难。游程长度编码既可以在很大程度上压缩数据，又最大限度地保存了原始栅格结构，编码解码十分容易。但对破碎数据处理效果不好。块码和四叉树编码具有区域性质，又具有可变的分辨率，有较高的压缩效率，但运算效率是其瓶颈。其中四叉树编码可以直接进行大量图形图像运算，效率较高，是很有前途的方法。其他压缩编码方式 还有很多编码方法，如傅立叶变换、小波变换、余弦变换等，常常用于遥感原始数据的压缩。由于它们多数是有损压缩，一般不用于需要进行分析的栅格数据。在四叉树根底上开展而来的八叉树目前也是研究热点之一。小结栅格数据结构属性明显，定位隐含：属性明显数据中直接记录了数据属性或指向数据属性的指针，因而我们可以直接得到地物的属性代码定位隐含所在位置那么根据行列号转换为相应的坐标，也就是说定位是根据数据在数据集中的位置得到的。栅格结构是按一定的规那么排列的，所表示的实体的位置很容易隐含在格网文件的存储结构中栅格模型矢量模型优点：（1）数据结构简单；（2）空间数据的叠置和组合十分容易方便；（3）各类空间分析都很易于进行；（4）数学模拟方便；（5）技术开发费用低。优点：（1）表示地理数据的精度较高；（2）严密的数据结构，数据量小；（3）用网络连接法能完整地描述拓扑关系；（4）图形输出精确美观；（5）图形数据和属性数据的恢复、更新、综合都能实现。缺点：（1）图形数据量大；（2）用大像元减少数据量时，可识别的现象结构将损失大量信息；（3）地图输出不精美；（4）难以建立网络连接关系；（5）投影变换花的时间多。缺点：（1）数据结构复杂；（2）矢量多边形地图或多边形网很难用叠置方法与栅格图进行组合；（3）显示和绘图费用高，特别是高质量绘图、彩色绘图和晕线图等；（4）数学模拟比较困难；（5）技术复杂，多边形内的空间分析不容易实现。※4.3矢量数据结构与栅格数据结构比较矢量数据模型与栅格数据模型比较从应用领域来看——栅格结构和矢量结构都有一定的局限性。一般来说，大范围小比例尺的自然资源、环境、农业、林业、地质等区域问题的研究，城市总体规划阶段的战略性布局研究等使用栅格模型比较适宜；城市分区或详细规划、土地管理、公共事业管理等方面应用矢量模型比较适宜。从数据来源来看——对于一个与遥感相结合的地理信息系统来说，栅格结构是必不可少的，因为遥感影像是以像元为单位的，可以直接将原始数据或经处理的影像数据纳入栅格结构的地理信息系统；而对地图数字化、拓扑检测、矢量绘图等，矢量数据结构又是必不可少的。※矢量数据结构与栅格数据结构的选择在GIS建立过程中，应根据应用的目的和应用的特点、可能获取的数据精度以及地理信息系统软件和硬件的配置情况选择适宜的数据结构。矢量与栅格一体化〔了解〕为了发挥矢量和栅格数据结构各自的特点，在两种数据的根底上开展了矢量—栅格一体化数据结构〔unifieddatastructure),这种空间数据结构的思想是通过同时记录多边形边界和边界中间包含的栅格地址，实现既保持矢量数据的特征又具有栅格数据的性质。根本思想：为了提高点、线和边界的表示精度，一般将点所在格网或线、边界通过的格网细分，根据精度要求可分为按照256×256或16×16将根本格网细分。根本格网和细分格网都采用线性四叉数编码，采样点和线目标与根本格网的交点用两个十进制Morton码表示。一、矢量与栅格一体化的概念为了建立矢量与栅格一体化数据结构，要对点、线、面目标数据结构的存储要求作如下的统一约定:对点状目标，因为没有形状和面积，在计算机内部只需要表示该点的一个位置数据及与结点关联的弧段信息。对线状目标，它有形状，但没有面积，在计算机内部需用一组元子来填满整个路径，并表示该弧段相关的拓扑信息。对面状目标，它既有形状，又有面积，在计算机内部需表示由元子填满路径的组边界和由边界组成的紧凑空间。4.4不规那么镶嵌数据结构4.4.1Voronio数据结构〔见教材106页〕4.1.2TIN数据结构TIN模型的数据存储方式比栅格数据复杂，它不仅要存储每个点的高程，还要存储其平面坐标、节点连接的拓扑关系，三角形及邻接三角形等关系。TIN模型在概念上类似于多边形网络的矢量拓扑结构，对于每个三角形、边和节点都对应一个记录，如下：三角形记录包括三个指向它三个边的记录的指针；三角形顶点邻接三角形ⅠabcⅡⅢⅡcdaⅠⅣⅢbecⅠⅤⅣⅣcedⅡⅢⅧⅤebgⅢⅥⅩⅥbhgⅤⅦ……………………边有四个指针字段，包括两个指向相邻三角形的指针和它的两个顶点的记录的指针；边顶点相邻三角形1abⅠ2acⅠⅡ3bcⅠⅢ……………每个节点包括三个坐标值的字段，分别存储X,Y,Z坐标。顶点xyzabcde※栅格数据模型和TIN数据模型的比较对地理空间的划分：TIN模型为不规那么三角形；而栅格模型为规那么格网；空间对象的表示：栅格数据模型既可以描述连续变化的地理现象，又可以表示离散的地理现象〔点、线、面〕，而TIN模型只能表示联系变化的地理现象；但TIN能精确地表示曲面类型地理现象的形状以及特殊的地形要素，比方山脊、山峰等，而栅格模型不能精确表示；外表模型的精度：栅格使用统一的CELL大小来表示，在地形平坦的地方，存在大量的数据冗余，而TIN具有随坡度变化而不同的点密度，在坡度变化大的地区点密度较高；栅格模型适合进行空间一致性分析、近邻分析、离散度分析及外表最低本钱分析，TIN模型适合进行坡度、坡向、体积计算和视线分析等4.5三维空间数据模型4.5.1三维空间的目标分类4.5.2八叉树数据结构4.5.3四面体格网在三维空间中，可将空间地物按维数分成零维〔点〕，一维〔线〕、二维〔面〕和三维〔体〕四大类。零维空间：有点状地物和用来表示与弧段的关联关系的结点两类目标。一维空间：有“拓朴弧段〞、“无拓朴弧段〞和线状地物。其中“拓朴弧段〞可以是构成多边形的边界线也可是构成各类网线〔如水系网、交通网、城市地下管网〕的网线段。二维空间：主要有三类目标，一个是构成面状地物的拓朴面片；第二个是像素，用它可组成面状要素；第三个是根据有限的离散数据建立数字外表模型。三维空间，有由假设干个面片或由数字立体模型表示体状地物；以及根据有限的三维空间离散数据建成的数字立体模型。4.5.1八叉树数据结构八叉树数据结构是三维栅格数据的压缩形式，是二维栅格数据中的四叉树在三维空间的推广，该数据结构是将所要表示的三维空间V按X、Y、Z三个方向从中间进行分割，把V分割成八个立方体，然后根据每个立方体中所含的目标来决定是否对各立方体继续进行八等分的划分，一直划分到每个立方体被一个目标所充满，或没有目标，或其大小已成为预先定义的不可再分的体素为止。三维空间体V及划分编码三维空间体V中的物体八叉树数据结构举例八叉树编码八叉树结构就是将空间区域不断地分解为八个同样大小的子区域(即将一个六面的立方体再分解为八个相同大小的小立方体)，同—区域的属性相同。八叉树主要用来解决地理信息系统中的三维问题。

八叉树的主要优点在于可以非常方便地实现有广泛用途的集合运算〔例如，可以求两个物体的并、交、差等运算〕而这些恰是其它表示方法比较难以处理或者需要消耗许多计算资源的地方。此外，由于这种方法的有序性及分层性，因而对显示精度和速度的平衡，隐线和隐面的消除等，带来了很大的方便，特别有用。4.5.2四面体格网四面体格网〔TetrahedralNetwork—TEN〕是将目标空间用紧密排列但不重叠的不规那么四面体形成的格网来表示，其实质是2DTIN结构在3D空间上的扩展。在概念上首先将2DVoronoi格网扩展到3D，形成3DVoronoi多面体，然后将TIN结构扩展到3D形成四面体格网〔见图示〕。四面体格网表示三维空间物体的例子四面体格网表示三维空间物体的例子的数据结构四面体格网由点、线、面和体四类根本元素组合而成。整个格网的几何变换可以变为每个四面体变换后的组合，这一特性便于许多复杂的空间数据分析。同时，四面体格网既具有体结构的优点，如快速几何变换、快速显示，又可以看成是一种特殊的边界表示，具有一些边界表示的优点，如关系的快速处理。矢量数据结构和栅格数据结构的相互转换是地理信息系统的根本功能之一，目前已经开展了许多高效的转换算法。但是从栅格到矢量数据的转换，特别是扫描图像的自动识别，仍然是研究的重点。4.6矢量数据结构与栅格数据结构的转换〔教材P164〕对于点实体，每个实体都仅由一个坐标对表示，其结构的转换不存在太大的技术问题。在这重点讲解一下线实体和多边形实体向栅格格式转换的过程。如下：4.6.1矢量格式向栅格格式的转换线实体向栅格格式的转换由于GIS中线实体是由顺次连接一组坐标点形成的折线段表达的，所以，线的栅格化可以分解为对做成线实体的折线段的栅格化。对于线段的栅格化，先使用点栅格化的方法，栅格化线段的两个端点，然后再栅格化线段的中间局部。而对于线段中间的局部的栅格化，需要分两种情况来处理:

设线段两端点的坐标分别为(x1,y1)和(x2,y2),栅格化后所队形的行列号分别为〔I1,J1)(I2,J2).那么行差为△I=︱I1-I2︱，列差为△J=︱J1-J2︱。分两种情况处理：一是列差大于行差△J>△I的情况，二是行差大于列差△I>△J的情况，运用扫描线算法实现。当△J>△I时，平行于y轴做每一列栅格的中心线，称为扫描线。求每一条扫描线与线段的交点，按点栅格化的方法将交点转换为栅格坐标。当△I>△J时，同理。△J>△I△I>△J多边形矢量格式向栅格格式的转换

内部点扩散算法射线算法和扫描算法边界代数算法1内部点扩散法每个面域多边形中选择一个内部点〔扩散种子〕；从种子点开始向8个邻域栅格扩散，分别判断8个栅格是否在多边形的边界上，有两种结果，一是在边界上，那么这个栅格不再作为种子；二是不再边界上，这个栅格将作为新的种子新的种子与原有种子一起继续参与扩撒运算重复〔2〕〔3〕，直到所有种子点填满该多边形为止。扩散算法程序设计比较复杂，需要在栅格阵列中进行搜索，占用内存很大。2射线算法射线算法可逐点判别数据栅格点在某多边形之外或在多边形内，由待判点向图外某点引射线，判断该射线与某多边形所有边界相交的总次数，如相交偶数次，那么待判点在该多边形的外部，如为奇数次，那么待判点在该多边形内部。射线算法要计算与多边形交点，因此运算量大。另一个比较麻烦的问题是射线与多边形相交时有些特殊情况如相切、重合等，会影响交点的个数，必须予以排除，由此造成算法的不完善，并增加了编程的复杂性。3扫描算法扫描算法是射线算法的改进，通常情况下，沿栅格阵列的行方向扫描，在每两次遇到多边形边界点的两个位置之间的栅格，属于该多边形。扫描算法省去了计算射线与多边形交点的大量运算，大大提高了效率，但一般需要预留一个较大的数组以存放边界点，而且扫描线与多边形边界相交的几种特殊情况仍然存在，需要加以判别。4边界代数算法边界代数多边形填充算法〔BoundaryAlgebraFilling，简称BAF〕，是任伏虎等设计并在微机地理信息系统上实现的一种基于积分思想的矢量格式向栅格格式转换算法。适合记录拓扑关系的多边形矢量数据转换为栅格数据。事实上，每幅地图都是由多个多边形区域组成的。如果把不属于任何多边形的区域〔包括无穷远点〕看成一个编号为零的特殊区域，那么每一条边界弧段都与两个不同编号的多边形相邻，按边界弧段的前进方向分别称为左、右多边形。对图3－24所示的3个多边形的6条边，有如表3－5所示的多边形编号。表3-5线号与左右多边形号的对应关系线号左多边形右多边形Ⅰ0n1Ⅱn20Ⅲn3n2Ⅳn1n2Ⅴn30Ⅵn3n1n2n1n3边界代数算法的根本思想：对每幅地图的全部具有左右多边形编号的边界弧段，沿其前进的方向逐个搜索，当边界上行时，将边界线位置与左图框之间的网格点加上一个值=〔左多边形编号〕-〔右多边形编号〕；当边界线下行时，将边界线位置与左图框的栅格点加上一个值=〔右多边形编号〕-〔左多边形编号〕，而不管边界线的排列顺序。射线算法单个多边形的转换多个多边形的转换

线号左多边形右多边形Ⅰ0n1Ⅱn20Ⅲn3n2Ⅳn1n2Ⅴn30Ⅵn3n1n2n1n3n2n1n3边界代数法与其它算法的不同之处在于它不是逐点搜寻判别边界，而是根据边界的拓扑信息，通过简单的加减代数运算将拓扑信息动态地赋予各栅格点，实现了矢量格式到栅格格式的转换。由于不需考虑边界与搜索轨迹之间的关系，因此算法简单，可靠性好，而且由于仅采用加减代数运算，每条边界仅计算一次，免去了公共边界重复运算，又可不考虑边界存放的顺序，因此运算速度快，同时较少受内存容量的限制，特别适用于微机地理信息系统。栅格数据向矢量数据转换的目的有三：①数据入库；②数据压缩；③矢量制图；

4.6.2栅格格式向矢量格式的转换1〕多边形边界提取：〔二值化，平滑，细化〕2〕边界线追踪※3〕拓扑关系生成4〕去除多余点及曲线圆滑栅格格式向矢量格式的转换的一般需要以下几个步骤所谓的二值化，是在一个设定的灰度阙值的根底上，对扫描获得的灰度图像〔如256级灰度〕进行0或1的简化处理，即有无判断。算法如下：1〕图像二值化1多边形边界提取由于线不光滑以及扫描、摄像系统的分辨率限制，使得一些曲线目标带来多余的小分支〔即毛刺噪声〕；此外，还有空洞和凹陷噪声〔如以下图〕，就会造成细化误差和失真，这样最影响最终栅格的跟踪和矢量化。曲线目标越宽，提取骨架和去除轮廓所需的次数也就越多，因此误差的影响也越大。2〕图像细化预处理二值图像平滑去除毛刺和空洞为了去除毛刺和空洞的影响，可以采用下面两个模板进行处理。处理过程如下：按点阵格式扫描图像上的每一个像素，只要图像相应区域与模板〔包括模板的90旋转〕吻合，那么判定为毛刺〔或空洞〕，对应模板中心数值变给0〔空洞模板将模板中心位置值改为1〕000010XXXX1X101XXX去除毛刺模板，X为任意值去除空洞模板，X为任意值3〕图像细化线细化是处理包含线状地物二值图像的一种重要技术，在地图扫描处理中，由于地图上主要信息是不同粗细和不同形状的线，必须首先进行线细化，以准确有效地提取这些线信息，并进一步矢量化。线细化就是不断去除曲线上不影响连通性的轮廓像素的过程，对细化的一般要求是：保证细化后曲线的连通性；细化结果是原曲线的中心线；保存细线端点下面介绍几种典型的细化方法：经典的细化算法对于二值栅格图像中每个像素点P,以及其直接相邻的8个像素点，令：N(p)为p的邻点的数值的和；图像像素联结数T(p)；Pw,PE,PS,PN分别指像素左侧、右侧、下边、上边邻点的数值T(p)=0T(p)=0T(p)=1T(p)=1T(p)=2T(p)=2T(p)=2T(p)=3T(p)=4算法步骤如下：对于栅格图像中的每一点p做如下操作：第一步：如果将所有被标志的栅格点赋值为0，如果没有被标志的点，那么算法结束第二步：如果将所有被标志的栅格点赋值为0，如果没有被标志的点，那么算法结束转到第一步。骨架法原理：在二值化的根底上，针