[發(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ú)信息

技術(shù)領(lǐng)域

本發(fā)明涉及一種基于插值算法的區(qū)域包圍式超圖可視化方法，屬于計(jì)算機(jī)應(yīng)用領(lǐng)域，特別是計(jì)算機(jī)圖形學(xué)與可視化技術(shù)領(lǐng)域。針對(duì)超圖可視化中超邊表達(dá)不直觀，使用計(jì)算機(jī)實(shí)現(xiàn)算法復(fù)雜的問(wèn)題，給出了一種直觀、有效、快速的超圖可視化方法。

技術(shù)背景

隨著圖理論在數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)領(lǐng)域越來(lái)越廣泛的應(yīng)用，基于超圖理論的數(shù)據(jù)表示和數(shù)據(jù)挖掘方法的研究變得越來(lái)越重要。

超圖是圖的一種變化類型，能在一條邊中表示多個(gè)節(jié)點(diǎn)之間的數(shù)據(jù)關(guān)系。超圖是一種非線性結(jié)構(gòu)，一個(gè)超圖G可以定義為G＝(V，E)，其中V＝{V₁，V₂，...，V_n}，是一個(gè)有窮非空的元素集合，稱為節(jié)點(diǎn)集或頂點(diǎn)集；E＝{e₁，e₂，...，e_m}，其中任意一個(gè)e_i(1≤i≤m)都是V的非空子集的集合，稱為超邊，當(dāng)超邊中的節(jié)點(diǎn)無(wú)先后順序時(shí)，稱為無(wú)向邊，當(dāng)有順序時(shí)，稱為有向邊。

在數(shù)學(xué)定義中，超圖是圖的一種派生形式，與普通圖不同的是，超圖中的一條超邊可以同時(shí)和任意個(gè)數(shù)的頂點(diǎn)相連接。超圖模型的特點(diǎn)是可以表達(dá)模式的復(fù)雜結(jié)構(gòu)和關(guān)系，在空間數(shù)據(jù)挖掘中，基于超圖模型的可視化可解決的問(wèn)題包括：表征復(fù)雜數(shù)據(jù)的內(nèi)在結(jié)構(gòu)和關(guān)系；展示對(duì)象的屬性和關(guān)系的發(fā)展變化趨勢(shì)；觀察模式的組成；在規(guī)模較大的數(shù)據(jù)集中進(jìn)行對(duì)象屬性值的查詢。超圖模型的優(yōu)點(diǎn)是用圖的邏輯結(jié)構(gòu)來(lái)有效地組織和傳遞數(shù)據(jù)集的結(jié)構(gòu)、關(guān)系和含義。

對(duì)于超圖的可視化，目前來(lái)說(shuō)主要有兩類：一類是沿用普通有向圖和無(wú)向圖的可視化方法，該方法使用多條邊前后連接，共同表示一條超邊；第二類是使用一個(gè)連續(xù)的區(qū)域，將超邊中的所有節(jié)點(diǎn)包圍在該區(qū)域中，從而表示一條超邊。

這兩類超邊表示方法，第一類對(duì)于超圖中超邊的表示并不直觀，當(dāng)超圖中的多條超邊存在交叉時(shí)，無(wú)法區(qū)分哪幾條線段連成了一條超邊；第二類方法對(duì)超邊的表現(xiàn)直觀性較好，但這種方法大部分需通過(guò)手工繪制獲得，經(jīng)查閱相關(guān)資料，還未發(fā)現(xiàn)有相關(guān)的計(jì)算機(jī)實(shí)現(xiàn)算法。

隨著對(duì)超圖應(yīng)用的增多，對(duì)超圖的可視化方法的探討，成為一個(gè)急需解決的問(wèn)題。

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

本發(fā)明提出的基于插值算法的區(qū)域包圍式超圖可視化方法，為解決超圖表示中傳統(tǒng)的超圖表示方法表達(dá)不直觀、不清晰的問(wèn)題，將超圖的傳統(tǒng)線式表達(dá)方式擴(kuò)展為區(qū)域式表達(dá)方式，提供了一種直觀、有效、快速的可視化方法。

本發(fā)明中涉及方法的原理是：將超圖中的每一條超邊所包含的節(jié)點(diǎn)，沿其超邊的垂線向兩側(cè)進(jìn)行擴(kuò)展，從而獲得擴(kuò)展點(diǎn)；然后使用Catmull-Rom算法將這些擴(kuò)展點(diǎn)使用一條連續(xù)平滑的曲線連接起來(lái)，獲得一個(gè)能包圍超邊節(jié)點(diǎn)的區(qū)域邊緣；接下來(lái)，通過(guò)對(duì)曲線進(jìn)行分段，并對(duì)不同的分段使用合適的方式進(jìn)行填充，最終獲得超邊包圍區(qū)域的填充效果；在超邊可視化過(guò)程中，根據(jù)色相環(huán)原理，將超圖中的不同超邊進(jìn)行差異性著色，從而增強(qiáng)超邊的區(qū)分性。

本發(fā)明的一種基于插值算法的區(qū)域包圍式超圖可視化方法，具體實(shí)現(xiàn)步驟如下：

步驟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：將超邊沿超邊的垂線方向往兩側(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)”。

對(duì)于涉及節(jié)點(diǎn)數(shù)為N的超邊，計(jì)算獲得的擴(kuò)展點(diǎn)數(shù)應(yīng)為2N。

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

a)首先將首點(diǎn)的兩個(gè)擴(kuò)展點(diǎn)，分別存入兩個(gè)“擴(kuò)展點(diǎn)鏈表”中；

b)然后判斷下一節(jié)點(diǎn)的兩個(gè)擴(kuò)展點(diǎn)與超邊的位置關(guān)系，并據(jù)此存入與該擴(kuò)展點(diǎn)位于超邊同側(cè)的鏈中；

c)循環(huán)執(zhí)行位置關(guān)系判斷，并加入到相應(yīng)的“擴(kuò)展點(diǎn)鏈表”中，直至最后一個(gè)節(jié)點(diǎn)。