[發(fā)明專利]針對層次數(shù)據(jù)的正方化有序樹圖布局方法

有效

• 申請?zhí)枺?/td>: 201410523310.1
• 申請日: 2014-10-07
• 公開（公告）號: CN104281681B
• 公開（公告）日: 2017-11-17
• 發(fā)明（設(shè)計）人: 陳誼;胡海云;甄遠剛;劉瑞軍
• 申請（專利權(quán)）人: 北京工商大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京理工大學(xué)專利中心11120
• 代理人: 張利萍

1.一種針對層次數(shù)據(jù)的正方化有序樹圖布局方法，對待顯示的數(shù)據(jù)集DS進行可視化處理，所述待顯示的數(shù)據(jù)集DS是一組通過層次結(jié)構(gòu)關(guān)系互相關(guān)聯(lián)的數(shù)據(jù)，即層次數(shù)據(jù)；其特征在于：其具體操作步驟如下：

A.將待可視化數(shù)據(jù)集DS中的數(shù)據(jù)，按照層次關(guān)系表示為一棵樹T；

B.從上向下依次對樹T中的每一層節(jié)點進行處理，同一層次的同父節(jié)點經(jīng)過處理后得到一個大權(quán)值節(jié)點集，因此樹T中的每一層節(jié)點進行處理后得到1個以上大權(quán)值節(jié)點集；

C.在二維平面上設(shè)置一個長寬比為6:4的矩形R，其面積用符號S表示；

D.針對步驟B得到的每一個大權(quán)值節(jié)點集，根據(jù)最短邊路徑原則，依次布局大權(quán)值節(jié)點集中的大權(quán)值節(jié)點；

所述最短邊路徑原則具體為：保持連續(xù)性的情況下，采用最短邊路徑進行布局；所述最短邊路徑是對帶狀路徑和螺旋狀路徑進行優(yōu)化，每個節(jié)點布局時都毗鄰上一個節(jié)點，并且布局方向緊靠剩余布局空間的最短邊；所述帶狀路徑是從左向右、從上到下依次布局；所述螺旋狀路徑是沿螺旋外環(huán)向內(nèi)環(huán)依次布局；

E.對于包含的節(jié)點個數(shù)大于2個的大權(quán)值節(jié)點，稱其為虛擬父節(jié)點；將其包含的全部節(jié)點看做為同父節(jié)點；依次對每一個包含的節(jié)點個數(shù)大于2個的大權(quán)值節(jié)點進行處理，得到一個大權(quán)值節(jié)點集；然后執(zhí)行步驟D的布局過程，直至所有布局節(jié)點皆為非組合節(jié)點；

經(jīng)過上述步驟的操作，即可完成對待顯示的數(shù)據(jù)集DS的正方化有序樹圖布局；

步驟B中所述對樹T中的同一層次的節(jié)點進行處理后得到大權(quán)值節(jié)點集的具體操作步驟為：

B1.將當(dāng)前節(jié)點的所有兄弟節(jié)點，記作節(jié)點集U；節(jié)點集U中的節(jié)點數(shù)量用符號M_u表示；設(shè)置變量p、M_p、k和m，并給變量p賦初始值為0；給變量k賦初始值為1；給變量m賦初始值為2；

B2.對于當(dāng)前節(jié)點集U中所有未經(jīng)過處理的節(jié)點，查找其最大值節(jié)點，最大值節(jié)點的序號用符號max表示，其值用符號U[max]表示；給變量M_p賦值為U[max]，并使變量p自增1；

B3.判斷1≤k＜m＜max≤M_u是否成立，如成立，則通過公式(1)計算第k個至第m個節(jié)點的節(jié)點值之和TempSum_k～m，然后執(zhí)行步驟B4的操作；否則，將TempSum_k～(m-1)作為一個新節(jié)點放入大權(quán)值節(jié)點集合U'中，并對當(dāng)前節(jié)點集U中的第k個至第m-1個節(jié)點標(biāo)記為已處理節(jié)點，然后給變量k賦值為m+1，給m賦值為k+1，執(zhí)行步驟B5的操作；

TempSumk~m=Σi=kmU[i]---(1)]]>

B4.判斷|TempSum_k～m-M_p|＜|TempSum_k～(m-1)-M_p|是否成立，如成立，則使變量m值自增1，然后重復(fù)B3至步驟B4的操作；否則，將TempSum_k～(m-1)作為一個新節(jié)點放入大權(quán)值節(jié)點集合U'中，并對當(dāng)前節(jié)點集U中的第k個至第m-1個節(jié)點標(biāo)記為已處理節(jié)點，然后給變量k賦值為m，給m賦值為k+1，然后重復(fù)B3至步驟B4的操作；

B5.將U[max]作為一個節(jié)點，添加至大權(quán)值節(jié)點集合U'中,并對當(dāng)前節(jié)點集U中的第max個節(jié)點標(biāo)記為已處理節(jié)點；然后，重復(fù)步驟B2至B5的操作，直至將原節(jié)點集U中所有節(jié)點通過合并組合添加至大權(quán)值節(jié)點集合U'；

經(jīng)過步驟B1至B5的操作，得到的大權(quán)值節(jié)點集合U'中的節(jié)點稱為大權(quán)值節(jié)點；

步驟D中所述針對每一個大權(quán)值節(jié)點集，根據(jù)優(yōu)化后的最短路徑，依次布局大權(quán)值節(jié)點集中的大權(quán)值節(jié)點的具體操作步驟為：

D1.對于由樹T的第二個層次的節(jié)點得到的大權(quán)值節(jié)點集，在步驟C設(shè)置的6:4的矩形R上布局節(jié)點；對于其它大權(quán)值節(jié)點集，在其父節(jié)點或虛擬父節(jié)點對應(yīng)的矩形中布局節(jié)點；

D2.依次對大權(quán)值節(jié)點集合U'中的每一個節(jié)點進行處理，得到當(dāng)前節(jié)點在矩形R或中對應(yīng)矩形r的相鄰兩條邊的長度和所處位置；

用符號s表示當(dāng)前節(jié)點的序號，用符號U'[s]表示當(dāng)前節(jié)點s的節(jié)點值，用符號SUM_U'表示大權(quán)值節(jié)點集合U'中所有節(jié)點值的和，用符號M_U'表示大權(quán)值節(jié)點集合U'中的節(jié)點數(shù)量，1≤s≤M_U'；矩形r相鄰兩條邊的長度，分別用符號a和b表示；前一節(jié)點s-1在矩形R或中對應(yīng)矩形r'的相鄰兩條邊的長度，分別用符號a'和b'表示；

對當(dāng)前節(jié)點進行處理時，分成兩種情況處理：

情況1：當(dāng)s的值為1或者a'＜b'時，執(zhí)行步驟D2.a至D2.c的操作；

D2.a：對當(dāng)前節(jié)點s處理，為其在矩形R或的當(dāng)前剩余部分中分配一個矩形r；矩形R或的當(dāng)前剩余部分仍為矩形，稱為剩余矩形R'，用符號l表示剩余矩形R'的短邊的長度，則：當(dāng)前節(jié)點s在矩形R或中的對應(yīng)矩形r的相鄰兩條邊中的一條邊長a＝l，另一條邊長b可根據(jù)公式(2)計算得到；

b=Sa×U′[s]SUMU′---(2)]]>

D2.b：確定當(dāng)前節(jié)點s對應(yīng)的矩形r在矩形R或中的所處位置：矩形r位于剩余矩形R'中，與前一節(jié)點s-1對應(yīng)的矩形相鄰，并且矩形r的一條長度為a的邊與剩余矩形R'的短邊重合，矩形r的一條長度為b的邊與剩余矩形R'的長邊的一部分重合，從而確定當(dāng)前節(jié)點s對應(yīng)的矩形r在矩形R或中的所處位置；

D2.c：如當(dāng)前節(jié)點s不是最后一個節(jié)點，則：令a'＝a；b'＝b；然后重復(fù)步驟D2，處理下一節(jié)點；否則，結(jié)束操作；

情況2：當(dāng)s的值不為1并且a'≥b'時，則布局當(dāng)前節(jié)點時，需調(diào)整前一節(jié)點s-1在矩形R或中對應(yīng)的矩形r'的相鄰兩條邊的長度以及位置，因此，此時的當(dāng)前剩余矩形R'中包含前一節(jié)點s-1在矩形R或中對應(yīng)的矩形；具體執(zhí)行步驟D2.1至D2.4的操作；

D2.1：當(dāng)前節(jié)點s在矩形R或中的對應(yīng)矩形r的相鄰兩條邊中一條邊長a可根據(jù)公式(3)計算得到，另一條邊長b可根據(jù)公式(4)計算得到；

a=l×U′[s]U′[s]+U′[s-1]---(3)]]>

b=Sl×U′[s]+U′[s-1]SUMU′---(4)]]>

D2.2：前一節(jié)點s-1在矩形R或中對應(yīng)的矩形r'的相鄰兩條邊中一條邊長a′＝l-a，另一條邊長b′＝b；

D2.3：確定前一節(jié)點s-1對應(yīng)的矩形r'在矩形R或中的所處位置：矩形r'位于剩余矩形R'中，與節(jié)點s-2對應(yīng)的矩形相鄰，并且矩形r'的一條長度為a'的邊與剩余矩形R'的短邊的一部分重合，矩形r'的一條長度為b'的邊與剩余矩形R'的長邊的一部分重合，從而確定前一節(jié)點s-1對應(yīng)的矩形r'在矩形R或中的所處位置；

D2.4：確定當(dāng)前節(jié)點s對應(yīng)的矩形r在矩形R或中的所處位置：矩形r位于剩余矩形R'中，與前一節(jié)點s-1對應(yīng)的矩形相鄰，并且矩形r的一條長度為b的邊與剩余矩形R'的長度為b'的邊重合，矩形r與矩形r'相互不重疊，從而確定當(dāng)前節(jié)點s對應(yīng)的矩形r在矩形R或中的所處位置；

D2.5：如當(dāng)前節(jié)點s不是最后一個節(jié)點，則：令a'＝a；b'＝b；然后重復(fù)步驟D2，處理下一節(jié)點；否則，結(jié)束操作。