基于多重编码技术的圆形窗口线裁剪算法  

New Clipping Algorithm of Line Against Circular Window with Multi-encoding Approach

作　　者：陆国栋[1] 邢军伟[1] 谭建荣[1] 

机构地区：[1]浙江大学CAD&CG国家重点实验室,杭州310027

出　　处：《计算机辅助设计与图形学学报》2002年第12期1133-1137,共5页Journal of Computer-Aided Design & Computer Graphics

基　　金：创新群体科学研究基金 (60 0 2 12 0 1);国家自然科学基金 (5 0 10 60 14 )资助

摘　　要：文中算法建立在全面分析线段与圆形窗口几何特性及二者相对位置的基础上 .首先引入常规外切正方形一次编码技术 ,然后提出旋转 4 5°外切正方形二次编码和广义距离三次编码两种新的编码技术 .常规外切正方形一次编码和旋转外切正方形二次编码可以快速地舍弃大部分完全位于圆形窗口外的线段 ,广义距离三次编码可以快速地获取完全位于圆形窗口内的线段、快速地判别线段与圆形窗口的相对位置 .在获取线圆相对位置的基础上 ,通过广义距离既可舍弃剩余的窗外线段 ,又能加快线段与圆形窗口的求交进程 .实验结果表明 ,该算法具有较高的运算效率和稳定性 .Based on the thorough analysis of relative positions of a line segment with circle, a new clipping algorithm for circular window is established. By introducing the common circumscribed square encoding first, two new encoding methods are designed, i.e., the secondary 45° rotated square encoding and the tertiary generalized distance encoding. The common encoding joining with the secondary encoding can rapidly identify most of the line segments that are completely outside the window. The tertiary encoding can quickly identify all the line segments that are completely inside the window as well as quickly determine the relative positions between them. The generalized distance can also be used to quickly discarding the remaining lines that are outside the window and quickly calculating the intersections between line segment and circle. Experiment results show that the new algorithm has a high efficiency and a good stability.

关 键 词：多重编码 圆形窗口 线裁剪算法 外切正方形 旋转正方形 广义距离 计算机图形学 

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