基于凸片段分解的多边形窗口线裁剪算法

摘要：

将多边形窗口的边顺序地分割成一些片段,使得每个片段都能局部地形成一个凸多边形,称为凸片段,并建立一个二叉树来管理这些凸片段.在裁剪计算时,先根据二叉树快速地找到与被裁剪线段相交的凸片段,再利用高效的凸多边形线裁剪算法对这些凸片段进行裁剪操作.文中算法能有效地降低裁剪计算的时间复杂度,使其在O(logN)～O(N)之间自适应地变化,且大部分情况下时间复杂度小于O(N).

关键词：计算机图形学、线裁剪、凸片段、二叉树、多边形

所属期刊栏目：18

分类号：TP3(计算技术、计算机技术)

资助基金：国家自然科学基金60373051;国家重点基础研究发展计划973计划2002CB312102;澳门大学校科研和教改项目

在线出版日期：2006-12-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：1799-1805