任意多边形窗口的圆裁剪算法.pdf

第 l9卷 第 5期 计 算 机 技 术 与 发 展 VO1．19 NO．5 2009年 5月 COMPL丌ERTE(’I1NOIX Y AND DEVEIOPMENT Mav 2009 任意多边形窗口的圆裁剪算法 杭后俊 ，孙丽萍 (安徽师范大学 数学计算机科学学院，安徽 芜湖 241000) 摘 要：圆的裁剪广泛应用于诸如计算机图形学、二维计算机动画以及机器人运动学等领域。讨论了圆关于任意多边形 窗口的一个裁剪算法 ，按逆时针方向依次求出多边形裁剪窗121的每条边与圆的交点并且保证交点正确排序 ，对于交点序 列中的任意两相邻的交点，采用 “中点检测法”来判定以它们为端点的圆弧与裁剪窗 口的位置关系，最后给出完整的裁剪 算法。实现结果表明，不论从效率还是稳定性方面都取得了比较理想的效果。 关键词：裁剪窗口；裁剪算法；求交算法 中图分类号 ：TP391．41 文献标识码 ：A 文章编号：1673—629X(2009)05—0235—03 AnAlgorithm forCircleClippingAgainstPolygonW indow HANGHou-jun，SUNLi—ping (SchoolofMathematicsandComputerScience，AnhuiNormalUniversity，Wuhu241000，China) Abstract：Circleclippingisappliedwidelycomputergraphics。suchastwodimensioncomputeranimationna drobotkinematicsete．Discuss— esacircleclipping algorithm againstthepolygonwindow indetail．Theintersectionpointsofthecircleandeachsideoftheclipping win- odw arecalculatednadsortedcorrectly．Regardingtwoneighborintersectoinpo intsinsequence， “themiddlepo intdetceting method ’is usedtOjudog thepositionrelationsofcircularRrenadtheclippingwindow．Finally，thewholeclipping algoritmh isgained．Theresultex— pressesthatthealgoritmh isstableandefficient． Keywolds：clipping window；clipping algoritmh ；intersectionalgoritmh O 引 言 及机器人运动学等领域。例如 ，经常需要对两个或多 确定图形中哪些部分落在显示区之内，哪些落在 个实体间进行碰撞、检测等。特别是在二维计算机动 显示区之外 ，以便只显示落在显示区内的那部分图形， 画中，用圆来表示二维实体的某些局部等等。人们往 这个选择过程称为裁剪。图形的裁剪算法是光栅图形 往希望先定义一个视窗(Viewport)，然后在该视窗内 学的重要内容之一 ，在各种有关计算机图形学的专著 显示图形对象。通过鼠标响应以弧擦除的方式来进行 中都对图形的裁剪进行专门的讨论 ．2]。对于广大用 窗口的裁剪。因此，讨论圆关