[發明專利]矩形窗口中的圓弧快速裁剪方法

無效

• 申請號: 200810243874.4
• 申請日: 2008-12-09
• 公開（公告）號: CN101488227A
• 公開（公告）日: 2009-07-22
• 發明（設計）人: 路通;楊若瑜;蘇豐;蔡士杰
• 申請（專利權）人: 南京大學
• 主分類號: G06T11/00
• 分類號: G06T11/00
• 代理公司: 南京蘇高專利商標事務所(普通合伙)
• 代理人: 柏尚春

1.一種矩形窗口中的圓弧快速裁剪方法，其特征在于，該方法包括以下步驟：

(1)輸入矩形裁剪窗口坐標；

(2)輸入待裁剪圓弧坐標；

(3)以圓弧起點、終點坐標為索引，直接查表一來獲取該圓弧的整體包圍盒；所述表一的第一列至第三列為始點與終點的象限位置，第四列至第七列為圓弧的包圍盒形成規則；其中第一列為起點P_s(x_s，y_s)所在象限，第二列為終點P_e(x_e，y_e)所在象限，第三列為起點與終點橫坐標的大小關系，第四列至第七列中x_left，y_bot，x_right，y_top分別為圓弧整體包圍盒邊界；

(4)比較步驟(3)中的圓弧整體包圍盒與矩形裁剪窗口，判斷圓弧整體包圍盒是否位于裁剪窗口內，若結果為是，則輸出該圓弧，并返回步驟(1)，否則進行下一步；

(5)比較該圓弧整體包圍盒與裁剪窗口，若圓弧整體包圍盒位于裁剪窗口外，若結果為是，則舍棄該圓弧，并返回步驟(2)，否則進行下一步；

(6)將待裁剪圓弧分割為多個象限圓弧段；

(7)以待裁剪圓弧起點、終點坐標為索引，通過查表二直接獲取其各分割后的象限圓弧段及其對應的象限圓弧段包圍盒；所述表二的第一列至第三列為起點與終點的象限位置，第四列和第五列分別為象限圓弧段的起點坐標值和終點坐標值，第六列至第九列為象限圓弧段的包圍盒；其中，第一列為圓弧起點P_s(x_e，y_s)所在象限，第二列為圓弧終點P_e(x_e，y_e)所在象限，第三列為起點與終點橫坐標的大小關系，第六列X_left為每個象限圓弧段的包圍盒的左邊界，第七列y_bot為每個象限圓弧段的包圍盒的下邊界，第八列x_right為每個象限圓弧段的包圍盒的右邊界，第九列y_top為每個象限圓弧段的包圍盒的上邊界；

(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)。

2.如權利要求1所述的矩形窗口中的圓弧快速裁剪方法，其中所輸入的待裁剪圓弧為逆時針方向，由其圓心、始點和終點定義。

3.如權利要求1或2所述的矩形窗口中的圓弧快速裁剪方法，坐標系原點位于待裁剪圓弧的圓心；否則先將坐標系原點平移至圓弧圓心，裁剪結束后再平移回去。

4.如權利要求3所述的矩形窗口中的圓弧快速裁剪方法，步驟(6)中以圓心為原點建立坐標系后，所述圓弧的象限圓弧段為被坐標軸切割的圓弧任一部分。