曲线数据压缩方法和实现

《曲线数据压缩方法和实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、曲线数据压缩方法和实现　　【摘要】本文主要讨论了曲线矢量数据的压缩算法，分析将其运用到等高线或其他曲线矢量数据压缩。在Spliting算法基础上提出了一种针对无拓扑矢量数据的快速压缩算法，并在AUTOCAD中实现该算法过程。【关键词】矢量数据，压缩算法，精确度，等高线中图分类号：U212.33+2曲文献标识码：A文章编号：一﹑引言在计算机自动制图中应用计算机处理已得到的数字化的资料就不能不注重计算机的容量和计算量。因此，就产生了计算机自动制图中的曲线压缩问题。曲线压缩实质上是信息压缩问题，从信息论上讲曲线矢量数

2、据压缩就是从组成曲线的点序集合A中抽取一个点序子集。用这个子集作为一个新的信息源，在规定的精度范围内对该子集从内容上尽可能地反映原集合，而于数量上则尽可能精简。7由于各种原因，系统接收的原图数据中，有一些等高线、曲线等线状要素的坐标点非常密集，存在大量冗余点。冗余点不但占用大量存储空间，使曲线上出现许多不应有的微小波动，还给对曲线的编辑带来困难。这有时是不必要的，而且常常造成系统处理受限制。因此，需要利用一定的压缩算法消除冗余点，对数据进行简化，并且在保证精度的前提下使曲线具有原来的轮廓和关系，节约存储空间。曲

3、线矢量数据压缩是从组成曲线的点序集合A中抽取一个点序A’，也就是说A’是A中的一部分，不是新的点。而由曲线拟合的方法也可以得到一个逼近的曲线，但拟合出来的曲线不一定通过原来曲线的点，为了避免误差的传递还是用上述方法压缩。二、曲线压缩方法讨论对于封闭曲线它是先确定曲线最左边或最右边两点作为起始端点，而对于非封闭曲线可选择两个断点为起始点，如图1，图1找出两端点之间的曲线上的离散点与两端点的连线的最大距离点，如果该距离值大于给定的精度值，则保留该点，如：2′大于精度值则保留2点。如果2′小于精度值，则再用分别得到的

4、相邻点4作为起始端点重新进行判断以确定下一个要保留的点。依次反复进行直到两直线之间曲线上的点到直线的距离大于精度值为止。最后，作为端点的末点与曲线的最后一个端点重合进行判断并保留最后一个端点。从以上可知，此法可以很大程度上满足即能保留曲线原始的点，能体现曲线的精度不受太大的变化。这在地形图作业上是一个很好的压缩方法。7三、曲线压缩的原理和步骤曲线数据压缩方法三部分：⑴把等高线上的离散点提取出来作为待处理的点；⑵对相邻两点的距离进行比较如果大于距离精度值则保留第二个点；在满足前面条件的情况下对两个端点之间的离散点

5、进行判断如果到两端点的距离大于偏离精确值，则保留该离散点；⑶对保留的点进行绘图使它成为与原等高线相近的曲线。3.1对曲线的离散点进行精度压缩原理7基本思想是去除偏离曲线距离小于规定值δ（例如图0.1mm）的点。假设（图1）中1、2、3、4、5、6为待压缩的曲线上的点。首先保留第一点1，并以1为起点，连接1、3两点，若点2到连线13的垂距22’大于δ，则保留点2，以点3为起点继续计算。若小于δ，则连接1、4两点，分别考察2、3两点到连线14的垂距，若任意一个垂距超过δ，则去掉点2，以点3为起点继续计算；否则，连接

6、1、5两点，考察2、3、4各点到连线15的垂距，……，如此进行下去，直到点1与点i连线时，其间至少有一个点到连线1i的垂距超过δ，则去掉2、3，…，i-2各点，然后以i-1为起点继续计算。重复上述步骤，直到曲线的终点。用这种方法压缩曲线时，在曲线变化平缓的地方，曲线上被压缩掉的点很多，剩下的点间距较大，绘制曲线时点之间会产生多余的摆动。为避免这种情况，压缩过程中可以加入距离条件，即当点的间距超过某一阈值Δ时必须保留一个点，即使其间各点到连线的垂距均不超限。3.2在曲线矢量数据压缩过程中的实现1对等高线上的离散点

7、进行提取。建立一个选择集把提取出的等高线上离散点存入新定义的数组中，其实现程序（见附录）3.2.2对数据进行压缩计算。该算法实际上是一个递归的过程，其实现一直以来也都采用递归的方式，本文通过利用堆和栈的数据结构，提出了该算法的一种非递归实现方法。在算法的实现过程中，用一个数组D来存放曲线的样点列P。，P,…P，用数组的位置索引来指示样点，同时采用了一个与之相配合的队和一个栈，记队尾元素为n，栈顶元素为b。具体步骤如下：(1)将曲线起点D[0]和终点D[n]的下标分别放入队和栈中，此时，n=0，b=n,。(2)连

8、接D[n]和D[b]，在D[n]和D[b]之间的点列中寻找与直线D[n]D[b]具有最大距离的点，记为D[c]，若D[n]与D[b]之间没有中间点，转(4)。若之间有最大距离点，利用两点之间的距离公式：判断D(n)与D(c)的距离是否大于距离精度值，若大于则保留点D(c),若小于则转（4）。7(3)判段D[c]到直线D[n]D[b]之间的距离是否小于阈值，利用点到直线公式判断。若否，则