[發明專利]提取最小封閉圖形的方法

有效

• 申請號: 201310034839.2
• 申請日: 2013-01-30
• 公開（公告）號: CN103116900A
• 公開（公告）日: 2013-05-22
• 發明（設計）人: 李嘉
• 申請（專利權）人: 深圳聯友科技有限公司
• 主分類號: G06T11/20
• 分類號: G06T11/20;G06F17/50
• 代理公司: 深圳市順天達專利商標代理有限公司 44217
• 代理人: 高占元

技術領域

本發明涉及圖形處理技術領域，尤其涉及一種計算任意交叉的直線線段提取所有互不覆蓋的最小封閉圖形的方法。

背景技術

開發CAD圖形平臺的時候，需要針對對用戶繪制的線條切割出互不覆蓋的最小的封閉圖形。

現有的任意相交直線線段提取所有互不覆蓋的封閉圖形算法的方法，如圖1所示，一般是遍歷所有線條，提取所有封閉圖形，將提取的封閉圖形進行覆蓋判斷，過濾互相覆蓋的圖形，得到所有互不覆蓋的最小單元封閉圖形。當線條復雜、交點數量大的時候提取封閉圖形的的效率低、需時長。

發明內容

本發明要解決的技術問題在于，針對現有技術提取最小封閉圖形效率低、需時長等的缺陷，提供一種計算任意交叉的直線線段提取所有互不覆蓋的最小封閉圖形的方法。

本發明解決其技術問題所采用的技術方案是：

根據本發明的一方面，提供一種提取最小封閉圖形的方法，包括：

S1、建立交點信息表；

S2、根據交點信息表，確定構成封閉圖形的交點；

S3、逐一判斷確定的多個封閉圖形中，是否存在包含了所有交點的封閉圖形，如是，則刪除封閉圖形；

S4、保存為最終結果。

優選的，所述S1具體包括：

S11、計算所有線段的交點；

S12、提取所有交點組成的有向線段列表；

S13、提取以同一起點的關聯線段列表；

S14、以起點為原點及水平方向射線為基線，計算關聯線段的終點與基線形成的象限角；

S15、根據象限角的大小，對同一起點的關聯線段進行排序形成有向線段集合。

優選的，所述S2具體包括：

S21、判斷交點信息表中的有向線段集合是否為空，若是，則跳轉S3；若否，則執行S22；

S22、從有向線段集合中提取任意一條有向線段作為起始邊，確定封閉圖形的起點和第二個點；

S23、在有向線段集合中，找到有向線段的反向邊的序列位置L；

S24、判斷L是否是最后一個序列位置，如是，則執行S25；如否，則執行S26；

S25、提取序列位置為1的有向線段作為封閉圖形的下一條邊線，并執行S27；

S26、提取L的下一序列位置的有向線段，作為組成封閉圖形的下一條邊線；

S27、把確定的有向線段從有向線段集合中刪除；

S28、判斷確定的交點是否和起點相同；若否，則提取下一條邊線，并跳轉S22；若是，封閉圖形提取成功，保存到封閉圖形列表中，并跳轉S21。

優選的，所述判斷L是否是最后一個序列位置具體為：當交點存在n條關聯線段，根據所述象限角排序后，處于第n條線段的就是最后一個序列位置的線段。

實施本發明的提取最小封閉圖形的方法的技術方案，具有以下優點或有益效果：本發明可快速提取最小封閉圖像，尤其是在交點數量大的時候，可快速提取互不覆蓋的最小封閉圖形，效率高。

附圖說明

為了更清楚地說明本發明實施例的技術方案，下面將對實施例描述中所需要使用的附圖作簡單的介紹，顯而易見，下面描述中的附圖僅僅是本發明的一些實施例，對于本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據這些附圖獲得其他的附圖，附圖中：

圖1是現有技術提取封閉圖形的方法實施例的流程示意圖；

圖2是本發明提取封閉圖形的方法第一實施例的流程示意圖；

圖3是本發明提取封閉圖形的方法第一實施例的S1的流程示意圖；

圖4是本發明提取封閉圖形的方法第一實施例的S2的流程示意圖；

圖5是本發明提取封閉圖形的方法第二實施例的交點示意圖；

圖6是本發明提取封閉圖形的方法第二實施例的有向線段示意圖。

具體實施方式

為了使本發明的目的、技術方案及優點更加清楚明白，下文將要描述的各種實施例將要參考相應的附圖，這些附圖構成了實施例的一部分，其中描述了實現本發明可能采用的各種實施例。應明白，還可使用其他的實施例，或者對本文列舉的實施例進行結構和功能上的修改，而不會脫離本發明的范圍和實質。

本發明提取最小封閉圖形的方法第一實施例，如圖2所示，包括：

S1、建立交點信息表；

S2、根據交點信息表，確定構成封閉圖形的交點；

S3、逐一判斷確定的多個封閉圖形中，是否存在包含了所有交點的封閉圖形，如是，則刪除所述封閉圖形；如否，則跳轉S4；

S4、保存為最終結果。