压缩矢量图形的两个算法的比较和分析  

Comparison and Analysis of Two Compact Algorithms for Vector Graph

作　　者：喻国宝[1] 廖湖声[1] 郑玉明[1] 

机构地区：[1]北京工业大学计算机学院,北京100022

出　　处：《计算机工程与应用》2005年第1期80-81,209,共3页Computer Engineering and Applications

基　　金：北京市教委科技发展基金(编号:KM200410005005);北京市优秀人才培养专项经费资助

摘　　要：文章在介绍矢量图形压缩的意义后,分别介绍了矢量图形压缩的分治算法和线性算法,并对这两个算法进行了分析和比较。在选取适当的控制数据压缩的阈值后,分治算法和线性算法的压缩效果接近,但线性算法所需存储空间比分治算法的少,而且线性算法的时间复杂度从分治算法的O(nlogn)降低到O(n)。After introducing the purpose of vector graph compact,a Divide-and-Conquer algorithm and a linear algorithm for vector graph compact are described in this paper.Comparison and analysis are also discussed,revealing that the linear algorithm has approximate same effectiveness as the Divide-and-Conquer algorithm but the linear algorithm has the time complexity of O(n) whereas the Divide-and-Conquer algorithm has the time complexity of O(nlogn).Moreover,the linear algorithm needs less memory than the Divide-and-Conquer algorithm.

关 键 词：地理信息系统 矢量图形压缩 算法分析 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]