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

一、矢量格式向栅格格式转换

词目： 栅格矢量数据转换 。英文： raster-vector data transformation 。释文： 空间数据的表达有栅格数据和矢量数据两种结构,在应用中常要根据需要互相转换。栅格数据以矩阵形式记录数据,数据按行按列规则排列。矢量数据将地物分为点、线、面,以点坐标的数据链表示地物的空间位置：一个点以一个坐标对(x,Y)表示,一串坐标对的有序排列组成线,线的闭合围成面。在数学上,一串坐标对的有序排列组成一个矢量,所以称为矢量数据。从矢量到栅格数据的转换称为矢量数据的栅格化,主要用于图件在喷墨绘图仪等栅格型外设上的输出、矢量数据与栅格数据的综合图像处理等场合。从栅格到矢量数据的转换又称为栅格数据的矢量化,主要用于地图或专题图件的扫描输入、图像分类或分割结果的存储和绘图等。

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

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

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

一、矢量格式向栅格格式转换

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

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

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

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

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

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

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