一种基于形状相似性度量的曲线化简算法

摘要

曲线的压缩与化简是制图综合领域的一个基础问题，近几十年来，这个问题得到了大量研究，并提出了众多算法，较具代表性的有Douglas-peucker法、Visvalingam法、Li-Openshaw法等。尽管曲线化简算法的种类繁多，然而，纵观这些算法，它们都需要有阈值的参与，且这些阈值又常常是诸如垂距、角度、面积、弧长等绝对标量，这就导致这些算法严重依赖于曲线所处的地理坐标系统，当曲线所处的地理坐标系统发生改变或者并不能确切知道其所在的地理坐标系统时，这些算法的阈值就难以设定，只有反复测试阈值，才能得到想要的化简结果，显然，这给算法的使用者带来了不便。针对上述问题，本文通过分析在不同化简阶段化简曲线与原始曲线的在几何形状上的相似程度提出了一种基于形状相似性度量的曲线化简算法，该算法仍然采用类似于Visvalingam法进行化简，但每次当从原始曲线上删除一个顶点时，都要计算化简曲线与原始曲线的形状相似度，并将所计算出的形状相似度作为阈值，由于形状相似度的计算完全取决于化简曲线与原始曲线在形状上的相似程度，因此它与曲线所处的地理坐标系统无关，无论曲线所处的坐标系统如何发生改变，只要所设定的阈值大小没有发生变化，都将得到相同的化简结果。这里，形状相似性的度量是采用几何矩的方法，同时又对该方法进行了改进。根据几何矩的定义，在计算几何矩时，必须首先对曲线进行等距离离散化，使得曲线上的顶点均匀等距分布，这就会面临这样一个问题，即如何确定曲线上顶点的距离间隔，若间隔过小，则会严重影响算法效率，若间隔过大，又会影响相似度计算结果的准确性，对此，本文提出了一种解决方法，根据该方法可将原始曲线上的顶点投影到化简曲线上，在不改变化简曲线形状的前提下，使得化简曲线的顶点数目仍与原始曲线的顶点数目相同，且顶点的分布情况也与原始曲线顶点的分布情况相似，这样也就无须对曲线进行等距离离散化，大大减少了计算量，且所计算得到的几何矩也准确可靠。