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

摘要

文中算法建立在全面分析线段与圆形窗口几何特性及二者相对位置的基础上.首先引入常规外切正方形一次编码技术,然后提出旋转45°外切正方形二次编码和广义距离三次编码两种新的编码技术.常规外切正方形一次编码和旋转外切正方形二次编码可以快速地舍弃大部分完全位于圆形窗口外的线段,广义距离三次编码可以快速地获取完全位于圆形窗口内的线段、快速地判别线段与圆形窗口的相对位置.在获取线圆相对位置的基础上,通过广义距离既可舍弃剩余的窗外线段,又能加快线段与圆形窗口的求交进程.实验结果表明,该算法具有较高的运算效率和稳定性.