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

有效

• 申請(qǐng)?zhí)枺?/td>: 201310228923.8
• 申請(qǐng)日: 2013-06-09
• 公開(kāi)（公告）號(hào): CN103258061A
• 公開(kāi)（公告）日: 2013-08-21
• 發(fā)明（設(shè)計(jì)）人: 陳紅倩;陳誼;劉鸝;曹健;張金躍;林曉蕾
• 申請(qǐng)（專利權(quán)）人: 北京工商大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

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

步驟1、讀入超圖數(shù)據(jù)，將讀入的超圖數(shù)據(jù)分別存儲(chǔ)為節(jié)點(diǎn)數(shù)據(jù)和超邊數(shù)據(jù)，節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)保存至一個(gè)結(jié)構(gòu)體中，節(jié)點(diǎn)信息使用數(shù)組存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)；超邊信息使用鏈表存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)；

步驟2、將步驟1中讀入的超邊沿超邊的垂線方向往兩側(cè)方向進(jìn)行擴(kuò)展，根據(jù)超邊中所含節(jié)點(diǎn)的順序，將超邊所涉及的節(jié)點(diǎn)分為中間節(jié)點(diǎn)和末端節(jié)點(diǎn)，并分別計(jì)算其“擴(kuò)展點(diǎn)”；針對(duì)中間節(jié)點(diǎn)，首先根據(jù)該中間節(jié)點(diǎn)與其兩側(cè)鄰接節(jié)點(diǎn)的連接線，計(jì)算“過(guò)中間節(jié)點(diǎn)的兩連接線角平分線”，然后根據(jù)所設(shè)定的超邊包圍區(qū)域?qū)挾萕，在該角平分線上中間節(jié)點(diǎn)的兩側(cè)，分別找到與中間節(jié)點(diǎn)距離為W的點(diǎn)，作為該中間節(jié)點(diǎn)的“擴(kuò)展點(diǎn)”；針對(duì)末端節(jié)點(diǎn)，首先根據(jù)該末端節(jié)點(diǎn)與其鄰接節(jié)點(diǎn)的連接線，計(jì)算一條“過(guò)末端節(jié)點(diǎn)并垂直于連接線”的垂線，然后根據(jù)所設(shè)定的超邊包圍區(qū)域?qū)挾萕，在該垂線上末端節(jié)點(diǎn)的兩側(cè)，分別找到與末端節(jié)點(diǎn)距離為W的點(diǎn)，作為該末端節(jié)點(diǎn)的“擴(kuò)展點(diǎn)”；

步驟3、通過(guò)步驟2所獲得的擴(kuò)展點(diǎn)，進(jìn)行同側(cè)擴(kuò)展點(diǎn)歸并，根據(jù)擴(kuò)展點(diǎn)與超邊的相對(duì)位置關(guān)系，分為兩個(gè)擴(kuò)展點(diǎn)鏈表；

步驟4、針對(duì)步驟3中歸并獲得的兩條擴(kuò)展點(diǎn)鏈，將其進(jìn)行重組為兩個(gè)控制點(diǎn)數(shù)組；

步驟5、對(duì)步驟4中獲得的兩個(gè)控制點(diǎn)數(shù)組，分別使用Catmull-Rom算法進(jìn)行曲線插值計(jì)算，根據(jù)所設(shè)定的插值點(diǎn)數(shù)M，將獲得M個(gè)插值點(diǎn)，連接控制點(diǎn)和M個(gè)插值點(diǎn)，將在兩個(gè)擴(kuò)展點(diǎn)之間獲得的一段平滑曲線；

步驟6、將步驟5中獲得的區(qū)域邊界曲線的各個(gè)子段，分類為始終位于超邊一側(cè)的子段和跨越超邊兩側(cè)的子段，并分別稱之為“同側(cè)子段”和“跨側(cè)子段”，每個(gè)同側(cè)子段存在于一對(duì)超邊節(jié)點(diǎn)的擴(kuò)展點(diǎn)之間，并必然在超邊的另一側(cè)存在一個(gè)對(duì)應(yīng)的同側(cè)子段；跨側(cè)子段將位于超邊的末端節(jié)點(diǎn)位置附近；對(duì)于擁有N個(gè)節(jié)點(diǎn)的超邊來(lái)說(shuō)，將擁有2*(N-1)個(gè)同側(cè)子段，以及2個(gè)跨側(cè)子段；對(duì)于同側(cè)子段，將其與超邊另一側(cè)的對(duì)應(yīng)子段進(jìn)行配對(duì)，并將插值點(diǎn)交叉間隔存儲(chǔ)；對(duì)于跨側(cè)子段，將其獨(dú)立存儲(chǔ)，以便于OpenGL的三角扇繪制；

步驟7、對(duì)超圖中的每一條超邊，使用色相環(huán)理論進(jìn)行著色，即根據(jù)超圖中超邊的數(shù)量，自動(dòng)為各條超邊添加顏色，從而增強(qiáng)超圖中各條超邊的區(qū)分度，增強(qiáng)超圖繪制結(jié)果的直觀性；

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

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

2.如權(quán)利要求1所述的一種基于插值算法的區(qū)域包圍式超圖可視化方法，其特征在于：歸并方法為，首先將首點(diǎn)的兩個(gè)擴(kuò)展點(diǎn)，分別存入兩個(gè)“擴(kuò)展點(diǎn)鏈表”中；然后判斷下一節(jié)點(diǎn)的兩個(gè)擴(kuò)展點(diǎn)與超邊的位置關(guān)系，并據(jù)此存入與該擴(kuò)展點(diǎn)位于超邊同側(cè)的鏈中；循環(huán)執(zhí)行位置關(guān)系判斷，并加入到相應(yīng)的“擴(kuò)展點(diǎn)鏈表”中，直至最后一個(gè)節(jié)點(diǎn)。

3.如權(quán)利要求1所述的一種基于插值算法的區(qū)域包圍式超圖可視化方法，其特征在于：將兩條擴(kuò)展點(diǎn)鏈進(jìn)行重組為兩個(gè)控制點(diǎn)數(shù)組方法為，針對(duì)兩條擴(kuò)展點(diǎn)鏈，分別定義為鏈A和鏈B，并定義超邊的第一個(gè)節(jié)點(diǎn)的擴(kuò)展點(diǎn)作為鏈頭；對(duì)于鏈A，首先借用鏈B中的第2個(gè)和第1個(gè)擴(kuò)展點(diǎn)，為其在對(duì)應(yīng)的控制點(diǎn)數(shù)組中建立第1、2個(gè)控制點(diǎn)，將位置信息賦值給這兩個(gè)控制點(diǎn)；然后將鏈A的所有擴(kuò)展點(diǎn)，依次為其建立控制點(diǎn)，并將其位置信息賦值給控制點(diǎn)；最后借用鏈B的最后1個(gè)擴(kuò)展點(diǎn)，為其建立控制點(diǎn)，并將位置坐標(biāo)賦值給控制點(diǎn)；對(duì)于鏈B，首先借用鏈A中的第1個(gè)擴(kuò)展點(diǎn)，為其在對(duì)應(yīng)的控制點(diǎn)數(shù)組中建立第1個(gè)控制點(diǎn)，將位置信息賦值給該控制點(diǎn)；然后將鏈B的所有擴(kuò)展點(diǎn)，依次為其建立控制點(diǎn)，并將其位置信息賦值給控制點(diǎn)；最后借用鏈A的倒數(shù)第2個(gè)擴(kuò)展點(diǎn)和最后1個(gè)擴(kuò)展點(diǎn)，為其建立控制點(diǎn)，并將位置信息賦值給這兩個(gè)控制點(diǎn)。