[發明專利]一種地圖邊界數據的二階優化簡化方法

有效

• 申請號: 201911097687.4
• 申請日: 2019-11-12
• 公開（公告）號: CN111222682B
• 公開（公告）日: 2022-05-03
• 發明（設計）人: 孫國道;李藏;王云超;寧辛雨;梁榮華
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06F17/11;G06F16/29
• 代理公司: 杭州斯可睿專利事務所有限公司 33241
• 代理人: 王利強

1.一種地圖邊界數據的二階優化簡化方法，其特征在于，所述方法包括以下步驟：

(1)數據提取及簡化：地圖邊界數據是由離散邊界點的集合、區域郵編和區域名稱組成，對數據進行預處理,去除無用的信息，采用Visvalingam–Whyatt算法，將設定的閾值與每個點的有效面積S進行比較，保留重要的點，有效面積S為一條線上三個連續點之間的三角形組成的面積；

(2)直角化與去噪聲：對各區域的邊界進行直角化處理，并對直角化后的邊界進行去噪聲，根據每個點與后一個點的橫縱坐標差值的比值大小K來進行邊界的直角化，對于連續的兩點(x_i，y_i)、(x_j，y_j)，直角化公式如下所示：

如果K≥1，點(x_j，y_j)向x做投影；如果K＜1，點(x_j，y_j)向y做投影；

經過直角化后的圖形，設置參數μ，用來表示各區域去噪聲的程度，將μ與每個區域中各邊長與此區域中對應的總邊長的比值進行比較，如果比值大于μ，則保留此邊長數據，否則刪除此邊長數據；

(3)布局優化：完成對區域邊界簡化后，將問題轉換為一個二階優化求解問題，通過確定目標函數，設定約束條件，得到二階優化方程組，運用Mosek數學求解工具對二階優化方程組求解最優解；

所述步驟(3)，具體包括如下步驟：

(3-1)圖形切割

使用Mosek數學求解工具求解二階優化方程組，將對每個區域的每一條邊進行約束，對各區域進行切割，即對各區域的點以x從小到大排序，相同的x點再以y從小到大排序，隨即進行分配，得到區域形狀都是矩形區域，以進行布局優化；

(3-2)二階優化方程組的形成

二階優化方程組的形成分為兩步，一步是目標函數的確定，另一步是約束條件的生成；對各個區域的大小進行控制，將原始矩形區域邊長與變化后矩形區域邊長差值平方的累加作為目標函數，目標函數如下所示：

其中，n代表數據集中的矩形個數，L_i1代表數據集中第i個矩形的橫向邊長長度，L_i2代表數據集中第i個矩形的縱向邊長長度，每個求解后的矩形分別用左下點(x_i0，y_i0)和右上點(x_i1，y_i1)兩個點顯示；

確定目標函數后，從單個區域和區域間的位置關系出發設定求解目標函數的約束條件，對于單個區域的約束，即對各區域的邊長加以約束，設定控制邊長變化幅度的參數α，將對應的優化求解的邊長控制在原始邊長1±α倍的范圍內，約束條件如下所示：

|x_i1-x_i0-L_i1|＜α×L_i1 (3)

|y_i1-y_i0-L_i2|＜α×L_i2 (4)

對于區域間位置關系的約束，將矩形區域的位置關系分為四種，第一種是一個矩形區域i的右邊僅有一個矩形區域j，并且矩形區域j的左邊也僅有一個矩形區域i，將這種位置關系定為D_ij；當一個矩形區域i的右邊存在兩個或兩個以上的矩形區域時，將矩形i與右上的矩形區域位置關系定為A，將矩形i與中間的矩形區域位置關系定為B，將矩形i與右下的矩形區域位置關系定為C，其約束條件如下所示：

x_i1＝x_j0 R_ij∈D_ij,A,B,C (5)

|y_i1-y_j1|＜α×L_i2 R_ij∈D_ij,A (6)

|y_i0-y_j0|＜α×L_i2 R_ij∈D_ij,C (7)

(3-3)圖形拼接

對優化后的結果進行拼接，使其保持每個區域原始的形狀，生成新的地圖。