[發明專利]多邊形裁剪中交點為多邊形頂點的進出性判別方法有效

申請號：	201410251976.6	申請日：	2014-06-09
公開（公告）號：	CN104036533B	公開（公告）日：	2017-02-15
發明（設計）人：	王慧青;崇素文;王慶;李玲	申請（專利權）人：	東南大學
主分類號：	G06T11/00	分類號：	G06T11/00
代理公司：	南京蘇高專利商標事務所(普通合伙)32204	代理人：	柏尚春
地址：	210096 ***	國省代碼：	江蘇;32
權利要求書：	查看更多	說明書：	查看更多
摘要：
搜索關鍵詞：	多邊形裁剪交點頂點進出判別方法
鉆瓜網技術展會專利詞庫專利權人專利榜在售專利公布日期熱門專利

【說明書】：

技術領域

本發明涉及一種計算機圖形學領域，具體涉及一種多邊形裁剪中交點為多邊形頂點的進出性判別方法。

背景技術

多邊形的裁剪是圖形學中的基本操作，一般多邊形之間的裁剪過程為裁剪多邊形與實體多邊形定點的順序存儲、裁剪多邊形與實體多邊形之間交點求解、多邊形交點的進出性判別、多邊形交點分別插入裁剪多邊形與實體多邊形的頂點集合，通過交點的進出性交替便利裁剪多邊形和實體多邊形得到裁剪結果。

現有技術中存在的問題是：當裁剪多邊形與實體多邊形存在頂點或邊合的情況時，在求解裁剪多邊形與主多邊形的交點時存在多個相同的交點，并且交點的進出性判定不一致，從而無法準確的插入裁剪多邊形和實體多邊形的頂點集合中，同時無法根據交點的進出性得到準確的裁剪結果。

發明內容

發明目的：本發明的目的在于解決現有技術中存在的不足，提供一種多邊形裁剪中交點為多邊形頂點的進出性判別方法。

技術方案：本發明的一種多邊形裁剪中交點為多邊形頂點的進出性判別方法，包括以下具體步驟：

(1)在裁剪多邊形C與實體多邊形S之間交點求解，且在交點的進出性預判別之后，計算交點集合中具有相同坐標交點的個數；其中，用C_i代表裁剪多邊形的第i個頂點，用S_j代表實體多邊形的第j個頂點，T表示裁剪多邊形和實體多邊形求交后的交點集合，T_k代表添加到裁剪多邊形中交點集合T中第k個交點，Q_l代表添加到實體多邊形頂點序列中交點集合Q的第l個點，其中i,j,k,l∈[1,2…,n]，NT為新添加到裁剪多邊形頂點序列新添加到T_k中的交點，NQ為新添加到Q_l中的交點；

(2)當具有相同坐標交點的個數N等于2時，說明裁剪多邊形與實體多邊形存在相同的頂點，且頂點坐標等于交點坐標，假設這兩個交點分別表示為T_k與T_k+1，Q中與T_k與T_k+1坐標相同的兩個交點分別為Q_l與Q_l+1，則該頂點進出性的判別步驟如下：

(21)如果T_k與T_k+1的進出性相同：

①若交點T_k與T_k+1的坐標與頂點C_i坐標不相等，交點Q_l與Q_l+1的坐標與頂點S_j坐標相同，則交點T_k與T_k+1是裁剪過程中的需要添加的交點，添加一個交點NT，該交點坐標及進出性均與T_k相同，且交點Q_l與Q_l+1是裁剪過程中的頂點坐標，設置S_j的進出性與頂點C_i的進出性相異；

②若交點T_k與T_k+1的坐標與頂點C_i坐標相等，交點Q_l與Q_l+1的坐標與頂點S_j坐標相同，則交點T_k與T_k+1是裁剪過程中頂點，設置頂點C_i的進出性等于交點T_k與T_k+1的進出性，交點Q_l與Q_l+1是裁剪過程中需要添加的交點，添加一個新點NQ，該交點坐標及其進出性與Q_l相同；