图3－24表示转换单个多边形的情况。设该多边形编号为a，对初始化的栅格阵列各像元赋值为零，欲完成转换，就是要将该多边形区域内的所有栅格像元均赋值为a，而多边形区域以外的像元仍保持原值零。因此，转换时以栅格行列为参考坐标轴，从多边形边界上某点开始顺时针搜索边界线。当边界上行时，如图3－24（a），位于该边界线段左侧的具有相同行号的所有栅格像元被减去a值；当边界下行时，如图3－24（b），该边界左侧（或为边界行进方向的右侧）的所有栅格像元加上一个值a，当沿边界搜索一周重新回到起点后，所有多边形内部像元点都已被赋值a，而多边形外部的栅格像元值不变，从而完成多边形填充的转换.
二、栅格数据向矢量数据的转换
栅格数据向矢量数据的转换实际上就是将具有相同属性代码的栅格像元集合表示为以边界弧段以及边界的拓扑信息所确定的多边形区域，而每个边界弧段又是由一系列小直线所组成的矢量格式边界线。通常这种转换包括对多边形边界的提取、多边形边界的跟踪、拓扑关系的生成和去除冗余点及曲线光滑等步骤。上述步骤是为了使栅格数据中包含的空间实体之间的拓扑关系和固定的属性代码在转换过程中仍保持其原有关系和原代码，保证数据转换的真实性和一致性。所谓多边形边界提取实际上是通过确定边界点和结点来实现的；边界线跟踪则是根据已经提取的结点或边界点，判断跟踪搜索方向后，逐个边界弧段地进行跟踪；拓扑关系生成则是将原栅格数据含有的边界拓扑关系转换为矢量拓扑数据结构并建立与属性数据的联系；去除冗余点以及曲线光滑是为减少数据冗余，将因逐点搜索边界点造成的多余点去掉，并采用一定的插补算法对由于栅格精度限制造成的边界曲线不圆滑进行处理。
下面介绍一种双边界直接搜索算法。其基本思想是通过边界提取将边界弧段左右多边形的拓扑信息保存在边界点或结点上，在对边界跟踪搜索时采用2X2栅格阵列作为窗口，顺序沿行（或列）方向对整个栅格阵列进行全图搜索，根据当前窗口内的四个栅格代码值的结构模式可以确定下一个窗口的搜索方向以及与被搜索边界的拓扑关系。具体步骤可分为三个阶段： （1）边界点和结点的提取
对于一个mXn的栅格图像阵列，采用2X2栅格阵列作为窗口顺序沿行、列方向对全图进行扫描。若当前窗口内的四个栅格像元的代码值相同，则表示它们属于同一区域，不是边界点；若当前窗口内的四个栅格值有且仅有两个不同的值，则该窗口内的四个栅格可确定出边界点。这说明该点位于以这两个值为编号的多边形边界上。为此可以将这四个栅格作为确定边界点的标识，并保留各栅格的原属性代码值；若窗口内四个栅格中有三个以上不同编码，则可以确定出结点，说明该点是三条以上不同边界弧段的交汇点，为此可用这四个栅格作为确定该结点的标识，并保留各栅格原代码值。若窗口中四个栅格出现对角线上两两相同的情况，说
明该处多边形不连通，此时仍将这四个栅格确定的点当作结点处理。图3－27、图3－28所示分别为结点和边界点的几种结构模式。
（2）边界线搜索与拓扑信息的生成
边界点和结点提取后，即可在此基础上进行边界线搜索。边界线搜索是逐个孤段进行的，对每个弧段由一个结点开始，选定与之相邻的任意一个边界点或结点进行搜索。首先记录边界点的两个多边形编号作为被搜索边界的左右多边形，而搜索方向则由进入当前点的方向和当前点下一步要走的方向来确定。因此每个边界点只能有两个走向：一个是前点的进入方向，另一个是要搜索的后续点方向。如图 3－28（3）所示的边界点只能有两个走向，即向下方和右方。若该边界点是由下方搜索得到的，也就是说，若其前点位于它的下方，则该点的搜索方向只能是右方，该边界弧段的左右多边形编号应分别为a和b；反之，如果该点是被其右方的点搜索到，即右点是该点的前点，则后续搜索方向应确定为下方，此时，该边界弧段的左右多边形编号应分别为b和a。其它情况依此类推。由此可见，这种结构可以唯一地确定搜索方向，从而大大地减少搜索时间，同时形成的矢量结构带有左右多边形编号的拓扑信息，容易建立拓扑结构和与属性数据的联系，利于提高转换效率。 （3）去除冗余点和曲线光滑
在进行边界搜索时，由于是沿边界逐点搜索，当遇到边界弧段是直线的情况时，就会产生多余点，从而造成数据冗余。为此，需要除去这些多余点记录。去除多余点的基本思想是根据解析几何中的直线方程来确定需要去除的点。在一个边界弧段上的连续三个点（x1，y1），（x2，y2）和（x3，y3），如果在一定的精度范围内可以认为它们是处于一条直线上，即满足直线方程，则三个中间的一点可以被认为是多余，应予以去除。
通过边界搜索产生的边界线由于栅格精度的限制，可能不够光滑，通常可以采用一些插值算法进行光滑处理，常用的算法有：
①线性迭代法；②分段三次多项式插值法；③正轴抛物线平均加权法；④斜轴抛物线平均加权法；⑤样条函数插值法。
E、 GIS数据模型
GIS涉及的数据量很大，而且数据之间的联系又是错综复杂，因此，GIS数据库的数据组织是一个核心问题。数据组织的好坏将影响到GIS效率的高低以及用户对GIS的使用。通常，数据库技术在处理数据库组织时，是从全局出发，对数据内部的联系和用户要求进行综合平衡来考虑。在设计数据库全局逻辑结构时，现有的数据库管理系统通常使用三种方法对数据构成三种不同形式的数据库数据结构，即:
（l）层次方法：将数据库数据接层次结构的形式进行组织； （2）网状方法：将数据库数据接“有向图”的结构形式组织；
（3）关系方法：将数据库数据按关系形式，即表格结构的形式进行组织。 对于不同形式的数据库数据结构方法，对应有不同类型的数据库数据的操作集合，以及为了保证数据库数据的完整性规定的完整性规则集合。一般情况下，数据库数据模型就是由上述的数据库数据结构、数据库操作集合和完整性规则集合三者组成。所谓模型是人们对客观世界的认识和理解，是对客观现实
系统的近似描述。所以数据模型又称为数据库结构，它反映了数据库中数据的整体逻辑组织，反映了实体之间的逻辑联系。
GIS数据模型是描述GIS的数据内容和数据之间的联系工具，它是衡量GIS数据库能力强弱的一个主要标志，也是数据库系统的基础。GIS数据库主要涉及对图形数据和属性数据的管理和组织，它是以一定的组织方式将互相关联的数据集合存贮在一起，并且能够以最佳方式和最小的数据冗余为多种目的服务。另一方面，由于计算机处理的数据既可以存放在数据文件里，也可以存放在数据库中，例如目前很多GIS系统就是用文件系统管理空间数据（图形数据），用数据库系统管理属性数据，所以也可以说数据库就是一些相互关联的存贮文件的集合。
目前在数据库领域中，流行的数据模型主要有三种，即层次模型、网状模型和关系模型，除此之外还有最近兴起的面向对象模型。需要说明的是，所谓关系数据库管理系统，就是说数据库管理系统所支持的数据模型是关系的，或者说该数据库管理系统采用的是关系方法。类似地，还有网状数据库管理系统和层次数据库管理系统。从目前数据库技术的状况和发展趋势来看，关系数据库将占主导地位。另外，面向对象技术用在数据库设计领域后，受到人们的重视，有趋势表明可能将发展成下一代数据库的主流。 一、层次模型
用树状结构来表示实体之间联系的模型称为层次模型。它是以结点来表示数据库中的
记录类型的有向树。如图3－29所示为一个简单的多边形地图。按层次方法可将图3－29构造成树结构的层次模型，如图3－30所示。
由图3－30可看出，层次模型揭示的是实体（记录）之间的一对多（1:n）的联系。通常把表示1的实体放在上方，称为“父结点”；而将表示n的实体放在下方，称为“子结点”；最上层只能有一个结点，称为根结点。为符合1：n的联系，除根结点外，其它的结点都有且仅有一个“父结点”，但是每个父结点可以对应于多个子结点。最下层的末端结点也称为叶结点。
在层次模型中，检索是向从根开始的某条路径提出询问，依照从左到右的顺序检查路径。图3－30
是用层次模型表示的简单多边形地图数据库结构，该结构按多边形、弧段和结点分为不同层次，如查询结点6，则从根结点开始，可循多边形 I一弧段f结点 6的路径搜索，层次关系非常清晰。
如上所述，可得出层次模型的两个限制条件： （l）有且仅有一个结点无父结点，即根结点；
（2）除根结点之外，所有结点有且仅有一个父结点。
这就使层次模型不能直接表示实体之间多对多（m：n）的联系。若需要用层次模型表示m：n联系，就必须设法先将该联系分解为1：n联系后，才能用其表示。这是令人遗憾的缺陷。在GIS中，若采用这种层次模型将难以顾及公共点、线数据共享和实体元素间的拓扑关系，导致数据冗余度增加，也给拓扑查询带来困难。归纳起来，层次模型的优点是容易理解，单码查找速度快，易于更新和扩充；但是多码查找比较困难，一般需要较大的索引文件，所以产生数据冗余。
二、网状模型
如果取消层次模型中的两个限制，即允许有多于一个以上的结点没有父结点，且允许每个结点可以有多个父结点，则树形结构便可形成网络形式。因此，网状模型就是用网络结构来表示实体之间联系的模型。理论上，由于网状模型没 有层次模型的那两点限制，所以可以直接表示m：n联系。但是在实际应用上，一些已经实现的支持网状模型的数据库管理系统
上，对直接处理实体之间的m：n联系作了限制。
网状模型和层次模型在本质上是一样的。从逻辑上看它们都是用连线表示实体之间的联系，用结点表示实体集。如图3－31所示为图3－29的网状模
型，从物理上看，层次模型和网状模型都是用指针来实现两个文件之间的联系。区别仅在于网状模型中的连线更加复杂，更加纵横交错，从而使数据结构更加复杂。
由此可知，网状模型是以有向图表示的网络结构，每个结点仍然表示数据库中的一个记录类型（实体）。网状模型的有向图与层次模型的有向树比较，其区别在于：
（1）可以有零个或多个结点无父结点（图3－32（a））； （2）至少有一个结点有多于一个父结点（图3－32（a，b））；
（3）允许两个结点之间有两种或多种联系（图3－32（C）。
网状模型中，结点之间的联系是任意的，为区分这些结点之间不同的联系，对这些联系要进行命名，通常将其称为“系型”。系型表示各结点之间，即记录类型之间的
联系。例如，记录型O和记录型M之间的联系命名S，则系型可表示为图3－33
（a）所示；若将该关系用在教授与研究生之间的指导关系，则可表示为图3－33（b）所示。
在基于矢量结构的GIS中，图形数据通常采用拓扑数据模型，这种模型非常类似于网状模型，只是在拓扑模型中一般采用目标标识来代替网状结构中的指针。
图3－34是用网状模型表示自然要素、社会经济要素和地理位臵要素之间联系的示例。 总之，网状模型较层次模型扩充了对实体之间联系的限制，可以较灵活地表示实体之间的多种关系，对确定的数据表示效率
较高，数据冗余也较小，适合于表示关系较复杂的地理数据和具有网络状特征的地理实体，但网状模型的数据指针比较复杂，数据更新也较为繁琐。 三、关系模型
表格是人们熟悉的数据表示方法。用表格数据表示实体和实体之间联系的模型称为关系模型。
在层次模型和网状模型中，文件中存放的是数据，各文件之间的联系是通过指针（连线）来实现的。而在关系模型中，文件中存放两类数据：一是实体本身的数据，二是实体间的联系。这里的联系是通过联接字段实现的。
关系模型源于数学，它把数据看成是二维表格中的元素，而这个二维表格就是所谓关系。表中的每一行代表一个记录或一个取样；每一列称为关系的一个属性集，列可以命名，称为属性名，或数据项类型。显然，关系是记录（行）的集合。如果表格中有n列，则称该关系是n元关系。
一个实体可由若干关系组成，而关系表的集合就构成关系模型。对这种数学化的模型，每个关系应满足下列条件：
（1）表中的每一列属性都是不能再分的基本字段； （2）各列被指定一个相异的名字； （3）各行（记录）相异，不允许重复； （4）行、列次序无关。
综合以上四点可知，一个关系是一个概念文件，该文件中的每个记录是唯一的，所有记录具有相同个数和类型的字段，也就是说，所有的记录有同样的固定长度和格式。图3－29所示的多边形地图，可用下列关系表示出多边形实体与其边界弧段实体和结点实体之间的关系。如图3－35所示各实体之间的联系可以通过连接字段来实现。例如关系1中边界弧段号C可与关系2中相同字段边界弧段号C进行连接，同样道理，关系2中结点号3也可与关系3中结点号3进行连接。
关系模型的最大特色是对实体描述的一致性，上述示例中用连接字段实现各实体之间联系正说明这一点。关系模型正是利用数据本身通过公共值隐含地表达它们之间的联系，并且可采用关系代数和关系运算来操作数据。在关系模型下，实体及其实体之间的联系均采用关系来描述，通过关系之间的连接运算还可建立新的关系，对关系数据库的查询和统计操作也都可以采用关系运算得以实现。此外，关系模型还具有结构简单、灵活、数据修改和更新方便、容易维护等特点。所以它是当前数据库中较常用的数据模型。目前，很多GIS中的属性数据都是采用关系数据模型，甚至某些关系还采用关系数据库管理系统来管理空间数据。
但是GIS中的关系模型在效率、数据语义、模型扩充和目标标识等方面还存在一些问题，特别是在处理空间数据库所涉及的复杂目标方面，传统的关系模型显得难以适应，此外，关系数据库系统的管理也较为复杂，查找速度与网状和层次模型相比也要慢一些。
四、面向对象模型（略）
综上所述，数据库理论是GIS的理论基础，尽管目前流行的通用数据库管理系统在对空间实体的定义、描述和检索运算上仍存在着很大的不足，进行GIS的技术设计时，完全采用通用数据库管理系统远非理想；但是，由于通用数据库管理系统在数据定义、结构扩充、数据更新和数据运算上效率高、通用性较强，因此目前很多GIS仍倾向于采用通用数据库管理系统作为其数据管理的支持系统。而与此同时，更适合于GIS需要的具有最小冗余、最大灵活性以及最快速的空间型数据库管理系统也正在发展之中。
－《地理信息系统基本原理及应用》