[發明專利]基于連通圖和凸包的散點圖去重疊算法

有效

• 申請號: 202110315709.0
• 申請日: 2021-03-24
• 公開（公告）號: CN113052893B
• 公開（公告）日: 2022-05-06
• 發明（設計）人: 廖志芳;孫金生;趙穎;郁松;龍軍
• 申請（專利權）人: 中南大學
• 主分類號: G06T7/62
• 分類號: G06T7/62;G06T7/64
• 代理公司: 長沙軒榮專利代理有限公司 43235
• 代理人: 李喆

1.一種基于連通圖和凸包的散點圖去重疊算法，其特征在于，包括：

步驟1，選取一個以圖片為標記點的圖片散點圖，且圖片散點圖中的所有圖片的四個邊長都相等，獲取圖片散點圖中每張圖片的坐標和寬高；

步驟2，通過碰撞檢測算法計算圖片散點圖中各個圖片之間的鄰接矩陣；

步驟3，根據計算出的各個圖片之間的鄰接矩陣和基于寬度優先搜索的暴力搜索方法計算圖片散點圖中所有圖片的連通圖；

步驟4，對計算出的每個連通圖計算凸包；

步驟5，采用基于網格布局的搜索算法分別將計算出的每個凸包所包圍的面積劃分為多個寬高相同的小正方形；

步驟6，將每個凸包中的圖片按照圖片到相對應的凸包中心的距離升序排列，將每個凸包中劃分出小正方形按照小正方形到相對應的凸包中心的距離升序排列，獲取每個凸包中的小正方形的坐標和寬高，將每個凸包中的小正方形的坐標和寬高分配到相對應的凸包中的圖片，得到每個凸包中的每張圖片新坐標和新寬高。

2.根據權利要求1所述的基于連通圖和凸包的散點圖去重疊算法，其特征在于，所述步驟1具體包括：

設定圖片散點圖的一個頂點為坐標原點、以坐標原點為起點的水平方向為X軸正方向和以坐標原點為起點的豎直方向為Y軸正方向，獲得圖片散點圖中所有圖片的坐標和寬高。

3.根據權利要求2所述的基于連通圖和凸包的散點圖去重疊算法，其特征在于，所述步驟2具體包括：

將圖片散點圖中的每張圖片看作為一個節點，將圖片散點圖中在視覺上發生重疊的圖片看作為發生了碰撞且將在視覺上發生重疊的圖片看作為相連的兩個節點，通過碰撞檢測算法將圖片散點圖中各個圖片之間的連接關系轉換為鄰接矩陣，得到N*N大小的鄰接矩陣，其中，當圖片i和圖片j之間的鄰接矩陣adjacent[i]j]＝＝1時，表示圖片i和圖片j發生重疊，當圖片i和圖片j之間的鄰接矩陣adjacent[i]j]＝＝0時，表示圖片i和圖片j不發生重疊。

4.根據權利要求3所述的基于連通圖和凸包的散點圖去重疊算法，其特征在于，所述步驟3具體包括：

步驟31，設置一個動態數組flags和一個動態數組islands，初始狀態下動態數組flags存儲了圖片散點圖中所有圖片的ID，動態數組islands為空；

步驟32，從動態數組flags中取出一個圖片的ID，以當前圖片的ID為起點結合當前圖片的鄰接矩陣使用寬度優先搜索算法在圖片散點圖中尋找出所有與當前圖片連通的圖片的ID，當有尋找到與當前圖片連通的圖片時，將所有尋找出的圖片的ID和當前圖片的ID存入新建數組island中，將新建數組island存入動態數組islands中，當未尋找到與當前圖片連通的圖片時，將當前圖片的ID存入新建數組flag中；

步驟33，將存入新建數組island中的圖片的ID或存入新建數組flag中的圖片的ID從動態數組flags中刪除；

步驟34，當動態數組flags為空時，結束算法；當動態數組flags不為空時，跳轉到步驟32繼續執行，直到動態數組flags為空時，結束算法；

得到存儲了圖片ID的動態數組islands和新建數組flag，將動態數組islands中的各個新建數組island表示為各個連通圖，將各個新建數組island中的圖片ID表示為相對應的連通圖中的圖片，將新建數組flag中的圖片ID表示為圖片散點圖中未被分配到連通圖中的圖片。

5.根據權利要求4所述的基于連通圖和凸包的散點圖去重疊算法，其特征在于，所述步驟4具體包括：

步驟41，判斷每個連通圖中的圖片數量是否大于1，當當前連通圖中的圖片數量不大于1時，對下一個連通圖中的圖片數量進行判斷，當當前連通圖中的圖片數量大于1時，根據當前連通圖中圖片的ID、圖片坐標和圖片寬高計算出當前連通圖中圖片的所有角的坐標，若當前連通圖中有M張圖片，則當前連通圖中圖片的所有角的坐標的計算結果為[M*4,2]的二維矩陣，根據計算出的[M*4,2]二維矩陣計算凸包，凸包計算結果為P*2二維矩陣，其中，P是凸包中的頂點的個數。