[發明專利]一種應用于地圖的聚點方法和裝置

有效

• 申請號: 201810212546.1
• 申請日: 2018-03-15
• 公開（公告）號: CN108509532B
• 公開（公告）日: 2020-09-29
• 發明（設計）人: 張亦萍;葉智慧;劉杰
• 申請（專利權）人: 浙江大華技術股份有限公司
• 主分類號: G06F16/29
• 分類號: G06F16/29;G06N3/00
• 代理公司: 北京同達信恒知識產權代理有限公司 11291
• 代理人: 黃志華

本發明公開了一種應用于地圖的聚點方法和裝置，所述方法包括：建立覆蓋地圖的蜂窩單元網格；計算所述蜂窩單元網格的每個蜂窩單元中點要素的個數和點要素的密集度，其中，所述點要素為所述地圖上的點要素；按照所述點要素的個數和所述點要素的密集度，對所述蜂窩單元網格的每個蜂窩單元進行排序，獲得排序后的蜂窩單元排序列表；基于所述蜂窩單元排序列表，聚合所述蜂窩單元網格的每個蜂窩單元，獲得一個或多個蜂窩單元聚簇，其中，每個蜂窩單元聚簇的坐標為其內部所有點要素的質心。這樣可以更精確地反映原始點位置，也規避了由于迭代順序對聚點結果的影響，支持點要素局部更新和聚合，并可充分利用分布式并行計算技術提升聚點方法的效果。

技術領域

本發明涉及地圖點要素處理領域，尤其涉及一種應用于地圖的聚點方法和裝置。

背景技術

目前已有的地圖點要素處理方法，基本上都是參考比例尺、注記等，例如以下兩種方式。

方式一，直接網格法

原理：將地圖范圍劃分成指定尺寸的正方形(每個縮放級別不同尺寸)，然后將落在對應格子中的點聚合到該正方形中(正方形的中心)，最終一個正方形內只顯示一個中心點，并且點上顯示該聚合點所包含的原始點的數量。如圖1A所示，是采用直接網格法進行聚合，聚合前和聚合后的結果圖。

方式二，直接距離法

原理：初始時沒有任何已知聚合點，然后對每個點進行迭代，計算一個點的外包正方形，若此點的外包正方形與現有的聚合點的外包正方形不相交，則新建聚合點(這里不是計算點與點間的距離，而是計算一個點的外包正方形，正方形的變長由用戶指定或程序設置一個默認值)，若相交，則把該點聚合到該聚合點中，若點與多個已知的聚合點的外包正方形相交，則計算該點到到聚合點的距離，聚合到距離最近的聚合點中，如此循環，直到所有點都遍歷完畢。每個縮放級別都重新遍歷所有原始點要素。如圖1B所示，是采用直接距離法進行聚合，聚合前和聚合后的結果圖。

直接網格法的優點是運算速度較快，每個原始點只需計算一次，沒有復雜的距離計算。而缺點也很明顯：有時明明很相近的點，卻僅僅因為網絡的分界線而被逼分開在不同的聚合點中，此外，聚合點的位置采用的是該網格的中心，而非該網格的質心，這樣聚合出來的點可能不能較精確反映原始點的信息。

直接距離法的優點是聚合點較精確的反映了所包含的原始點要素的位置信息，而缺點是速度不如完全基于網格的速度快等，此外各個點要素迭代順序不同會導致最終結果不同。如圖1C所示，是采用直接距離法進行迭代，各個點要素迭代順序不同會導致最終結果不同的示意圖。

可見，現有技術中至少存在如下技術問題：

在對地圖點要素進行處理時，聚合出來的點有時不能較精確反映原始點的信息，且聚合點時的迭代順序會影響最終的結果，在地圖點要素發生變化時，迭代效率較低。

發明內容

本發明實施例通過提供一種應用于地圖的聚點方法和裝置，用于解決現有技術中在對地圖點要素進行處理時，聚合出來的點有時不能較精確反映原始點的信息，且聚合點時的迭代順序會影響最終的結果，在地圖點要素發生變化時，迭代效率較低的技術問題。

第一方面，本發明一實施例提供了一種應用于地圖的聚點方法，包括：

建立覆蓋地圖的蜂窩單元網格；

計算所述蜂窩單元網格的每個蜂窩單元中點要素的個數和點要素的密集度，其中，所述點要素為所述地圖上的點要素；

按照所述點要素的個數和所述點要素的密集度，對所述蜂窩單元網格的每個蜂窩單元進行排序，獲得排序后的蜂窩單元排序列表；

基于所述蜂窩單元排序列表，聚合所述蜂窩單元網格的每個蜂窩單元，獲得一個或多個蜂窩單元聚簇，其中，所述一個或多個蜂窩單元聚簇中每個蜂窩單元聚簇的坐標為其內部所有點要素的質心，所述每個蜂窩單元聚簇包括至少一個蜂窩單元。