基于适应性相关测试和点斜式查表求交的圆形窗口快速裁剪方法

摘要

在智能CAD、图形识别与理解等复杂图形应用系统中,由于图元数量多、图元间关系复杂,且系统实时交互响应要求较高,现有圆形窗口裁剪算法较难满足要求.为此提出圆形窗口对线段的一种新的快速裁剪算法.该算法由基于切线分隔的圆外线段快速适应性测试方法、基于最小范围的圆内线段测试方法和基于点斜式查表的线段与窗口圆快速求交方法三部分组成.通过按端点位置选择适应的测试方法、尽量避免不必要的操作、尽量以简单操作代替复杂操作等措施,大大提高了圆形窗口对线段的裁剪速度.在图形识别及智能CAD等应用中的实验结果表明,采用文中算法可较大地提高效率.%Existing circular window 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 constraints and real-time interaction requirements. This paper presents a fast line clipping algorithm against circular windows. The proposed algorithm is composed of three parts: adaptive identification of invisible lines based on tangent lines separation, fast identification of visible lines based on polygons cutting, and fast line-arc intersections generation based on predefined tables retrieval. Experimental results demonstrate that the proposed algorithm greatly reduces the computational cost to clip lines by adaptive line-circle situation analysis and replacement of time-consuming operations with simpler ones.