[發明專利]一種基于HCT圖的層次數據對比可視分析方法

有效

• 申請號: 201810243279.4
• 申請日: 2018-03-23
• 公開（公告）號: CN108427765B
• 公開（公告）日: 2020-06-12
• 發明（設計）人: 陳誼;李玥;章蓉
• 申請（專利權）人: 北京工商大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/26
• 代理公司: 北京萬象新悅知識產權代理有限公司 11360
• 代理人: 黃鳳茹

1.一種基于可重疊圓形樹HCT圖的層次數據對比可視分析方法，將每組層次數據表示為一棵樹，針對兩棵樹構建集合樹，再將集合樹通過空間填充的方法進行可視化映射，得到可重疊圓形樹HCT圖，從而實現對兩組層次數據進行對比可視分析；包括如下步驟：

A.創建集合樹：

通過計算兩棵樹中同名節點的子節點集合的包含關系來構建集合樹；兩棵樹T₁、T₂從根結點開始依次對比每個同名節點的子節點集合，根據兩個子節點集合中元素的集合關系，生成兩個同名節點對應的集合樹節點，根據生成的所有集合樹節點的層次關系，自底向上遞歸實現集合樹的創建；

集合樹的每一個節點為由五個子集組成的一個元素集合，該節點集合中的元素是兩棵樹上對應節點的子節點；五個子集為：T₁_Only、T₂_Other、Both、T₂_Only、T₁_Other；其中，T₁、T₂為兩棵參與比較的樹；集合樹中A節點由樹T₁中A節點的子節點集合C_A1與樹T₂中A節點的子節點集合C_A2組成；子節點集合S₁為子節點只是T₁樹中A節點的子節點的集合，即C_A1-C_A2；子節點集合S₂為子節點只是T₂樹中A節點的子節點的集合，即C_A2-C_A1；子節點集合Both為子節點在既是T₁也是T₂樹中A節點子節點的集合，即C_A1∩C_A2；子節點集合S₁中，集合T₁_Only表示只存在于T₁樹中的子節點，T₂_Other表示其余子節點；子節點集合S₂中，集合T₂_Only表示只存在于T₂樹中的子節點，T₁_Other表示其余子節點；

B.設置HCT圖排布算法的起始默認參數；執行如下操作：

B1.定義HCT圖的圖元：

集合樹中每個節點集合包括子節點集合S₁、S₂、Both，對應的HCT圖中的每個圖元也包括分別對應S₁、S₂、Both的區域；HCT圖的圖元包括重疊圓形和圓形；重疊圓形是HCT圖中出現重疊的兩個子圓，將重疊的兩個子圓作為一個圖元，映射為集合樹上的一個節點；重疊圓形中，將重疊區域作為Both區域的形狀映射，重疊區域兩側的區域分別作為S₁、S₂區域的形狀映射；

B2.設置S₁、S₂、Both三個區域之間內部元素放大倍數R_S1、R_S2、R_Both，通過放大倍數控制三個區域內元素的大小；設置HCT圖的初始坐標，初始坐標為HCT圖在當前頁面上的位置；

C.將集合樹中每一個節點映射為HCT中一個圖元：根據每個節點的五個子節點集合的狀態，生成該節點在HCT圖中的形狀信息及其子節點排布信息；執行如下操作：

C1.根據集合樹節點的五個子集，首先將Both集合中的元素放置到一個圓形區域中，該圓形區域為即將生成的該節點的最終圖元的Both區域：

C2.創建外圍序列，外圍序列存放已排布的子元素中最外圍的一圈元素；

創建當前已放置元素的最小外接圓表示當前的Both區域，根據Both區域比例與數據節點值確認Both集合中每個子節點的半徑，并從大到小排序；

C3.通過外圍序列中的兩個相鄰元素確定新加入元素的位置；

新加入元素放置之前首先對外圍序列進行自檢，若在外圍序列中，兩個相鄰元素之間插入新元素后，新元素會與其他已放置元素相交，即存在凹陷位置，則將兩個相鄰元素與被影響的元素作為測試集合，對測試集合中元素進行兩兩組合，測試兩個元素之間加入新元素是否會影響其他已放置元素；如果沒有影響，則在序列中刪除測試集合剩余的元素；

C4.若放置的元素是Both集合中的第一個元素，則放置在Both區域的圓心位置，并生成初始外圍序列；

C5.在圓形區域放置其余元素；如果放置的當前元素為重疊圓形，則首先將該元素拆分為兩個子圓，在計算得到的最佳位置放置半徑較大的子圓，然后放置另一個子圓，并使得外接圓最小；

C6.在圓形區域放置其余元素；如果該元素為圓形，則遍歷外圍序列，依次計算外圍序列中兩個相鄰的元素與當前的最小外接圓之間可放置的圓的大小，得到可放置的圓最大的位置，作為當前最優的可放置位置，并放置該元素；

C7.根據C6新插入的元素所放置的位置，更新外圍序列，繪制新的外接圓；

C8.對每個元素執行步驟C2到步驟C6，直到全部放置完成；最后繪制最小外接圓，該外接圓為該節點的Both區域；由此Both集合元素放置完成；

C9.生成Both區域后，在兩側放置S₁、S₂集合中的元素，生成該節點的S₁、S₂區域：

C10.通過一條過Both區域圓心的直線，將外圍序列、Both區域中的元素分為上下兩個部分；

C11.將S1、S2集合中的元素從大到小排序，根據當前區域之間內部元素的放大倍數R_S1、R_S2、R_Both，計算得到所有元素的半徑；

C12.放置S₁子集中的一個元素，根據上部分的外圍序列與外接圓，計算得到最優的位置放置元素，并更新上部分的外圍序列與上部分的外接圓；

C13.放置S₂子集中的一個元素，根據下部分的外圍序列與外接圓，計算得到最優的位置放置元素，并更新下部分的外圍序列與下部分的外接圓；

C14.對于S1集合、S2集合中其余元素，按照步驟C12、步驟C13的順序依次放置，直到放完為止；

C15.輸出節點的形狀信息和該位置的子節點的排布信息；

D.從集合樹葉子節點出發，執行步驟C的操作，自底向上生成每個節點的形狀及其子節點布局，并根據集合樹中節點的層次關系排布所有節點，生成HCT圖，進一步實現區域縮放的交互設計；具體執行如下操作：

D1.自底向上逐層掃描集合樹上的節點，并對集合樹中所有節點執行步驟C，確定每個節點的圖元信息以及其子節點布局；

D2.通過步驟C生成的每個節點的位置一樣，根據集合樹上節點的父子關系，自上而下將每個節點的圖元信息與該節點在父節點的子節點布局中的對應位置進行匹配，即通過將節點進行旋轉、移動、縮放，使其與父節點中所排布的位置相同，得到該節點的旋轉系數、移動系數、自縮放系數；對該節點所有子節點根據旋轉系數、移動系數或自縮放系數進行相應旋轉、移動或縮放；若該子節點不是葉子節點，則對該子節點的所有子節點進行旋轉、移動、縮放；

D3.當集合樹中所有節點的子節點布局與對應的元素全部匹配，結束操作，得到HCT圖的布局信息；

D4.對HCT圖中元素進行交互設計與分析：通過控制區域默認比例放大或縮小元素，達到對兩棵樹之間共性部分或差異性部分突出展示的效果。