著名的有才無(wú)德科學(xué)家曾說(shuō)過(guò)：“如果我看得比別人更遠(yuǎn)些琢锋，那是因?yàn)槲艺驹诰奕说募绨蛏显！蹦芡瓿蛇@個(gè)特效吴超，感謝我愛(ài)的人钉嘹，感謝月餅提供的部分C語(yǔ)言支持，感謝產(chǎn)品大濕的部分思路分析鲸阻。
起因：產(chǎn)品大濕說(shuō)跋涣，搞個(gè)地圖，搞個(gè)類似蘋(píng)果相冊(cè)“地點(diǎn)”相簿的地圖鸟悴，可以顯示10萬(wàn)+數(shù)據(jù)的陈辱。聽(tīng)到小道消息的我，立馬從抽屜里拿出了海鷗匕首刺向產(chǎn)品大濕的胸膛细诸，他現(xiàn)在正躺在醫(yī)院治療傷口沛贪，估計(jì)懸。
說(shuō)起實(shí)現(xiàn)過(guò)程也是一波三折，采用了5種方法利赋，完整耗時(shí)大概是3天水评，和上次新浪特效差不多。那么媚送，廢話不多說(shuō)中燥，開(kāi)始講過(guò)程。
方法1：
這個(gè)簡(jiǎn)單呀季希，以前做過(guò)天地圖廈門(mén)項(xiàng)目褪那，里面就寫(xiě)過(guò)聚合抽稀的算法，難不倒我式塌，分分鐘把代碼拷貝過(guò)來(lái)。嗯友浸，做法是：采用雙重循環(huán)峰尝，計(jì)算點(diǎn)和點(diǎn)的距離，如果小于某個(gè)距離收恢，就將兩個(gè)點(diǎn)聚合武学。有點(diǎn)智商的人都能寫(xiě)出來(lái)。然后測(cè)測(cè)10萬(wàn)條數(shù)據(jù)伦意，Oh my god火窒，瞬間爆炸，機(jī)子卡住不動(dòng)了驮肉，時(shí)間復(fù)雜度n^2熏矿，所以不動(dòng)很正常。而且還發(fā)現(xiàn)以前寫(xiě)的算法代碼還有可以優(yōu)化的空間离钝，哈哈票编，不過(guò)這工程已經(jīng)由別人接手了，不管它卵渴。
方案總結(jié)：
這種方案可以達(dá)到較好的聚合效果慧域，但是不同的地圖level需要定義不同的距離。最重要的是效率太低浪读。
結(jié)論：
此路不通昔榴，換一條路。研究失敗并不是件壞事碘橘，這些失敗的經(jīng)驗(yàn)互订，往往是為成功打下鋪墊。
方法2：
不行的話繼續(xù)干蛹屿，百度查找iOS地圖聚合抽稀屁奏，出來(lái)的基本都是TBAnnotationClustering，工程的文章思路解析在這里：《How To Efficiently Display Large Amounts of Data on iOS Maps》错负。這個(gè)工程是采用四叉樹(shù)的方式坟瓢，將地圖上的所有點(diǎn)全部劃分到四叉樹(shù)中勇边，通過(guò)四叉樹(shù)的方式，將查詢和比對(duì)數(shù)據(jù)的效率大大提升折联，可以說(shuō)工程的效率是很高的粒褒。其實(shí)如果要求沒(méi)那么高的話，使用這樣的代碼就可以達(dá)到要求了诚镰。大概講一下它的做法：根據(jù)需要聚合的點(diǎn)數(shù)據(jù)奕坟，將世界劃分成四叉樹(shù)，不斷地四分清笨，直至所有數(shù)據(jù)都掛在四叉樹(shù)上月杉，結(jié)束運(yùn)算；此時(shí)所有的點(diǎn)經(jīng)緯度都有一個(gè)范圍抠艾，如果要比對(duì)苛萎，只需要比對(duì)范圍就可以了。然后移動(dòng)地圖時(shí)检号，將當(dāng)前可見(jiàn)區(qū)域放入腌歉，根據(jù)一定的比值，將當(dāng)前區(qū)域劃分成橫豎n個(gè)格子齐苛。最后遍歷樹(shù)翘盖，將樹(shù)上符合格子范圍的點(diǎn)放入數(shù)組中，就可以得到聚合數(shù)據(jù)了凹蜂。
方案總結(jié)：
效率是極高的馍驯，效果也算可以。但圖標(biāo)會(huì)重疊炊甲，不好泥彤；平移時(shí)，圖標(biāo)會(huì)變動(dòng)卿啡，不好吟吝。而且有時(shí)候地圖level 1有1個(gè)點(diǎn)，level 2有2個(gè)點(diǎn)颈娜，level 3卻還是1個(gè)點(diǎn)剑逃，不符合正常邏輯。
結(jié)論：
此路不通官辽，換一條路蛹磺。朋友說(shuō)高德也有一個(gè)點(diǎn)聚合demo，我就去下載了看了看同仆，代碼邏輯抄襲TBAnnotationClustering萤捆，就沒(méi)什么可說(shuō)的了。
方法3：
一個(gè)字干干干，繼續(xù)俗或。有了前人四叉樹(shù)的基礎(chǔ)上市怎，我可以將剛才的世界范圍換成中國(guó)，樹(shù)頂點(diǎn)是中國(guó)范圍辛慰。接下來(lái)解決一下重疊問(wèn)題区匠，怎么消除重疊呢？我想了想帅腌，尼瑪驰弄，就把當(dāng)前的屏幕區(qū)域分成等額的幾份，不就OK了速客。然后橫豎循環(huán)每個(gè)等額區(qū)域戚篙，將樹(shù)上符合等額區(qū)域范圍的點(diǎn)放入數(shù)組中，就可以得到聚合數(shù)據(jù)了溺职。
方案總結(jié)：
重疊是不重疊了已球，效率也是極高的，放大縮小也沒(méi)問(wèn)題辅愿。但是每次平移地圖，因?yàn)橹匦掠?jì)算都會(huì)刷一下界面忆某。體驗(yàn)當(dāng)然不行点待。
結(jié)論：
此路不同，換一條路弃舒。萬(wàn)惡的百度癞埠，啊不，萬(wàn)能的百度求助完了之后聋呢，在某人的提醒下苗踪，求助我的好友：偉哥、陳大濕削锰、首長(zhǎng)通铲，問(wèn)他們之前有沒(méi)有搞過(guò)關(guān)于地圖聚合抽稀，偉哥說(shuō)沒(méi)搞過(guò)器贩，首長(zhǎng)也說(shuō)沒(méi)搞過(guò)颅夺，陳大濕比較熱情，向我問(wèn)了不少關(guān)聯(lián)問(wèn)題蛹稍，但也沒(méi)搞過(guò)吧黄。所以大部分還是得靠自己呀，不過(guò)感謝他們唆姐。
方法4：
怎么辦呢拗慨，經(jīng)過(guò)幾天晚上夢(mèng)周公的時(shí)間苦思冥想，終于想到了一種不錯(cuò)的方案。嗯嗯赵抢，大概說(shuō)一下做法：將中國(guó)劃分區(qū)域剧蹂，不同的地圖level劃分不同等量的格子，比如0-3級(jí)別劃分2X2格昌讲，4-7級(jí)別劃分4X4格国夜，8-11級(jí)別劃分16X16……以此類推，然后雙重循環(huán)短绸，將樹(shù)上符合等額區(qū)域范圍的點(diǎn)放入數(shù)組中车吹，就可以得到聚合數(shù)據(jù)了。但是醋闭，當(dāng)分到65536X65536的時(shí)候窄驹，就發(fā)現(xiàn)，速度已經(jīng)快不行了证逻。這種說(shuō)白了乐埠，時(shí)間復(fù)雜度還是n^2。
方案總結(jié)：
數(shù)據(jù)不重疊囚企，而且放大后數(shù)據(jù)散開(kāi)丈咐，平移圖標(biāo)不變，近乎完美龙宏。但是效率太低棵逊，而且聚合的間隙不能控制。
結(jié)論：
此路不同银酗，換一條路辆影。
方法5：
讓我好好想想，將數(shù)據(jù)點(diǎn)掛在四叉樹(shù)上這一步黍特，感覺(jué)沒(méi)什么問(wèn)題蛙讥，問(wèn)題在于怎么將數(shù)據(jù)點(diǎn)的聚合效果做的和蘋(píng)果一樣。經(jīng)過(guò)不斷的思考灭衷，終于想出了一種新的做法：我根據(jù)圖標(biāo)的大小取出當(dāng)前地圖level等量的矩形區(qū)域次慢，作為單個(gè)聚合點(diǎn)的范圍，防止重疊今布。然后取當(dāng)前屏幕上下左右5屏的距離作為總范圍傳入查詢樹(shù)中经备，開(kāi)始遍歷樹(shù)，用數(shù)組去裝聚合點(diǎn)部默，并判斷點(diǎn)包含情況侵蒙。最后遍歷該數(shù)組，完成傅蹂。
方案總結(jié)：
這個(gè)方案基本上與蘋(píng)果的樣式一樣了纷闺，還原度達(dá)到90%算凿。不過(guò)問(wèn)題還是有，因?yàn)槭侨?倍屏幕犁功，而是全中國(guó)氓轰，所以在小幾率情況下，還是會(huì)出現(xiàn)平移時(shí)浸卦，數(shù)據(jù)發(fā)生變化署鸡。然后就是取當(dāng)前地圖level等量的矩形區(qū)域，這個(gè)數(shù)據(jù)并不準(zhǔn)確限嫌，畢竟地圖上的每個(gè)點(diǎn)都不太一樣靴庆。效率方面沒(méi)有方法2和方法3的高，但可以滿足要求怒医。
結(jié)論：
方法可行炉抒，暫時(shí)采用此方式。
當(dāng)然方法5并不是最優(yōu)解稚叹，目前正在思考一種更加完美的方案焰薄，不僅效率高，而且能夠解決方法5中的問(wèn)題扒袖。如果后續(xù)研究出來(lái)塞茅，將會(huì)繼續(xù)提供方法6的思路，敬請(qǐng)期待季率。
有人問(wèn)我凡桥，為什么不按項(xiàng)目時(shí)間進(jìn)行，而總是即使加班也要提前完成蚀同。我覺(jué)得提前完成，可以讓我花更多的時(shí)間提高app的用戶體驗(yàn)啊掏，而且按照自己寫(xiě)好的測(cè)試用例來(lái)自測(cè)蠢络，讓app少點(diǎn)bug，多點(diǎn)美感迟蜜。以后別人想起我或者我做的app刹孔，可能會(huì)說(shuō)到：喔，他呀娜睛！做的app髓霞，bug很少，而且體驗(yàn)很不錯(cuò)畦戒，是一位不錯(cuò)的開(kāi)發(fā)人員方库。這樣我就很高興了。
著名的有才無(wú)德科學(xué)家曾說(shuō)過(guò)：“如果我看得比別人更遠(yuǎn)些障斋，那是因?yàn)槲艺驹诰奕说募绨蛏献萘省徐鹤！蹦芡瓿蛇@個(gè)特效，感謝我愛(ài)的人邀层，感謝月餅提供的部分C語(yǔ)言支持返敬，感謝產(chǎn)品大濕的部分思路分析。
起因：產(chǎn)品大濕說(shuō)寥院，搞個(gè)地圖劲赠，搞個(gè)類似蘋(píng)果相冊(cè)“地點(diǎn)”相簿的地圖，可以顯示10萬(wàn)+數(shù)據(jù)的秸谢。聽(tīng)到小道消息的我凛澎，立馬從抽屜里拿出了海鷗匕首刺向產(chǎn)品大濕的胸膛，他現(xiàn)在正躺在醫(yī)院治療傷口钮追，估計(jì)懸预厌。
說(shuō)起實(shí)現(xiàn)過(guò)程也是一波三折，采用了5種方法元媚，完整耗時(shí)大概是3天轧叽，和上次新浪特效差不多。那么刊棕，廢話不多說(shuō)炭晒，開(kāi)始講過(guò)程。
方法1：
這個(gè)簡(jiǎn)單呀甥角，以前做過(guò)天地圖廈門(mén)項(xiàng)目网严，里面就寫(xiě)過(guò)聚合抽稀的算法，難不倒我嗤无，分分鐘把代碼拷貝過(guò)來(lái)震束。嗯，做法是：采用雙重循環(huán)当犯，計(jì)算點(diǎn)和點(diǎn)的距離垢村，如果小于某個(gè)距離，就將兩個(gè)點(diǎn)聚合嚎卫。有點(diǎn)智商的人都能寫(xiě)出來(lái)嘉栓。然后測(cè)測(cè)10萬(wàn)條數(shù)據(jù)，Oh my god拓诸，瞬間爆炸侵佃，機(jī)子卡住不動(dòng)了，時(shí)間復(fù)雜度n^2奠支，所以不動(dòng)很正常馋辈。而且還發(fā)現(xiàn)以前寫(xiě)的算法代碼還有可以優(yōu)化的空間，哈哈倍谜，不過(guò)這工程已經(jīng)由別人接手了首有，不管它燕垃。
方案總結(jié)：
這種方案可以達(dá)到較好的聚合效果，但是不同的地圖level需要定義不同的距離井联。最重要的是效率太低卜壕。
結(jié)論：
此路不通，換一條路烙常。研究失敗并不是件壞事轴捎，這些失敗的經(jīng)驗(yàn)，往往是為成功打下鋪墊蚕脏。
方法2：
不行的話繼續(xù)干侦副，百度查找iOS地圖聚合抽稀，出來(lái)的基本都是TBAnnotationClustering驼鞭，工程的文章思路解析在這里：《How To Efficiently Display Large Amounts of Data on iOS Maps》秦驯。這個(gè)工程是采用四叉樹(shù)的方式，將地圖上的所有點(diǎn)全部劃分到四叉樹(shù)中挣棕，通過(guò)四叉樹(shù)的方式译隘，將查詢和比對(duì)數(shù)據(jù)的效率大大提升，可以說(shuō)工程的效率是很高的洛心。其實(shí)如果要求沒(méi)那么高的話固耘，使用這樣的代碼就可以達(dá)到要求了。大概講一下它的做法：根據(jù)需要聚合的點(diǎn)數(shù)據(jù)词身，將世界劃分成四叉樹(shù)厅目，不斷地四分，直至所有數(shù)據(jù)都掛在四叉樹(shù)上法严，結(jié)束運(yùn)算损敷；此時(shí)所有的點(diǎn)經(jīng)緯度都有一個(gè)范圍，如果要比對(duì)深啤，只需要比對(duì)范圍就可以了嗤锉。然后移動(dòng)地圖時(shí)，將當(dāng)前可見(jiàn)區(qū)域放入墓塌，根據(jù)一定的比值，將當(dāng)前區(qū)域劃分成橫豎n個(gè)格子奥额。最后遍歷樹(shù)苫幢，將樹(shù)上符合格子范圍的點(diǎn)放入數(shù)組中，就可以得到聚合數(shù)據(jù)了垫挨。
方案總結(jié)：
效率是極高的韩肝，效果也算可以。但圖標(biāo)會(huì)重疊九榔，不好哀峻；平移時(shí)涡相，圖標(biāo)會(huì)變動(dòng)，不好剩蟀。而且有時(shí)候地圖level 1有1個(gè)點(diǎn)催蝗，level 2有2個(gè)點(diǎn)，level 3卻還是1個(gè)點(diǎn)育特，不符合正常邏輯丙号。
結(jié)論：
此路不通，換一條路缰冤。朋友說(shuō)高德也有一個(gè)點(diǎn)聚合demo犬缨，我就去下載了看了看，代碼邏輯抄襲TBAnnotationClustering棉浸，就沒(méi)什么可說(shuō)的了怀薛。
方法3：
一個(gè)字干干干，繼續(xù)迷郑。有了前人四叉樹(shù)的基礎(chǔ)上枝恋，我可以將剛才的世界范圍換成中國(guó)，樹(shù)頂點(diǎn)是中國(guó)范圍三热。接下來(lái)解決一下重疊問(wèn)題鼓择，怎么消除重疊呢？我想了想就漾，尼瑪呐能，就把當(dāng)前的屏幕區(qū)域分成等額的幾份，不就OK了抑堡。然后橫豎循環(huán)每個(gè)等額區(qū)域摆出，將樹(shù)上符合等額區(qū)域范圍的點(diǎn)放入數(shù)組中，就可以得到聚合數(shù)據(jù)了首妖。
方案總結(jié)：
重疊是不重疊了偎漫，效率也是極高的，放大縮小也沒(méi)問(wèn)題有缆。但是每次平移地圖象踊，因?yàn)橹匦掠?jì)算都會(huì)刷一下界面。體驗(yàn)當(dāng)然不行棚壁。
結(jié)論：
此路不同杯矩，換一條路。萬(wàn)惡的百度袖外，啊不史隆，萬(wàn)能的百度求助完了之后，在某人的提醒下曼验，求助我的好友：偉哥泌射、陳大濕粘姜、首長(zhǎng)，問(wèn)他們之前有沒(méi)有搞過(guò)關(guān)于地圖聚合抽稀熔酷，偉哥說(shuō)沒(méi)搞過(guò)孤紧，首長(zhǎng)也說(shuō)沒(méi)搞過(guò)，陳大濕比較熱情纯陨，向我問(wèn)了不少關(guān)聯(lián)問(wèn)題坛芽，但也沒(méi)搞過(guò)。所以大部分還是得靠自己呀翼抠，不過(guò)感謝他們咙轩。
方法4：
怎么辦呢，經(jīng)過(guò)幾天晚上夢(mèng)周公的時(shí)間苦思冥想阴颖，終于想到了一種不錯(cuò)的方案活喊。嗯嗯，大概說(shuō)一下做法：將中國(guó)劃分區(qū)域量愧，不同的地圖level劃分不同等量的格子钾菊，比如0-3級(jí)別劃分2X2格，4-7級(jí)別劃分4X4格偎肃，8-11級(jí)別劃分16X16……以此類推煞烫，然后雙重循環(huán)，將樹(shù)上符合等額區(qū)域范圍的點(diǎn)放入數(shù)組中累颂，就可以得到聚合數(shù)據(jù)了滞详。但是，當(dāng)分到65536X65536的時(shí)候紊馏，就發(fā)現(xiàn)料饥，速度已經(jīng)快不行了。這種說(shuō)白了朱监，時(shí)間復(fù)雜度還是n^2岸啡。
方案總結(jié)：
數(shù)據(jù)不重疊，而且放大后數(shù)據(jù)散開(kāi)赫编，平移圖標(biāo)不變巡蘸，近乎完美。但是效率太低擂送，而且聚合的間隙不能控制悦荒。
結(jié)論：
此路不同，換一條路团甲。
方法5：
讓我好好想想，將數(shù)據(jù)點(diǎn)掛在四叉樹(shù)上這一步黍聂，感覺(jué)沒(méi)什么問(wèn)題躺苦，問(wèn)題在于怎么將數(shù)據(jù)點(diǎn)的聚合效果做的和蘋(píng)果一樣身腻。經(jīng)過(guò)不斷的思考，終于想出了一種新的做法：我根據(jù)圖標(biāo)的大小取出當(dāng)前地圖level等量的矩形區(qū)域匹厘，作為單個(gè)聚合點(diǎn)的范圍嘀趟，防止重疊。然后取當(dāng)前屏幕上下左右5屏的距離作為總范圍傳入查詢樹(shù)中愈诚，開(kāi)始遍歷樹(shù)她按，用數(shù)組去裝聚合點(diǎn)，并判斷點(diǎn)包含情況炕柔。最后遍歷該數(shù)組酌泰，完成。
方案總結(jié)：
這個(gè)方案基本上與蘋(píng)果的樣式一樣了匕累，還原度達(dá)到90%陵刹。不過(guò)問(wèn)題還是有，因?yàn)槭侨?倍屏幕欢嘿，而是全中國(guó)衰琐，所以在小幾率情況下，還是會(huì)出現(xiàn)平移時(shí)炼蹦，數(shù)據(jù)發(fā)生變化羡宙。然后就是取當(dāng)前地圖level等量的矩形區(qū)域，這個(gè)數(shù)據(jù)并不準(zhǔn)確掐隐，畢竟地圖上的每個(gè)點(diǎn)都不太一樣狗热。效率方面沒(méi)有方法2和方法3的高，但可以滿足要求瑟枫。
結(jié)論：
方法可行斗搞，暫時(shí)采用此方式。
當(dāng)然方法5并不是最優(yōu)解慷妙，目前正在思考一種更加完美的方案僻焚，不僅效率高，而且能夠解決方法5中的問(wèn)題膝擂。如果后續(xù)研究出來(lái)虑啤，將會(huì)繼續(xù)提供方法6的思路，敬請(qǐng)期待架馋。
有人問(wèn)我狞山，為什么不按項(xiàng)目時(shí)間進(jìn)行，而總是即使加班也要提前完成叉寂。我覺(jué)得提前完成萍启，可以讓我花更多的時(shí)間提高app的用戶體驗(yàn)，而且按照自己寫(xiě)好的測(cè)試用例來(lái)自測(cè)，讓app少點(diǎn)bug勘纯，多點(diǎn)美感局服。以后別人想起我或者我做的app，可能會(huì)說(shuō)到：喔驳遵，他呀淫奔！做的app，bug很少堤结，而且體驗(yàn)很不錯(cuò)唆迁，是一位不錯(cuò)的開(kāi)發(fā)人員。這樣我就很高興了竞穷。
