二、栅格和矢量数据结构相互转换算法

　　矢量结构与栅格结构的相互转换，一直是地理信息系统的技术难题之一。这主要是由于转换程序通常占用较多的内存，涉及复杂的数值运算，而难以在实用系统特别是微机地理信息系统中被采用。近年来已发展了许多高效的转换算法，适用于不同的环境。

　　对于点状实体，每个实体仅由一个坐标对表示，其矢量结构和栅格结构的相互转换基本上只是坐标精度转换问题。线实体的矢量结构由一系列坐标对表示，在变为栅格结构时，除把序列中坐标对变为栅格行列坐标外，还需根据栅格精度要求，在坐标点之间插满一系列栅格点，这也容易由两点式直线方程得到；线实体由栅格结构变为矢量结构与将多边形边界表示为矢量结构相似。因此以下重点讨论多边形（面实体）的矢量结构与栅格结构相互转换问题。

　　（一）矢量格式向栅格格式转换

　　矢量格式向栅格格式转换又称为多边形填充，就是在矢量表示的多边形边界内部的所有栅格上赋予相应的多边形编号，从而形成栅格数据阵列。

　　1.内部点扩散算法；该算法由每个多边形一个内部点（种子点）开始，向其八个方向的邻点扩散，判断各个新加入点是否在多边形边界上，如果是边界点，则新加入点不作为种子点，否则把非边界点的邻点作为新的种子点与原有种子点一起进行新的扩散运算，并将该种子点赋予多边形的编号。重复上述过程，直到所有种子点填满该多边形并遇到边界为止。

　　扩散算法程序设计比较复杂，需要在栅格阵列中进行搜索，占用内存很大。在一定栅格精度上，如果复杂图形的同一多边形的两条边界落在同一个或相邻的两个栅格内，会造成多边形不连通，则一个种子点不能完成整个多边形的填充。

　　2.复数积分算法：对全部栅格阵列逐个栅格单元判断栅格归属的多边形编码，判别方法是由待判点对每个多边形的封闭边界计算复数积分，对某个多边形，如果积分值为2πi，则该待判点属于此多边形，赋予多边形编号，否则在此多边形外部，不属于该多边形。

　　复数积分算法涉及许多乘除运算，尽管可靠性好，设计也并不复杂，但运算时间很长，难以在比较低档次的计算机上采用。采用一些优化方法，如根据多边形边界坐标的最大最小值范围组成的矩形来判断是否需要做复数积分运算，可以部分地改善运算时间长的困难。

　　3.射线算法：射线算法可逐点判别数据栅格点在某多边形之外或在多边形内，由待判点向图外某点引射线，判断该射线与某多边形所有边界相交的总次数，如相交偶数次，则待判点在该多边形的外部，如为奇数次，则待判点在该多边形内部。

　　射线算法要计算与多边形交点，因此运算量大。另一个比较麻烦的问题是射线与多边形相交时有些特殊情况如相切、重合等，会影响交点的个数，必须予以排除，由此造成算法的不完善，并增加了编程的复杂性。

　　4.扫描算法：扫描算法是射线算法的改进，通常情况下，沿栅格阵列的行方向扫描，在每两次遇到多边形边界点的两个位置之间的栅格，属于该多边形。扫描算法省去了计算射线与多边形交点的大量运算，大大提高了效率，但一般需要预留一个较大的数组以存放边界点，而且扫描线与多边形边界相交的几种特殊情况仍然存在，需要加以判别。

　　5.边界代数算法：边界代数多边形填充算法（Boundary Algebra Filling，简称BAF），是任伏虎等设计并在微机地理信息系统上实现的一种基于积分思想的矢量格式向栅格格式转换算法。

　　为说明边界代数转换法的原理，先考虑图3－23所示单个多边形的简单情况，模仿积分求多边形区域面积的过程，初始化的栅格阵列各栅格值为零，欲填充多边形编号为a的区域，即将区域内栅格点的值变为a，而区域外各点仍保持原值零。转换时，以栅格行列为参考坐标轴，由多边形边界上某点为起点顺时针搜索边界线，当边界线段为上行时（图3－23（a）），位于搜索边界曲线左侧的具有相同行坐标的所有栅格点被减去一个值a；当边界线段为下行时（图3－23（b）），则将边界曲线左边（从曲线前进方向看为右侧）所有具相同行坐标的栅格点加上一个值a，当沿边界搜索运算一周回到起始点后，所有多边形内部的栅格点都被赋值a，而多边形外的栅格点的值不变。
　　本文标题：栅格和矢量数据结构的选择及其相互转换算法(2)
　　手机页面：http://m.dljs.net/dlsk/gis/4765.html
　　本文地址：http://www.dljs.net/dlsk/gis/4765.html