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

摘要

The speed of graphics processing and analysis is affected by the inefficiency, high memory occupancy rate and other issues of the vector circular cutting in existing algorithms. Therefore, an algorithm with linear complexity for vector circular cutting against arbitrary polygon window is proposed. Firstly, using the projection method for linear mapping of vector circles, a linear function of radiation is constructed to detect the intersection of circles and polygons quickly and accurately. Meanwhile, through the line truncation method, the real intersec-tion points between circles and the polygon are obtained by using the linear equation. Then, the intersection points are sorted according to the prescribed direction based on the cross product between three points. Finally, the midpoint detection method is used to determine the visibility of arcs or circles drawn to the memory, and the drawn image and the statistical pattern complexity are output. The experimental results indicate that the proposed algorithm can effectively avoid the generation of virtual intersections, reduce the time and space complexity of the clipping process, and improve the accuracy of vector circles clipping.%已有的矢量圆裁剪算法存在效率低和内存占用率高等问题，将会影响到图形处理和分析的速度，为此提出一种具有线性复杂度的任意多边形窗口的矢量圆裁剪算法。首先采用投影法对矢量圆线性映射，构造一个线性的射线函数，快速而准确地对圆与多边形进行相交性检测，同时通过线截断法，运用线性方程精确地求出圆与多边形的实交点；然后根据三点之间的叉积按照规定的方向对交点进行排序；最后采用中点检测法确定可见性的圆弧或圆绘制到内存，并输出绘制好的图像和统计的图形复杂度。实验结果表明，该算法可有效地避免虚交点的产生，降低裁剪显示过程中的时间和空间复杂度，提高矢量圆裁剪准确性。