著名的有才無德科學(xué)家曾說過：“如果我看得比別人更遠(yuǎn)些，那是因?yàn)槲艺驹诰奕说募绨蛏稀！蹦芡瓿蛇@個(gè)特效，感謝我愛的人，感謝月餅提供的部分C語言支持，感謝產(chǎn)品大濕的部分思路分析。
起因：產(chǎn)品大濕說，搞個(gè)地圖，搞個(gè)類似蘋果相冊“地點(diǎn)”相簿的地圖，可以顯示10萬+數(shù)據(jù)的。聽到小道消息的我，立馬從抽屜里拿出了海鷗匕首刺向產(chǎn)品大濕的胸膛，他現(xiàn)在正躺在醫(yī)院治療傷口，估計(jì)懸。
說起實(shí)現(xiàn)過程也是一波三折，采用了5種方法，完整耗時(shí)大概是3天，和上次新浪特效差不多。那么，廢話不多說，開始講過程。
方法1：
這個(gè)簡單呀，以前做過天地圖廈門項(xiàng)目，里面就寫過聚合抽稀的算法，難不倒我，分分鐘把代碼拷貝過來。嗯，做法是：采用雙重循環(huán)，計(jì)算點(diǎn)和點(diǎn)的距離，如果小于某個(gè)距離，就將兩個(gè)點(diǎn)聚合。有點(diǎn)智商的人都能寫出來。然后測測10萬條數(shù)據(jù)，Oh my god，瞬間爆炸，機(jī)子卡住不動(dòng)了，時(shí)間復(fù)雜度n^2，所以不動(dòng)很正常。而且還發(fā)現(xiàn)以前寫的算法代碼還有可以優(yōu)化的空間，哈哈，不過這工程已經(jīng)由別人接手了，不管它。
方案總結(jié)：
這種方案可以達(dá)到較好的聚合效果，但是不同的地圖level需要定義不同的距離。最重要的是效率太低。
結(jié)論：
此路不通，換一條路。研究失敗并不是件壞事，這些失敗的經(jīng)驗(yàn)，往往是為成功打下鋪墊。
方法2：
不行的話繼續(xù)干，百度查找iOS地圖聚合抽稀，出來的基本都是TBAnnotationClustering，工程的文章思路解析在這里：《How To Efficiently Display Large Amounts of Data on iOS Maps》。這個(gè)工程是采用四叉樹的方式，將地圖上的所有點(diǎn)全部劃分到四叉樹中，通過四叉樹的方式，將查詢和比對數(shù)據(jù)的效率大大提升，可以說工程的效率是很高的。其實(shí)如果要求沒那么高的話，使用這樣的代碼就可以達(dá)到要求了。大概講一下它的做法：根據(jù)需要聚合的點(diǎn)數(shù)據(jù)，將世界劃分成四叉樹，不斷地四分，直至所有數(shù)據(jù)都掛在四叉樹上，結(jié)束運(yùn)算；此時(shí)所有的點(diǎn)經(jīng)緯度都有一個(gè)范圍，如果要比對，只需要比對范圍就可以了。然后移動(dòng)地圖時(shí)，將當(dāng)前可見區(qū)域放入，根據(jù)一定的比值，將當(dāng)前區(qū)域劃分成橫豎n個(gè)格子。最后遍歷樹，將樹上符合格子范圍的點(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é)論：
此路不通，換一條路。朋友說高德也有一個(gè)點(diǎn)聚合demo，我就去下載了看了看，代碼邏輯抄襲TBAnnotationClustering，就沒什么可說的了。
方法3：
一個(gè)字干干干，繼續(xù)。有了前人四叉樹的基礎(chǔ)上，我可以將剛才的世界范圍換成中國，樹頂點(diǎn)是中國范圍。接下來解決一下重疊問題，怎么消除重疊呢？我想了想，尼瑪，就把當(dāng)前的屏幕區(qū)域分成等額的幾份，不就OK了。然后橫豎循環(huán)每個(gè)等額區(qū)域，將樹上符合等額區(qū)域范圍的點(diǎn)放入數(shù)組中，就可以得到聚合數(shù)據(jù)了。
方案總結(jié)：
重疊是不重疊了，效率也是極高的，放大縮小也沒問題。但是每次平移地圖，因?yàn)橹匦掠?jì)算都會(huì)刷一下界面。體驗(yàn)當(dāng)然不行。
結(jié)論：
此路不同，換一條路。萬惡的百度，啊不，萬能的百度求助完了之后，在某人的提醒下，求助我的好友：偉哥、陳大濕、首長，問他們之前有沒有搞過關(guān)于地圖聚合抽稀，偉哥說沒搞過，首長也說沒搞過，陳大濕比較熱情，向我問了不少關(guān)聯(lián)問題，但也沒搞過。所以大部分還是得靠自己呀，不過感謝他們。
方法4：
怎么辦呢，經(jīng)過幾天晚上夢周公的時(shí)間苦思冥想，終于想到了一種不錯(cuò)的方案。嗯嗯，大概說一下做法：將中國劃分區(qū)域，不同的地圖level劃分不同等量的格子，比如0-3級別劃分2X2格，4-7級別劃分4X4格，8-11級別劃分16X16……以此類推，然后雙重循環(huán)，將樹上符合等額區(qū)域范圍的點(diǎn)放入數(shù)組中，就可以得到聚合數(shù)據(jù)了。但是，當(dāng)分到65536X65536的時(shí)候，就發(fā)現(xiàn)，速度已經(jīng)快不行了。這種說白了，時(shí)間復(fù)雜度還是n^2。
方案總結(jié)：
數(shù)據(jù)不重疊，而且放大后數(shù)據(jù)散開，平移圖標(biāo)不變，近乎完美。但是效率太低，而且聚合的間隙不能控制。
結(jié)論：
此路不同，換一條路。
方法5：
讓我好好想想，將數(shù)據(jù)點(diǎn)掛在四叉樹上這一步，感覺沒什么問題，問題在于怎么將數(shù)據(jù)點(diǎn)的聚合效果做的和蘋果一樣。經(jīng)過不斷的思考，終于想出了一種新的做法：我根據(jù)圖標(biāo)的大小取出當(dāng)前地圖level等量的矩形區(qū)域，作為單個(gè)聚合點(diǎn)的范圍，防止重疊。然后取當(dāng)前屏幕上下左右5屏的距離作為總范圍傳入查詢樹中，開始遍歷樹，用數(shù)組去裝聚合點(diǎn)，并判斷點(diǎn)包含情況。最后遍歷該數(shù)組，完成。
方案總結(jié)：
這個(gè)方案基本上與蘋果的樣式一樣了，還原度達(dá)到90%。不過問題還是有，因?yàn)槭侨?倍屏幕，而是全中國，所以在小幾率情況下，還是會(huì)出現(xiàn)平移時(shí)，數(shù)據(jù)發(fā)生變化。然后就是取當(dāng)前地圖level等量的矩形區(qū)域，這個(gè)數(shù)據(jù)并不準(zhǔn)確，畢竟地圖上的每個(gè)點(diǎn)都不太一樣。效率方面沒有方法2和方法3的高，但可以滿足要求。
結(jié)論：
方法可行，暫時(shí)采用此方式。
當(dāng)然方法5并不是最優(yōu)解，目前正在思考一種更加完美的方案，不僅效率高，而且能夠解決方法5中的問題。如果后續(xù)研究出來，將會(huì)繼續(xù)提供方法6的思路，敬請期待。
有人問我，為什么不按項(xiàng)目時(shí)間進(jìn)行，而總是即使加班也要提前完成。我覺得提前完成，可以讓我花更多的時(shí)間提高app的用戶體驗(yàn)，而且按照自己寫好的測試用例來自測，讓app少點(diǎn)bug，多點(diǎn)美感。以后別人想起我或者我做的app，可能會(huì)說到：喔，他呀！做的app，bug很少，而且體驗(yàn)很不錯(cuò)，是一位不錯(cuò)的開發(fā)人員。這樣我就很高興了。
著名的有才無德科學(xué)家曾說過：“如果我看得比別人更遠(yuǎn)些，那是因?yàn)槲艺驹诰奕说募绨蛏??！蹦芡瓿蛇@個(gè)特效，感謝我愛的人，感謝月餅提供的部分C語言支持，感謝產(chǎn)品大濕的部分思路分析。
起因：產(chǎn)品大濕說，搞個(gè)地圖，搞個(gè)類似蘋果相冊“地點(diǎn)”相簿的地圖，可以顯示10萬+數(shù)據(jù)的。聽到小道消息的我，立馬從抽屜里拿出了海鷗匕首刺向產(chǎn)品大濕的胸膛，他現(xiàn)在正躺在醫(yī)院治療傷口，估計(jì)懸。
說起實(shí)現(xiàn)過程也是一波三折，采用了5種方法，完整耗時(shí)大概是3天，和上次新浪特效差不多。那么，廢話不多說，開始講過程。
方法1：
這個(gè)簡單呀，以前做過天地圖廈門項(xiàng)目，里面就寫過聚合抽稀的算法，難不倒我，分分鐘把代碼拷貝過來。嗯，做法是：采用雙重循環(huán)，計(jì)算點(diǎn)和點(diǎn)的距離，如果小于某個(gè)距離，就將兩個(gè)點(diǎn)聚合。有點(diǎn)智商的人都能寫出來。然后測測10萬條數(shù)據(jù)，Oh my god，瞬間爆炸，機(jī)子卡住不動(dòng)了，時(shí)間復(fù)雜度n^2，所以不動(dòng)很正常。而且還發(fā)現(xiàn)以前寫的算法代碼還有可以優(yōu)化的空間，哈哈，不過這工程已經(jīng)由別人接手了，不管它。
方案總結(jié)：
這種方案可以達(dá)到較好的聚合效果，但是不同的地圖level需要定義不同的距離。最重要的是效率太低。
結(jié)論：
此路不通，換一條路。研究失敗并不是件壞事，這些失敗的經(jīng)驗(yàn)，往往是為成功打下鋪墊。
方法2：
不行的話繼續(xù)干，百度查找iOS地圖聚合抽稀，出來的基本都是TBAnnotationClustering，工程的文章思路解析在這里：《How To Efficiently Display Large Amounts of Data on iOS Maps》。這個(gè)工程是采用四叉樹的方式，將地圖上的所有點(diǎn)全部劃分到四叉樹中，通過四叉樹的方式，將查詢和比對數(shù)據(jù)的效率大大提升，可以說工程的效率是很高的。其實(shí)如果要求沒那么高的話，使用這樣的代碼就可以達(dá)到要求了。大概講一下它的做法：根據(jù)需要聚合的點(diǎn)數(shù)據(jù)，將世界劃分成四叉樹，不斷地四分，直至所有數(shù)據(jù)都掛在四叉樹上，結(jié)束運(yùn)算；此時(shí)所有的點(diǎn)經(jīng)緯度都有一個(gè)范圍，如果要比對，只需要比對范圍就可以了。然后移動(dòng)地圖時(shí)，將當(dāng)前可見區(qū)域放入，根據(jù)一定的比值，將當(dāng)前區(qū)域劃分成橫豎n個(gè)格子。最后遍歷樹，將樹上符合格子范圍的點(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é)論：
此路不通，換一條路。朋友說高德也有一個(gè)點(diǎn)聚合demo，我就去下載了看了看，代碼邏輯抄襲TBAnnotationClustering，就沒什么可說的了。
方法3：
一個(gè)字干干干，繼續(xù)。有了前人四叉樹的基礎(chǔ)上，我可以將剛才的世界范圍換成中國，樹頂點(diǎn)是中國范圍。接下來解決一下重疊問題，怎么消除重疊呢？我想了想，尼瑪，就把當(dāng)前的屏幕區(qū)域分成等額的幾份，不就OK了。然后橫豎循環(huán)每個(gè)等額區(qū)域，將樹上符合等額區(qū)域范圍的點(diǎn)放入數(shù)組中，就可以得到聚合數(shù)據(jù)了。
方案總結(jié)：
重疊是不重疊了，效率也是極高的，放大縮小也沒問題。但是每次平移地圖，因?yàn)橹匦掠?jì)算都會(huì)刷一下界面。體驗(yàn)當(dāng)然不行。
結(jié)論：
此路不同，換一條路。萬惡的百度，啊不，萬能的百度求助完了之后，在某人的提醒下，求助我的好友：偉哥、陳大濕、首長，問他們之前有沒有搞過關(guān)于地圖聚合抽稀，偉哥說沒搞過，首長也說沒搞過，陳大濕比較熱情，向我問了不少關(guān)聯(lián)問題，但也沒搞過。所以大部分還是得靠自己呀，不過感謝他們。
方法4：
怎么辦呢，經(jīng)過幾天晚上夢周公的時(shí)間苦思冥想，終于想到了一種不錯(cuò)的方案。嗯嗯，大概說一下做法：將中國劃分區(qū)域，不同的地圖level劃分不同等量的格子，比如0-3級別劃分2X2格，4-7級別劃分4X4格，8-11級別劃分16X16……以此類推，然后雙重循環(huán)，將樹上符合等額區(qū)域范圍的點(diǎn)放入數(shù)組中，就可以得到聚合數(shù)據(jù)了。但是，當(dāng)分到65536X65536的時(shí)候，就發(fā)現(xiàn)，速度已經(jīng)快不行了。這種說白了，時(shí)間復(fù)雜度還是n^2。
方案總結(jié)：
數(shù)據(jù)不重疊，而且放大后數(shù)據(jù)散開，平移圖標(biāo)不變，近乎完美。但是效率太低，而且聚合的間隙不能控制。
結(jié)論：
此路不同，換一條路。
方法5：
讓我好好想想，將數(shù)據(jù)點(diǎn)掛在四叉樹上這一步，感覺沒什么問題，問題在于怎么將數(shù)據(jù)點(diǎn)的聚合效果做的和蘋果一樣。經(jīng)過不斷的思考，終于想出了一種新的做法：我根據(jù)圖標(biāo)的大小取出當(dāng)前地圖level等量的矩形區(qū)域，作為單個(gè)聚合點(diǎn)的范圍，防止重疊。然后取當(dāng)前屏幕上下左右5屏的距離作為總范圍傳入查詢樹中，開始遍歷樹，用數(shù)組去裝聚合點(diǎn)，并判斷點(diǎn)包含情況。最后遍歷該數(shù)組，完成。
方案總結(jié)：
這個(gè)方案基本上與蘋果的樣式一樣了，還原度達(dá)到90%。不過問題還是有，因?yàn)槭侨?倍屏幕，而是全中國，所以在小幾率情況下，還是會(huì)出現(xiàn)平移時(shí)，數(shù)據(jù)發(fā)生變化。然后就是取當(dāng)前地圖level等量的矩形區(qū)域，這個(gè)數(shù)據(jù)并不準(zhǔn)確，畢竟地圖上的每個(gè)點(diǎn)都不太一樣。效率方面沒有方法2和方法3的高，但可以滿足要求。
結(jié)論：
方法可行，暫時(shí)采用此方式。
當(dāng)然方法5并不是最優(yōu)解，目前正在思考一種更加完美的方案，不僅效率高，而且能夠解決方法5中的問題。如果后續(xù)研究出來，將會(huì)繼續(xù)提供方法6的思路，敬請期待。
有人問我，為什么不按項(xiàng)目時(shí)間進(jìn)行，而總是即使加班也要提前完成。我覺得提前完成，可以讓我花更多的時(shí)間提高app的用戶體驗(yàn)，而且按照自己寫好的測試用例來自測，讓app少點(diǎn)bug，多點(diǎn)美感。以后別人想起我或者我做的app，可能會(huì)說到：喔，他呀！做的app，bug很少，而且體驗(yàn)很不錯(cuò)，是一位不錯(cuò)的開發(fā)人員。這樣我就很高興了。
