iOS苹果相册“地点”相簿效果实现浅谈
著名的有才无德科学家曾说过：“如果我看得比别人更远些，那是因为我站在巨人的肩膀上。”能完成这个特效，感谢我爱的人，感谢月饼提供的部分C语言支持，感谢产品大湿的部分思路分析。
起因：产品大湿说，搞个地图，搞个类似苹果相册“地点”相簿的地图，可以显示10万+数据的。听到小道消息的我，立马从抽屉里拿出了海鸥匕首刺向产品大湿的胸膛，他现在正躺在医院治疗伤口，估计悬。
说起实现过程也是一波三折，采用了5种方法，完整耗时大概是3天，和上次新浪特效差不多。那么，废话不多说，开始讲过程。
方法1：
这个简单呀，以前做过天地图厦门项目，里面就写过聚合抽稀的算法，难不倒我，分分钟把代码拷贝过来。嗯，做法是：采用双重循环，计算点和点的距离，如果小于某个距离，就将两个点聚合。有点智商的人都能写出来。然后测测10万条数据，Oh my god，瞬间爆炸，机子卡住不动了，时间复杂度n^2，所以不动很正常。而且还发现以前写的算法代码还有可以优化的空间，哈哈，不过这工程已经由别人接手了，不管它。
方案总结：
这种方案可以达到较好的聚合效果，但是不同的地图level需要定义不同的距离。最重要的是效率太低。
结论：
此路不通，换一条路。研究失败并不是件坏事，这些失败的经验，往往是为成功打下铺垫。
方法2：
不行的话继续干，百度查找iOS地图聚合抽稀，出来的基本都是TBAnnotationClustering，工程的文章思路解析在这里：《How To Efficiently Display Large Amounts of Data on iOS Maps》。这个工程是采用四叉树的方式，将地图上的所有点全部划分到四叉树中，通过四叉树的方式，将查询和比对数据的效率大大提升，可以说工程的效率是很高的。其实如果要求没那么高的话，使用这样的代码就可以达到要求了。大概讲一下它的做法：根据需要聚合的点数据，将世界划分成四叉树，不断地四分，直至所有数据都挂在四叉树上，结束运算；此时所有的点经纬度都有一个范围，如果要比对，只需要比对范围就可以了。然后移动地图时，将当前可见区域放入，根据一定的比值，将当前区域划分成横竖n个格子。最后遍历树，将树上符合格子范围的点放入数组中，就可以得到聚合数据了。
方案总结：
效率是极高的，效果也算可以。但图标会重叠，不好；平移时，图标会变动，不好。而且有时候地图level 1有1个点，level 2有2个点，level 3却还是1个点，不符合正常逻辑。
结论：
此路不通，换一条路。朋友说高德也有一个点聚合demo，我就去下载了看了看，代码逻辑抄袭TBAnnotationClustering，就没什么可说的了。
方法3：
一个字干干干，继续。有了前人四叉树的基础上，我可以将刚才的世界范围换成中国，树顶点是中国范围。接下来解决一下重叠问题，怎么消除重叠呢？我想了想，尼玛，就把当前的屏幕区域分成等额的几份，不就OK了。然后横竖循环每个等额区域，将树上符合等额区域范围的点放入数组中，就可以得到聚合数据了。
方案总结：
重叠是不重叠了，效率也是极高的，放大缩小也没问题。但是每次平移地图，因为重新计算都会刷一下界面。体验当然不行。
结论：
此路不同，换一条路。万恶的百度，啊不，万能的百度求助完了之后，在某人的提醒下，求助我的好友：伟哥、陈大湿、首长，问他们之前有没有搞过关于地图聚合抽稀，伟哥说没搞过，首长也说没搞过，陈大湿比较热情，向我问了不少关联问题，但也没搞过。所以大部分还是得靠自己呀，不过感谢他们。
方法4：
怎么办呢，经过几天晚上梦周公的时间苦思冥想，终于想到了一种不错的方案。嗯嗯，大概说一下做法：将中国划分区域，不同的地图level划分不同等量的格子，比如0-3级别划分2X2格，4-7级别划分4X4格，8-11级别划分16X16……以此类推，然后双重循环，将树上符合等额区域范围的点放入数组中，就可以得到聚合数据了。但是，当分到65536X65536的时候，就发现，速度已经快不行了。这种说白了，时间复杂度还是n^2。
方案总结：
数据不重叠，而且放大后数据散开，平移图标不变，近乎完美。但是效率太低，而且聚合的间隙不能控制。
结论：
此路不同，换一条路。
方法5：
让我好好想想，将数据点挂在四叉树上这一步，感觉没什么问题，问题在于怎么将数据点的聚合效果做的和苹果一样。经过不断的思考，终于想出了一种新的做法：我根据图标的大小取出当前地图level等量的矩形区域，作为单个聚合点的范围，防止重叠。然后取当前屏幕上下左右5屏的距离作为总范围传入查询树中，开始遍历树，用数组去装聚合点，并判断点包含情况。最后遍历该数组，完成。
方案总结：
这个方案基本上与苹果的样式一样了，还原度达到90%。不过问题还是有，因为是取5倍屏幕，而是全中国，所以在小几率情况下，还是会出现平移时，数据发生变化。然后就是取当前地图level等量的矩形区域，这个数据并不准确，毕竟地图上的每个点都不太一样。效率方面没有方法2和方法3的高，但可以满足要求。
结论：
方法可行，暂时采用此方式。
当然方法5并不是最优解，目前正在思考一种更加完美的方案，不仅效率高，而且能够解决方法5中的问题。如果后续研究出来，将会继续提供方法6的思路，敬请期待。
有人问我，为什么不按项目时间进行，而总是即使加班也要提前完成。我觉得提前完成，可以让我花更多的时间提高app的用户体验，而且按照自己写好的测试用例来自测，让app少点bug，多点美感。以后别人想起我或者我做的app，可能会说到：喔，他呀！做的app，bug很少，而且体验很不错，是一位不错的开发人员。这样我就很高兴了。
著名的有才无德科学家曾说过：“如果我看得比别人更远些，那是因为我站在巨人的肩膀上。”能完成这个特效，感谢我爱的人，感谢月饼提供的部分C语言支持，感谢产品大湿的部分思路分析。
起因：产品大湿说，搞个地图，搞个类似苹果相册“地点”相簿的地图，可以显示10万+数据的。听到小道消息的我，立马从抽屉里拿出了海鸥匕首刺向产品大湿的胸膛，他现在正躺在医院治疗伤口，估计悬。
说起实现过程也是一波三折，采用了5种方法，完整耗时大概是3天，和上次新浪特效差不多。那么，废话不多说，开始讲过程。
方法1：
这个简单呀，以前做过天地图厦门项目，里面就写过聚合抽稀的算法，难不倒我，分分钟把代码拷贝过来。嗯，做法是：采用双重循环，计算点和点的距离，如果小于某个距离，就将两个点聚合。有点智商的人都能写出来。然后测测10万条数据，Oh my god，瞬间爆炸，机子卡住不动了，时间复杂度n^2，所以不动很正常。而且还发现以前写的算法代码还有可以优化的空间，哈哈，不过这工程已经由别人接手了，不管它。
方案总结：
这种方案可以达到较好的聚合效果，但是不同的地图level需要定义不同的距离。最重要的是效率太低。
结论：
此路不通，换一条路。研究失败并不是件坏事，这些失败的经验，往往是为成功打下铺垫。
方法2：
不行的话继续干，百度查找iOS地图聚合抽稀，出来的基本都是TBAnnotationClustering，工程的文章思路解析在这里：《How To Efficiently Display Large Amounts of Data on iOS Maps》。这个工程是采用四叉树的方式，将地图上的所有点全部划分到四叉树中，通过四叉树的方式，将查询和比对数据的效率大大提升，可以说工程的效率是很高的。其实如果要求没那么高的话，使用这样的代码就可以达到要求了。大概讲一下它的做法：根据需要聚合的点数据，将世界划分成四叉树，不断地四分，直至所有数据都挂在四叉树上，结束运算；此时所有的点经纬度都有一个范围，如果要比对，只需要比对范围就可以了。然后移动地图时，将当前可见区域放入，根据一定的比值，将当前区域划分成横竖n个格子。最后遍历树，将树上符合格子范围的点放入数组中，就可以得到聚合数据了。
方案总结：
效率是极高的，效果也算可以。但图标会重叠，不好；平移时，图标会变动，不好。而且有时候地图level 1有1个点，level 2有2个点，level 3却还是1个点，不符合正常逻辑。
结论：
此路不通，换一条路。朋友说高德也有一个点聚合demo，我就去下载了看了看，代码逻辑抄袭TBAnnotationClustering，就没什么可说的了。
方法3：
一个字干干干，继续。有了前人四叉树的基础上，我可以将刚才的世界范围换成中国，树顶点是中国范围。接下来解决一下重叠问题，怎么消除重叠呢？我想了想，尼玛，就把当前的屏幕区域分成等额的几份，不就OK了。然后横竖循环每个等额区域，将树上符合等额区域范围的点放入数组中，就可以得到聚合数据了。
方案总结：
重叠是不重叠了，效率也是极高的，放大缩小也没问题。但是每次平移地图，因为重新计算都会刷一下界面。体验当然不行。
结论：
此路不同，换一条路。万恶的百度，啊不，万能的百度求助完了之后，在某人的提醒下，求助我的好友：伟哥、陈大湿、首长，问他们之前有没有搞过关于地图聚合抽稀，伟哥说没搞过，首长也说没搞过，陈大湿比较热情，向我问了不少关联问题，但也没搞过。所以大部分还是得靠自己呀，不过感谢他们。
方法4：
怎么办呢，经过几天晚上梦周公的时间苦思冥想，终于想到了一种不错的方案。嗯嗯，大概说一下做法：将中国划分区域，不同的地图level划分不同等量的格子，比如0-3级别划分2X2格，4-7级别划分4X4格，8-11级别划分16X16……以此类推，然后双重循环，将树上符合等额区域范围的点放入数组中，就可以得到聚合数据了。但是，当分到65536X65536的时候，就发现，速度已经快不行了。这种说白了，时间复杂度还是n^2。
方案总结：
数据不重叠，而且放大后数据散开，平移图标不变，近乎完美。但是效率太低，而且聚合的间隙不能控制。
结论：
此路不同，换一条路。
方法5：
让我好好想想，将数据点挂在四叉树上这一步，感觉没什么问题，问题在于怎么将数据点的聚合效果做的和苹果一样。经过不断的思考，终于想出了一种新的做法：我根据图标的大小取出当前地图level等量的矩形区域，作为单个聚合点的范围，防止重叠。然后取当前屏幕上下左右5屏的距离作为总范围传入查询树中，开始遍历树，用数组去装聚合点，并判断点包含情况。最后遍历该数组，完成。
方案总结：
这个方案基本上与苹果的样式一样了，还原度达到90%。不过问题还是有，因为是取5倍屏幕，而是全中国，所以在小几率情况下，还是会出现平移时，数据发生变化。然后就是取当前地图level等量的矩形区域，这个数据并不准确，毕竟地图上的每个点都不太一样。效率方面没有方法2和方法3的高，但可以满足要求。
结论：
方法可行，暂时采用此方式。
当然方法5并不是最优解，目前正在思考一种更加完美的方案，不仅效率高，而且能够解决方法5中的问题。如果后续研究出来，将会继续提供方法6的思路，敬请期待。
有人问我，为什么不按项目时间进行，而总是即使加班也要提前完成。我觉得提前完成，可以让我花更多的时间提高app的用户体验，而且按照自己写好的测试用例来自测，让app少点bug，多点美感。以后别人想起我或者我做的app，可能会说到：喔，他呀！做的app，bug很少，而且体验很不错，是一位不错的开发人员。这样我就很高兴了。
