[發明專利]基于快速分組搜索技術的CAD網絡拓撲圖分析方法

有效

• 申請號: 201110260519.X
• 申請日: 2011-09-05
• 公開（公告）號: CN102323966A
• 公開（公告）日: 2012-01-18
• 發明（設計）人: 胡華威;林俊;郭樂;楊合恭
• 申請（專利權）人: 江蘇西電南自智能電力設備有限公司
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 南京縱橫知識產權代理有限公司 32224
• 代理人: 董建林

1.一種基于快速分組搜索技術的CAD網絡拓撲圖分析方法，其特征在于：包括以下步驟

(1)、圖元定義：對CAD內部除了自帶的線型圖元外的各圖元之間的連接關系進行定義，具體包括以下步驟：

A、將所需要的圖元定義成圖塊形式；

B、在圖塊上添加統一的特殊端子作為判斷連接關系的依據，特殊端子的定義如下：以半徑為r的圓以及其圓心位置為P的點構成的圖塊，所有圖元之間的判斷就以各自圖元相對P點作為判斷基礎；而半徑為r的圓作為識別P端子和提供CAD吸附功能的前提條件；

C、在各圖塊上分別定義自己的屬性，包括位置、顏色、大小，相關系統可以根據需要擴展屬性作為分析的依據；

(2)、根據定義的各類圖元繪制圖形，并通過CAD自帶的各類線型連接圖元，同時對各圖塊定義的屬性進行賦值；

(3)、分析網絡拓撲圖：對于一張繪制好的圖形，圖元間的連接方式有兩種：一是直接連接，即圖元間的特殊端子重合；二是間接連接，即特殊端子間通過若干CAD的線型圖元進行連接；

對于直接連接的方式，只需通過遍歷特殊端子的重合關系即可，假設自定義圖元分別為A1，A2，.....An，各圖元存在的特殊端子數分別為D1，D2，......Dn，則所需時間頻度為T(n)=Σi=1n(Di*Σj=1,i!=jnDj)=0(n2);]]>

對于間接連接的方式，采用如下方法分析：

A、對所有線型圖元進行分組：以線型圖元間最大連接串進行分組為原則，連接串獲取方法如下：循環遍歷各線型圖元間的連接關系，把連接的圖元放入相同的數組當中，并對分析到一對多連接的圖元進行數組復制，增加連接串；直到循環一遍之后沒有在所有數組中增加新圖元則退出，假設線型圖元數目為m，每條線端子數為2，最壞情況下每次循環都需要添加圖元，則時間復雜度為O(m³)；

B、遍歷自定義圖元：對于每一個連接串，可以認為是一條包含若干端點的線，如果需要搜索的兩個自定義圖元的各自一個特殊端子存在于一條連接串中，則兩圖元必定連接，所以只需遍歷每兩個圖元的特殊端子在數組中的包含關系即可；時間頻度和直接連接分析方法一樣為

由此，分析整張圖紙網絡拓撲關系只需時間復雜度為O(m³+n²)。

2.根據權利要求1所述的一種基于快速分組搜索技術的CAD網絡拓撲圖分析方法，其特征在于：在步驟(1)的C步驟之后還包括步驟D：CAD自帶線型圖元可作為帶有端子的圖元進行連接判斷基礎。