线段与圆在任意多边形边界中的裁剪算法设计及实现

摘要

设计并优化了线段与圆关于任意多边形边界（包括凸多边形及凹多边形边界）的裁剪算法。求出每一条边界与所要裁剪的线段和圆的交点并排序，利用交点将裁剪对象分割成线段、圆弧，通过计算线段和圆弧的中点并判断其与边界的位置关系来完成对图形的裁剪。文中给出了算法具体描述，通过对算法复杂度的分析，该算法的效率与以往的一些经典算法相比有了较大提高。%The lineand circle clipping algorithms against the arbitrary polygon boundary,including convex polygon boundary and concave polygon boundary,are designed and optimized in this paper.The intersection points between each boundary and line or circle that needs to be clipped are calculated and sorted,and then these intersection points are used to divide the clipping object into line segments or circular arcs. The graphic is clipped by calculating middle points of these line segments or circular arcs and deciding their positional relation to the boundary. Both algorithms are described in detail in this paper.Through the analysis of the complexity of the two algorithms, it can be seen that the efficiency of both algorithms has been improved a lot compared with other classical algorithms.