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

有效

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

一種地圖邊界數據的二階優化簡化方法，包括以下步驟：對原始數據進行篩選，清洗，刪除不重要的地圖邊界數據并對清洗后的數據進行區域簡化，即使用Visvalingam–Whyatt算法對各區域邊界進行簡化；再將簡化后的區域進行直角化，去噪聲；在完成上述步驟后，再對區域進行布局優化，即區域切割，確定目標函數，設定多種約束條件，Mosek求解二階優化方程組，最后進行區域拼接；通過以上步驟，生成新的地圖。本發明保證了各個區域的大致形狀和區域間的相對位置，提高了精確性。

技術領域

本發明涉及一種地圖邊界數據的二階優化簡化方法。

背景技術

在空間數據可視化應用領域中，大多數據展示信息都是通過其地理空間位置來收集的。傳統地圖的區域邊界復雜且形狀不規則，可視化信息堆積在地圖上展示，并不能快速的找到潛在信息并得到有效分析，因此，生成與傳統地圖相似的簡化地圖能夠大大的提高研究人員與普通民眾對空間數據分析和可視查看的速度與準確率。隨著信息化時代的發展，空間可視化對于地理數據的充分展示具有不可替代的作用，為了更方便的理解復雜的地理信息，提供方便和友好的地理數據可視化是至關重要的。

現階段，我國雖然在簡化地圖上取得了一定成效，但也造成了部分有價值信息的丟失或帶來了一些錯誤信息。大多數地圖簡化往往都是根據各區域的面積和規定各區域的形狀來簡化，這可能帶來區域形狀變化很大、各區域相對位置關系變動大的問題，而這也是地圖簡化中需要考慮的問題，因此，如何在保持區域的大致形狀不變及各區域的相對位置關系的基礎上對地圖進行簡化是一大難點。

空間數據可視化大多是在地圖上實現信息可視化和分析，而傳統的地圖由于其自身復雜的邊界和區域的不規則性并不能很好的將復雜的空間和屬性數據以具有空間定位的圖形圖像形式展示出來，同時現有算法生成的簡化地圖也不能完全保留實際地圖的結構信息。

發明內容

為了克服現有技術的不足，便于用戶分析和挖掘數據，獲取正確的可視化信息，對地圖邊界進行簡化并刪除不重要的信息，形成美觀、簡潔的地圖尤為重要；為了解決地圖中復雜的邊界，生成規則的平面地圖，方便用戶用來呈現其他信息，提供一種地圖邊界數據的二階優化簡化方法，分為三個步驟來進行：數據提取及簡化、直角化與去噪聲、布局優化。數據提取及簡化主要是對原始數據中離散邊界點的集合進行處理，去掉無價值的信息，同時通過Visvalingam–Whyatt算法減少離散邊界點的數量。在設計過程中，為了確保地圖數據經二階優化后生成的地圖具有美觀和簡潔性，本發明對簡化后的地圖進行直角化與去噪聲，即將新地圖的邊界轉換成直邊，每個角轉換成直角，并刪除區域中的突兀部分。經過上述步驟后，區域間會存在重疊和空隙，布局優化則是將上述問題轉換成二階優化求解最優布局，用Mosek數學求解工具對確定的二階優化方程進行求解，保證了各個區域的大致形狀和區域間的相對位置，提高了精確性。

為了解決上述技術問題本發明采用如下的技術方案：

一種地圖邊界數據的二階優化簡化方法，包括以下步驟：

(1)數據提取及簡化；地圖邊界數據是由許多離散邊界點的集合、區域郵編和區域名稱組成，為了能更加高效地分析數據,需要對數據進行預處理,去除無用的信息，如去掉同一區域周圍附帶的較小的島嶼；同時，針對復雜的區域邊界數據集，為了有效的減少各區域邊界上的點，采用了Visvalingam–Whyatt算法，在將設定的閾值Δs與每個點的有效面積S進行比較的基礎上保留重要的點，有效面積S為一條線上三個連續點之間的三角形組成的面積，且Δ_s越大，各區域的邊界越簡單，簡化程度越高；

(2)直角化與去噪聲；經數據處理后，區域邊界雖然得到了很大的簡化但依舊是一個復雜且不規則的邊界，為了方便后邊的布局優化，對各區域的邊界進行直角化處理并對直角化后的邊界進行去噪聲，根據每個點與后一個點的橫縱坐標差值的比值大小K來進行邊的直角化。對于連續的兩點(x_i，y_i)、(x_j，y_j)，直角化公式如下所示：