高级检索
路通, 蔡士杰. 基于查表的快速圆弧裁剪算法[J]. 计算机辅助设计与图形学学报, 2011, 23(8): 1324-1331.
引用本文: 路通, 蔡士杰. 基于查表的快速圆弧裁剪算法[J]. 计算机辅助设计与图形学学报, 2011, 23(8): 1324-1331.
Lu Tong, Cai Shijie. A Fast Table-Based Arc Clipping Algorithm[J]. Journal of Computer-Aided Design & Computer Graphics, 2011, 23(8): 1324-1331.
Citation: Lu Tong, Cai Shijie. A Fast Table-Based Arc Clipping Algorithm[J]. Journal of Computer-Aided Design & Computer Graphics, 2011, 23(8): 1324-1331.

基于查表的快速圆弧裁剪算法

A Fast Table-Based Arc Clipping Algorithm

  • 摘要: 在智能CAD、图形识别与理解等复杂图形应用系统中,由于图元数量多、图元间关系复杂,且系统实时交互响应要求较高,现有圆弧裁剪算法较难满足要求.为此提出一种从2个角度大幅提高圆弧裁剪效率的快速圆弧裁剪算法.首先按圆弧与矩形裁剪窗口的位置关系,通过所在圆、圆弧、分割后的各象限圆弧段与裁剪窗口最多进行三层次适应性相关测试,以较少的操作尽可能多地排除与裁剪窗口不相交的圆弧;其次对剩余的、需通过求交操作完成裁剪的圆弧给出基于查表法的圆弧-直线交点获取方法,避免了复杂的开方操作,可快速获取裁剪结果.在图形识别及智能CAD等应用中的实验结果表明,采用文中算法可较大地提高效率.

     

    Abstract: Existing arc clipping algorithms are inefficient for many complex real-life applications like intelligent CAD and graphics recognition/understanding systems,due to their large number of graphical primitives,complicated geometrical relations and real-time interaction requirements.A fast arc clipping algorithm is proposed to greatly improve the efficiency in two steps.First,adaptive relational-tests are performed to exclude or reserve those arcs without arc-line intersections as more as possible in three levels: circular boundary boxes,arc boundary boxes and segmented quadrant arc boundary boxes.Second,a fast table-based arc-line intersections retrieval method is proposed to obtain the final clipping results for the rest arcs.Only several times of shift,comparison,addition/subtraction or multiplication operations are needed to clip any given arc.Experimental results in real-life graphical applications show that the algorithm is very fast and more efficient.

     

/

返回文章
返回