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

無效

• 申請號: 201110301235.0
• 申請日: 2011-10-08
• 公開（公告）號: CN102509258A
• 公開（公告）日: 2012-06-20
• 發明（設計）人: 陸添超;路通
• 申請（專利權）人: 南京大學
• 主分類號: G06T3/00
• 分類號: G06T3/00
• 代理公司: 江蘇圣典律師事務所 32237
• 代理人: 胡建華

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

步驟1：輸入矩形窗口的坐標，包括矩形窗口左上角頂點和右下角頂點的坐標；

步驟2：輸入待裁剪的橢圓弧的坐標，包括了橢圓弧的起點坐標、終點坐標以及橢圓弧的長軸和水平坐標軸的夾角；

步驟3：以橢圓弧起點坐標和終點坐標，根據橢圓弧所屬橢圓為正則橢圓或非正則橢圓查整體包圍盒表獲得橢圓弧的整體包圍盒，所述整體包圍盒查詢表包括正則橢圓整體包圍盒查詢表和非正則橢圓整體包圍盒查詢表；

步驟4：比較所述橢圓弧整體包圍盒和矩形窗口，判斷橢圓弧整體包圍盒是否位于矩形窗口內，若結果為是，則輸出該橢圓弧，并轉入步驟23，否則進行步驟5；

步驟5：比較該橢圓弧整體包圍盒與矩形窗口，判斷橢圓弧整體包圍盒是否位于矩形窗口外，若結果為是，則舍棄該待裁剪的橢圓弧，并轉入步驟23，否則進行步驟6；

步驟6：將待裁剪橢圓弧根據四個象限分割為多個象限橢圓弧段，橢圓弧落在幾個象限內就被坐標軸分割為對應個數的象限橢圓弧段；

步驟7：根據待裁剪橢圓弧起點坐標、終點坐標，查象限橢圓弧段表獲得各分割后的象限橢圓弧段及其對應的象限橢圓弧段包圍盒；

步驟8：比較各象限橢圓弧段包圍盒與矩形窗口，若各象限橢圓弧段包圍盒均在矩形窗口外，則舍棄待裁剪橢圓弧，并轉入步驟23，否則進行步驟9；

步驟9，根據矩形窗口上邊界、下邊界、左邊界及右邊界的延長線將坐標系分為九個分區，由上至下、由左至右分別依次編碼為1區到9區；

步驟10，遍歷各分割后的象限橢圓弧段，取各個象限橢圓弧段的起點坐標、終點坐標，確定起點、終點所在分區的編碼；

步驟11：判斷橢圓弧所屬橢圓是否為正則橢圓，如果是正則橢圓，則轉到步驟12，否則轉步驟14；

步驟12：根據各個象限橢圓弧段起點、終點所在分區，及矩形窗口與各象限橢圓弧段的關系，判斷各個象限橢圓弧段是否在矩形窗口外，如果是，則舍棄該待裁剪的橢圓弧，并轉入步驟23，否則轉步驟13；

步驟13：根據點P1(0.25A，0.6124B)、點P2(0.5A，0.866B)、點P3(0.7071A，0.7071B)、點P4(0.866A，0.5B)將象限橢圓弧段分成子段；其中A是橢圓長軸的長度，B是短軸的長度；

步聚14：將點P1(0.25A，0.6124B)、點P2(0.5A，0.866B)、點P3(0.7071A，0.7071B)、點P4(0.866A，0.5B)旋轉至待裁剪橢圓弧所屬的橢圓上作為分段點，將非正則橢圓弧分成子段；

步驟15：查子段包圍盒表得到各子段的包圍盒；所述子段包圍盒表包括子段包圍盒的總表、包含始點的非完整橢圓弧子段包圍盒修改表以及包含終點的非完整橢圓弧子段包圍盒修改表三個表；

步驟16：比較橢圓弧各子段的包圍盒與矩形窗口，若各子段均在矩形窗口外，則舍棄待裁剪橢圓弧，并轉入步驟23，否則進行步驟17；

步驟17：將橢圓弧各子段按比例變換到規范化坐標空間的半徑為R的圓弧，即使橢圓長軸與短軸長度等同于圓弧半徑R，矩形窗口按照相同的比例變換；

步驟18：對矩形窗口左右兩邊界的X坐標和矩形窗口上下兩邊界的Y坐標作比例變換，比例因子為1024/R，所述X坐標和Y坐標分別為標準坐標系中的橫坐標和縱坐標；矩形窗口左右兩邊界和上下兩邊界的求交順序根據求交順序表來確定；

步驟19：根據變換后的X坐標和Y坐標查規范化圓弧直線交點的坐標表，獲得規范化圓弧直線交點坐標，即Y坐標和X坐標；

步驟20：對所述坐標實施反比例變換，得到圓弧直線實際交點坐標，比例因子為R/1024；

步驟21：根據圓弧直線實際交點坐標，對所輸入圓弧進行裁剪；

步驟22：將規范化圓反比例變換為橢圓，得到一個或多個橢圓弧段；

步驟23：輸出并顯示最終裁剪結果。

2.根據權利要求1中所述的矩形窗口中橢圓曲線的快速裁剪方法，其特征在于，所輸入的待裁剪橢圓弧為逆時針方向，由其橢圓心、長軸與水平坐標軸的夾角、始點和終點描述，且經過平移后將坐標軸原點設定于待裁剪橢圓弧的圓心。