[發明專利]一種基于插值算法的區域包圍式超圖可視化方法

有效

• 申請號: 201310228923.8
• 申請日: 2013-06-09
• 公開（公告）號: CN103258061A
• 公開（公告）日: 2013-08-21
• 發明（設計）人: 陳紅倩;陳誼;劉鸝;曹健;張金躍;林曉蕾
• 申請（專利權）人: 北京工商大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于插值算法的區域包圍式超圖可視化方法，其特征在于包括如下步驟：

步驟1、讀入超圖數據，將讀入的超圖數據分別存儲為節點數據和超邊數據，節點的數據結構保存至一個結構體中，節點信息使用數組存儲結構進行存儲；超邊信息使用鏈表存儲結構進行存儲；

步驟2、將步驟1中讀入的超邊沿超邊的垂線方向往兩側方向進行擴展，根據超邊中所含節點的順序，將超邊所涉及的節點分為中間節點和末端節點，并分別計算其“擴展點”；針對中間節點，首先根據該中間節點與其兩側鄰接節點的連接線，計算“過中間節點的兩連接線角平分線”，然后根據所設定的超邊包圍區域寬度W，在該角平分線上中間節點的兩側，分別找到與中間節點距離為W的點，作為該中間節點的“擴展點”；針對末端節點，首先根據該末端節點與其鄰接節點的連接線，計算一條“過末端節點并垂直于連接線”的垂線，然后根據所設定的超邊包圍區域寬度W，在該垂線上末端節點的兩側，分別找到與末端節點距離為W的點，作為該末端節點的“擴展點”；

步驟3、通過步驟2所獲得的擴展點，進行同側擴展點歸并，根據擴展點與超邊的相對位置關系，分為兩個擴展點鏈表；

步驟4、針對步驟3中歸并獲得的兩條擴展點鏈，將其進行重組為兩個控制點數組；

步驟5、對步驟4中獲得的兩個控制點數組，分別使用Catmull-Rom算法進行曲線插值計算，根據所設定的插值點數M，將獲得M個插值點，連接控制點和M個插值點，將在兩個擴展點之間獲得的一段平滑曲線；

步驟6、將步驟5中獲得的區域邊界曲線的各個子段，分類為始終位于超邊一側的子段和跨越超邊兩側的子段，并分別稱之為“同側子段”和“跨側子段”，每個同側子段存在于一對超邊節點的擴展點之間，并必然在超邊的另一側存在一個對應的同側子段；跨側子段將位于超邊的末端節點位置附近；對于擁有N個節點的超邊來說，將擁有2*(N-1)個同側子段，以及2個跨側子段；對于同側子段，將其與超邊另一側的對應子段進行配對，并將插值點交叉間隔存儲；對于跨側子段，將其獨立存儲，以便于OpenGL的三角扇繪制；

步驟7、對超圖中的每一條超邊，使用色相環理論進行著色，即根據超圖中超邊的數量，自動為各條超邊添加顏色，從而增強超圖中各條超邊的區分度，增強超圖繪制結果的直觀性；

步驟8、使用OpenGL中的折線(GL_LINE_STRIP)模式繪制超邊包圍區域的邊界曲線，使用OpenGL中的三角帶(GL_TRIANGLE_STRIP)模式繪制已配對并交叉存儲的同側子段部分，使用OpenGL中的三角扇(GL_TRIANGLE_FAN)模式繪制跨側子段部分；

步驟9：判斷超圖中的所有超邊是否繪制完畢，如還有未繪制超邊，則跳轉至步驟2，進行下一條超邊的繪制。

2.如權利要求1所述的一種基于插值算法的區域包圍式超圖可視化方法，其特征在于：歸并方法為，首先將首點的兩個擴展點，分別存入兩個“擴展點鏈表”中；然后判斷下一節點的兩個擴展點與超邊的位置關系，并據此存入與該擴展點位于超邊同側的鏈中；循環執行位置關系判斷，并加入到相應的“擴展點鏈表”中，直至最后一個節點。

3.如權利要求1所述的一種基于插值算法的區域包圍式超圖可視化方法，其特征在于：將兩條擴展點鏈進行重組為兩個控制點數組方法為，針對兩條擴展點鏈，分別定義為鏈A和鏈B，并定義超邊的第一個節點的擴展點作為鏈頭；對于鏈A，首先借用鏈B中的第2個和第1個擴展點，為其在對應的控制點數組中建立第1、2個控制點，將位置信息賦值給這兩個控制點；然后將鏈A的所有擴展點，依次為其建立控制點，并將其位置信息賦值給控制點；最后借用鏈B的最后1個擴展點，為其建立控制點，并將位置坐標賦值給控制點；對于鏈B，首先借用鏈A中的第1個擴展點，為其在對應的控制點數組中建立第1個控制點，將位置信息賦值給該控制點；然后將鏈B的所有擴展點，依次為其建立控制點，并將其位置信息賦值給控制點；最后借用鏈A的倒數第2個擴展點和最后1個擴展點，為其建立控制點，并將位置信息賦值給這兩個控制點。