矩形窗口中的圆弧快速裁剪方法

摘要

本发明公开了一种圆弧在矩形窗口下的快速裁剪方法，对任意给定的圆弧段，该方法按各类圆弧出现概率及所需操作，先后通过圆弧整体包围盒、各分割后的象限圆弧段包围盒、裁剪窗口顶点相对于象限圆弧段的内外测试，以较少的操作尽可能多地排除与裁剪窗口不相交的圆弧；对剩余需求交操作完成裁剪的圆弧，通过查表法快速获取圆弧与裁剪窗口边的交点。本发明的有益之处是，对任意待裁剪圆弧，仅需几次移位、整数加减或少量乘除法运算，即可快速获取其裁剪结果，圆弧裁剪效率有很大提高。此外，由于圆弧裁剪是图形学及CAD的基础问题，该方法可广泛应用于各类绘图软件、建模软件、CAD软件及复杂工程图设计系统等。

主权项

一种矩形窗口中的圆弧快速裁剪方法，其特征在于，该方法包括以下步骤：(1)输入矩形裁剪窗口坐标；(2)输入待裁剪圆弧坐标；(3)以圆弧起点、终点坐标为索引，直接查表一来获取该圆弧的整体包围盒；所述表一的第一列至第三列为始点与终点的象限位置，第四列至第七列为圆弧的包围盒形成规则；其中第一列为起点Ps(xs，ys)所在象限，第二列为终点Pe(xe，ye)所在象限，第三列为起点与终点横坐标的大小关系，第四列至第七列中xleft，ybot，xright，ytop分别为圆弧整体包围盒边界；(4)比较步骤(3)中的圆弧整体包围盒与矩形裁剪窗口，判断圆弧整体包围盒是否位于裁剪窗口内，若结果为是，则输出该圆弧，并返回步骤(1)，否则进行下一步；(5)比较该圆弧整体包围盒与裁剪窗口，若圆弧整体包围盒位于裁剪窗口外，若结果为是，则舍弃该圆弧，并返回步骤(2)，否则进行下一步；(6)将待裁剪圆弧分割为多个象限圆弧段；(7)以待裁剪圆弧起点、终点坐标为索引，通过查表二直接获取其各分割后的象限圆弧段及其对应的象限圆弧段包围盒；所述表二的第一列至第三列为起点与终点的象限位置，第四列和第五列分别为象限圆弧段的起点坐标值和终点坐标值，第六列至第九列为象限圆弧段的包围盒；其中，第一列为圆弧起点Ps(xe，ys)所在象限，第二列为圆弧终点Pe(xe，ye)所在象限，第三列为起点与终点横坐标的大小关系，第六列Xleft为每个象限圆弧段的包围盒的左边界，第七列ybot为每个象限圆弧段的包围盒的下边界，第八列xright为每个象限圆弧段的包围盒的右边界，第九列ytop为每个象限圆弧段的包围盒的上边界；(8)比较各象限圆弧段包围盒与裁剪窗口，若各象限圆弧段均在裁剪窗口外，则舍弃待裁剪圆弧，并返回步骤(2)，否则进行下一步；(9)在矩形裁剪窗口基础上，根据其上边界、下边界、左边界及右边界将坐标系分为九个分区，由上至下、由左至右分别依次编码为1区到9区；(10)遍历各分割后的象限圆弧段，取其起点、终点坐标，与裁剪窗口四条边界分别比较后，确定起点、终点所在分区的编码；(11)根据各象限圆弧段起点、终点所在分区，及裁剪窗口右上或左下顶点与各象限圆弧段内侧或外侧关系，判断该圆弧是否在裁剪窗口外，若判断结果为是，则舍弃该圆弧，并返回步骤(1)；否则进行下一步；(12)对裁剪窗口右边界的x坐标作比例变换，比例因子为1024/R，其中乘以1024的操作通过将x坐标左移10位实现，R为圆弧半径；(13)利用变换后的右边界x坐标查预定义的规范化圆弧‑直线交点的y坐标表表三，快速获取规范化圆弧‑直线交点坐标；所述表三的第一列为圆弧起点的分区编码，第二列为圆弧终点的分区编码，第三列为圆弧段与裁剪窗口边交点数，第四列和第五列为与裁剪窗口边的求交顺序，第六列为保留段用于说明裁剪圆弧段与起点、终点以及两个交点的关系；(14)对所查得的y坐标实施比例变换，得到圆弧‑直线实际交点坐标，比例因子为R/1024，其中除以1024的操作通过将y坐标右移10位实现；(15)根据上步所得圆弧与裁剪窗口直线边交点坐标，对所输入圆弧进行裁剪；(16)输出并显示最终裁剪结果，并返回步骤(1)。