[發明專利]一種基于力導引的異形區域拓撲布局算法

在審

• 申請號: 201810985452.8
• 申請日: 2018-08-28
• 公開（公告）號: CN109145462A
• 公開（公告）日: 2019-01-04
• 發明（設計）人: 姚興苗;焦海超;胡光岷
• 申請（專利權）人: 電子科技大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 成都虹盛匯泉專利代理有限公司 51268
• 代理人: 王偉

1.一種基于力導引的異形區域拓撲布局算法，其特征在于，包括以下步驟：

S1、基于標簽傳播的初始布局區域劃分；

S2、在已確定的異形區域內進行節點的初始位置布局；

S3、通過增加區域頂點對原始節點的吸引力從而將布局適應于異形區域的約束。

2.根據權利要求1所述的一種基于力導引的異形區域拓撲布局算法，其特征在于，所述步驟S1具體實現方法為：

S11、采用基于標簽傳播的社團劃分方法對輸入的大規模網絡拓撲數據進行社團劃分；

S12、對所有包含地理信息的節點進行初始化標簽設置，標簽序號從1開始；若多個節點的地理區域限制信息一致，則設置成相同的標簽號，否則標簽號遞增，完成后最大標簽號記作L_max；

S13、對剩余不包含地理信息的節點進行初始化標簽設置，標簽序號從(L_max+1)開始遞增，所有節點隨機獲取標簽，所有標簽不重復；當某個節點的相鄰節點編號小于或者等于L_max時，執行步驟S14，否則直接執行步驟S15；

S14、對相鄰節點具有地理信息的節點，尋找其具有地理信息的相鄰節點中標簽號出現次數最多的標簽，將出現次數最多的標簽號賦值給該不包含地理信息的節點；

S15、亂序排列所有節點，對每一個節點進行標簽更新；搜索與該節點直接相連接的節點標簽，記錄每個與之相連的標簽出現的次數，選擇出現次數最多的標簽作為該節點的新標簽；當多個標簽出現次數相同時，隨機選擇一個標簽作為該節點的新標簽；

S16、重復執行步驟S15，直到達到預設的迭代次數或者所有節點的標簽不再發生改變；

S17、針對劃分好的社團，計算社團中各節點地理信息的平均值，并選取該平均值的位置作為區域中心，確定區域中心相對地圖或其他映射關系的區域信息，若社團中無地理信息節點，則按照模塊度最大原則合并到其他社團進行區域劃分，然后根據社團中節點所包含的地理信息確定當前社團中所有節點的實際布局區域。

3.根據權利要求1所述的一種基于力導引的異形區域拓撲布局算法，其特征在于，所述步驟S2具體實現方法為：

S21、根據步驟S1得到的實際布局區域，由幾何方法求得區域中心P；

S22、求得質心P到多邊形區域輪廓各頂點的距離r_k，k為多邊形區域的頂點數；

S23、將r_k等分成n份，分割點從內向外分別記作r_k1、r_k2、…、r_k(n-1)，連接r_k上對應序號的分割點，在異形區域內部得到(n-1)個多邊形C₁、C₂、…、C_n-1，且其形狀與異形輪廓形狀一致；

S24、對所有節點隨機排序，P處放置第一個節點，然后對于剩余節點，分別均勻放置在C₁、C₂、…、C_n-1的輪廓上，按照各多邊形周長比例放置對應數量的節點。

4.根據權利要求1所述的一種基于力導引的異形區域拓撲布局算法，其特征在于，所述步驟S3包括以下子步驟：

S31、以多邊形區域的中心P作為公共頂點，多邊形輪廓相鄰兩頂點兩兩作為一組頂點，以三點構建三角形區域，將多邊形區域劃分成了不重合的n個三角形區域A₁、A₂、…、A_n，n為多邊形的頂點數；

S32、對每個內部節點，判斷其屬于某一個劃分區域A_i內部，1≤i≤n,i∈Z；

計算區域A_i中屬于多邊形區域頂點的兩個輪廓頂點Q₁、Q₂對該內部節點的斥力：

f_r(d)＝k²/d

其中，

計算區域A_i中屬于多邊形區域頂點的兩個輪廓頂點Q₁、Q₂對該內部節點的吸引力：

f_va(d)＝(d²/k)·α(x)

其中，

S33、計算區域A_i中屬于多邊形區域頂點的兩個輪廓頂點Q₁、Q₂對該內部節點的合力，將原始節點沿合力方向移動位移S；

S34、重復步驟S31～S33，直至節點布局符合美學要求。