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

《任意多边形窗口的圆裁剪算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第l9卷第5期计算机技术与发展VO1．19NO．52009年5月COMPL丌ERTE(’I1NOIXYANDDEVEIOPMENTMav2009任意多边形窗口的圆裁剪算法杭后俊，孙丽萍(安徽师范大学数学计算机科学学院，安徽芜湖241000)摘要：圆的裁剪广泛应用于诸如计算机图形学、二维计算机动画以及机器人运动学等领域。讨论了圆关于任意多边形窗口的一个裁剪算法，按逆时针方向依次求出多边形裁剪窗121的每条边与圆的交点并且保证交点正确排序，对于交点序列中的任意两相邻的交点，采用“中点检测法”来判定以它们为

2、端点的圆弧与裁剪窗口的位置关系，最后给出完整的裁剪算法。实现结果表明，不论从效率还是稳定性方面都取得了比较理想的效果。关键词：裁剪窗口；裁剪算法；求交算法中图分类号：TP391．41文献标识码：A文章编号：1673—629X(2009)05—0235—03AnAlgorithmforCircleClippingAgainstPolygonWindowHANGHou-jun，SUNLi—ping(SchoolofMathematicsandComputerScience，AnhuiNormalUnive

3、rsity，Wuhu241000，China)Abstract：Circleclippingisappliedwidelycomputergraphics。suchastwodimensioncomputeranimationandrobotkinematicsete．Discuss—esacircleclippingalgorithmagainstthepolygonwindowindetail．Theintersectionpointsofthecircleandeachsideoftheclip

4、pingwin-dowarecalculatedandsortedcorrectly．Regardingtwoneighborintersectionpointsinsequence，“themiddlepointdetectingmethod’isusedtOjudgothepositionrelationsofcircularRreandtheclippingwindow．Finally，thewholeclippingalgorithmisgained．Theresultex—pressesth

5、atthealgorithmisstableandefficient．Keywolds：clippingwindow；clippingalgorithm；intersectionalgorithmO引言及机器人运动学等领域。例如，经常需要对两个或多确定图形中哪些部分落在显示区之内，哪些落在个实体间进行碰撞、检测等。特别是在二维计算机动显示区之外，以便只显示落在显示区内的那部分图形，画中，用圆来表示二维实体的某些局部等等。人们往这个选择过程称为裁剪。图形的裁剪算法是光栅图形往希望先定义一个视窗(View

6、port)，然后在该视窗内学的重要内容之一，在各种有关计算机图形学的专著显示图形对象。通过鼠标响应以弧擦除的方式来进行中都对图形的裁剪进行专门的讨论．2]。对于广大用窗口的裁剪。因此，讨论圆关于一个多边形窗口的裁户来说，不论是使用图形软件库(如OpenGL等)开发剪算法就显得非常有意义。绘图软件，还是直接使用各种图形软件进行图形对象文中讨论了任意多边形窗口的圆裁剪算法问题，的绘制与编辑，图形的裁剪是使用频率非常高的操给出了一个快速裁剪算法，并对该算法进行了实现。作[。多年来，许多学者专门撰写论文对有关

7、基本图形1直线段与圆的求交算法的裁剪算法进行探讨[4-8]。对圆裁剪的讨论更多的侧圆相对于多边形窗口裁剪的关键是要求出圆和窗重于矩形裁剪窗151【9．1，任意多边形窗口的圆裁剪算口每条边的交点。因此，直线段与圆的求交算法是文法讨论得很少。而作为图形裁剪的重要部分，的中后续内容的基础。剪广泛应用于诸如计算机图形学、二维计算机动l，以如图1，已知线段P1P2，端点坐标为P(1，j，1)，P(2，Y2)，则其方程为：收稿日期：2008—09一I6ax十+f=0基金项目：安徽省自然科学基金(2006kj076

8、B)；安徽师范大学青年基其中口=Y0一Yl，b：1一zO，CXOYJ—1YO。金(2008xqn47)作者简介：杭后俊(1965一)，男。安徽无为人，副教授，研究方向为计圆的方程为：算机图形学，CAGD等。(—z0)+(Y—Y0)=r(2)·236·计算机技术与发展第l9卷由点到直线的距离公式可知，圆心(，Y0)刮中。,P1P2的距离c，为Ste1)6结束。完整的求交伪代码如下：／／将交点保存到交点表中floatintersecpoint[8][2]；i