[發(fā)明專利]圖形處理方法

有效

• 申請?zhí)枺?/td>: 201110202619.7
• 申請日: 2011-07-19
• 公開（公告）號: CN102890815A
• 公開（公告）日: 2013-01-23
• 發(fā)明（設計）人: 牟文杰
• 申請（專利權）人: 上海博泰悅臻電子設備制造有限公司
• 主分類號: G06T3/00
• 分類號: G06T3/00;G09B29/00
• 代理公司: 北京集佳知識產(chǎn)權代理有限公司 11227
• 代理人: 駱蘇華

技術領域

本發(fā)明涉及矢量化數(shù)據(jù)技術領域，尤其涉及一種用于電子地圖的圖形處理方法。

背景技術

在地理信息系統(tǒng)(Geographic?Information?System，GIS)、車載導航系統(tǒng)以及互聯(lián)網(wǎng)地圖應用領域，都會應用到矢量化的地圖數(shù)據(jù)，對這些矢量化數(shù)據(jù)的處理是上述領域的一個重要工作。其中，對于多邊形的切割處理是一個較難的技術點。

具體地，在多邊形圖形顯示的過程中，往往需要確定多邊形圖形的哪些部分落在顯示區(qū)域內(nèi)，哪些部分落在顯示區(qū)域之外。所述顯示區(qū)域為用于顯示的視口或視區(qū)，如顯示器所對應的區(qū)域。以便只顯示位于顯示區(qū)域內(nèi)的圖形，進而簡化矢量化數(shù)據(jù)的處理程序。一般通過切割的方法以決定圖形中哪些部分位于顯示區(qū)域內(nèi)。即需要對多邊形圖形進行一些幾何上的切割處理，以便去除落在顯示區(qū)域之外的部分，保留位于顯示區(qū)域以內(nèi)的部分。

現(xiàn)有技術提供有多種多邊形處理算法，如Sutherland-Hodgeman算法，所述算法是基于用直線對多邊形進行切割。但所述算法在切割凹多邊形可能會形成若干子多邊形，且所述子多邊形之間不是相互獨立，并通過位于子多邊形之間的來回切割邊將所述多個子多邊形連接，以形成一個封閉的多邊形。即各個子多邊形之間還存在有不必要的切割邊，使得計算量增大，降低計算效率。這樣的結果不但增加額外的切割邊，而且在某些繪圖系統(tǒng)中還不能正常地將多個子多邊形進行連接，以獲得封閉的多邊形。

現(xiàn)有技術還提供一種多邊形切割算法Weiler-Atherton算法，雖然可以正確處理凹多邊形的切割，但是算法復雜性比較高，計算效率低，其時間復雜度為O(n^2)。

具體的關于時間復雜度表述如下：算法在處理一個由n個元素組成的對象時，處理時間為以n為變量的函數(shù)f(n)，且處理時間會隨著數(shù)值n的增大而增大，對應地：若函數(shù)f(n)表示為f(n)＝A*n，則時間復雜度為O(n)級別；若函數(shù)f(n)表示為f(n)＝A*n^2+B*n+C，則時間復雜度為O(n^2)，以此類推。即算法的時間復雜度主要是由函數(shù)f(n)的最高次冪決定的。

基于上述情況，需要一種圖形處理方法，不僅能夠處理凹多邊形，而且算法較簡單，計算效率高，時間復雜度低。

發(fā)明內(nèi)容

本發(fā)明解決的問題是提供一種圖形處理方法，能夠對多邊形進行正確切割處理，且算法簡單、計算效率高、時間復雜度低。

為解決上述問題，本發(fā)明提供一種圖形處理方法，包括：

提供待處理多邊形和顯示區(qū)域，所述顯示區(qū)域和待處理多邊形具有重疊區(qū)域；

將所述待處理多邊形存儲至多邊形隊列單元，形成多邊形隊列，后續(xù)圖形處理僅對多邊形隊列進行處理；

將所述顯示區(qū)域的邊作為切割邊，并依次選取顯示區(qū)域的切割邊對所述多邊形隊列進行切割，直至顯示區(qū)域所有的邊均對所述多邊形隊列進行切割；

其中，在顯示區(qū)域的每一邊對所述多邊形隊列切割后，還包括判斷切割結果是否至少由一個以上非獨立的子多邊形構成：

若是，則切割結果為待拆分多邊形，并對所述待拆分多邊形進行拆分，形成若干數(shù)目相互獨立的子多邊形，并將拆分后的子多邊形更新至多邊形隊列；

若否，則將所述切割結果更新至多邊形隊列。

可選的，所述待處理多邊形分為保留部分和舍棄部分，所述保留部分位于所述顯示區(qū)域內(nèi)，所述舍棄部分位于所述顯示區(qū)域外。

可選的，對所述待拆分多邊形進行拆分包括：提供經(jīng)顯示區(qū)域的切割邊切割獲得的切割結果，所述切割結果至少由一個以上非獨立的子多邊形構成；所述切割邊與待拆分多邊形的交點為切割點；定義切割邊的第一方向及切割點序號，沿第一方向，所述切割點序號依次增大，按照排序后的切割點建立索引；按索引對待拆分多邊形進行拆分。

可選的，所述第一方向為所述切割邊兩端中選定的一端的延長方向。

可選的，按照如下順序對切割點進行排序：將待處理多邊形放置于正交坐標系中，所述正交坐標系包括X軸和Y軸；若切割邊與X軸夾角絕對值小于45°，則切割點按X值從小到大排序；若切割邊與X軸夾角絕對值不小于45°，則切割點按Y值從小到大排序。

可選的，定義待處理多邊形的線條走向，使得在索引中序號最小的切割點處，所述待處理多邊形的線條由顯示區(qū)域外進入顯示區(qū)域內(nèi)。

可選的，沿所述待處理多邊形的線條走向，所述切割點分為入點和出點：在所述入點處，所述待處理多邊形的線條由顯示區(qū)域外進入顯示區(qū)域內(nèi)；在所述出點處，所述待處理多邊形的線條由顯示區(qū)域內(nèi)進入顯示區(qū)域外。