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

• 作者: 吴恩华 孙春娟 李静 王文成
• 来源期刊: 计算机辅助设计与图形学学报
• 学科: 工学
• 关键词: 计算机图形学 线裁剪 凸片段 二叉树 多边形
• 年，卷（期）: 2006,（12）
• 所属期刊栏目: 图形算法与技术
• 页码范围: 1799-1805
• 页数: 7页
• 分类号: TP3
• 字数: 5304字
• 语种: 中文
• DOI: 10.3321/j.issn:1003-9775.2006.12.002

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吴恩华	中国科学院软件研究所计算机科学国家重点实验室	114	2335	25.0	44.0
5	李静	中国科学院软件研究所计算机科学国家重点实验室	238	2528	23.0	40.0
6	王文成	中国科学院软件研究所计算机科学国家重点实验室	42	484	13.0	20.0
7	孙春娟	中国科学院软件研究所计算机科学国家重点实验室	2	13	2.0	2.0