CIM algorithm for approximating three-dimensional polygonal curves |
| |
Authors: | Junhai Yong Shimin Hu Jiaguang Sun |
| |
Affiliation: | (1) National CAD Engineering Center, Tsinghua University, 100084 Beijing, P.R. China;(2) Department of Computer Science and Technology, Tsinghua University, 100084 Beijing, P.R. China |
| |
Abstract: | The polygonal approximation problem is a primary problem in computer graphics, pattern recognition, CAD/CAM, etc. In R2, the cone intersection method (CIM) is one of the most efficient algorithms for approximating polygonal curves. With CIM Eu and Toussaint, by imposing an additional constraint and changing the given error criteria, resolve the three-dimensional weighted minimum number polygonal approximation problem with the parallel-strip error criterion (PS-WMN) under L2 norm. In this paper, without any additional constraint and change of the error criteria, a CIM solution to the same problem with the line segment error criterion (LS-WMN) is presented, which is more frequently encountered than the PS-WMN is. Its time complexity is O(n3), and the space complexity is O(n2). An approxi- mation algorithm is also presented, which takes O(n2) time and O(n) space. Results of some examples are given to illustrate the efficiency of these algorithms. |
| |
Keywords: | polygonal curve CIM LS-WMN approximation optimization |
本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录! |
| 点击此处可从《计算机科学技术学报》浏览原始摘要信息 |
|
点击此处可从《计算机科学技术学报》下载全文 |
|