多边形链式编码方式的改进及其编码方法

邱国清

(漳州师范学院 计算机科学与工程系， 福建 漳州 363000)

0 引言

链式编码主要是记录线状地物和面状地物的边界，它把边界表示为：由某一点出发并按某些基本方向确定的单位矢量链 。基本矢量方向可用0～7整数表示，该编码对探测边界急弯和凹进部分都很容易，比较适合存储图形数据，但该编码也存在一个缺点，它对于叠置运算无法实现，对局部修改会改变整体结构，链式编码是由若干基本矢量方向组成的链，这些矢量方向不可以用来运算，必须将这些矢量方向转换成可以用来运算的编码。本文采用二叉树原理、Morton码和霍夫曼原理，利用拓扑结构将链式编码的单位矢量方向转换成编码。

1 结点的编码和搜索

拓扑结构可以描述地图特征的三个空间关系：区域定义、连通性和邻接性。多边形由一条或多条弧段围成的区域来定义。弧段链首尾相连，自行封闭。在数字化过程中，对结点坐标进行匹配，使得连通的弧段结点都具有相同坐标的特性，并在此基础上对弧段结点按照数值大小进行排序。

多边形的搜索方法有很多，其中左转算法具有计算简单、循环次数少、容易实现等特点：

1)以起点弧段L的尾结点N为起点搜索点，通过结点的弧段记录表，读出与该结点相连的所有弧段的标识码L[i]；

2)分别计算弧段L[i]与X轴正向的夹角a[i],0≤a[i]≤2π .计算夹角时，以结点N和L[i]上与该结点最近的拐点所连的直线代表L[i] 来计算夹角。

3)若L对应的夹角a为a[i] 中的最小角，则a[i]中的最大角amax所对应的弧L[i] 为搜索的后续弧段L*；否则，计算△a[i]=a-a[i] ，取最小正 △a[i]所对应的弧L[k]为后续弧段L*.

4)以L*的尾端为起点，重复(1)～(3)，直到L*=L.

2 多边形的搜索

当弧段关系确定后，算法初始输入的离散弧段已经通过起始和终止结点坐标匹配为对应的逻辑结点，通过此逻辑结点和弧段组成的“逻辑网络”就可以进行多边形搜索。

3 多余多边形的处理

为了避免在矢量化过程中生成重复多余的多边形，应在将要生成一个多边形之前，通过索引机制快速地检查是否已经存在与之相同的多边形：首先由将生成多边形最小外接矩形的中心行列号确定该中心所在的网格，然后把将生成多边形的最小外接矩形与网格中所有多边形的最小外接矩形进行比较，如果某一个多边形的最小外接矩形与将生成多边形的最小外接矩形相同，则将生成多边形为多余多边形，应不予生成[2]。

4 链式编码原理

链式编码的前两个数字表示起点的行、列数，从第三个数字开始的每个数字表示单位矢量的方向，8个方向以0～7整数表示。

图1 链式编码图

在图1中，包含两个多边形，共用一条边(该边包含6、7、8、9、10、11共5个点)。根据统计，方向为0的有4、9、13共3个点；方向为1的有5、16共2个点；方向为2的有6、8、10、14、17共5个点；方向为3的有7、15共2个点；方向为4的有11、18共2个点；方向为5的有12共1个点；方向为6的有1共1个点；方向为7的有2、6共2个点。

5 链式编码转换成二叉树

霍夫曼编码的基本思想[3]是按照字符出现概率的大小，概率大的字符分配短码，概率小的字符分配长码来构造最短的平均码长，以图一为例，该图形编码中每个方向出现的概率大小计算如表1所示。

表1 概率表

用霍夫曼编码方法，对属性值进行编码，其编码过程如表2所示。

表2 编码过程

表2的编码过程可用图2的编码树来表示。

图2 霍夫曼编码树

通过霍夫曼编码树，可以将链式编码的方向矢量转换为可用来运算的编码。

6 总结

根据霍夫曼编码和二叉树的原理将链式编码中的方向矢量转换为可以运算的编码，由于链式编码方式中的每个节点是依据行、列以及单位矢量的方向表示，所以当链式编码被转换成霍夫曼编码树时，每个节点都由唯一的霍夫曼编码表示，从而克服链式编码方式对于叠置运算无法实现以及相邻区域的边界被重复存储而产生冗余。

参考文献:

[1]闫浩文.计算机地图制图原理与算法基础[M].北京：科学出版社,2007.

[2]扶卿华,倪绍祥,郭 剑. 栅格数据矢量化及其存在问题的解决[J].现代测绘,2004,27(3):8～11.

[3]付先平. 多媒体技术及应用[M]. 北京：清华大学出版社，2007.

[4]艾自兴,龙 毅.计算机地图制图[M].武汉:武汉大学出版社,2005.