美文网首页
iOS苹果相册“地点”相簿效果实现浅谈

iOS苹果相册“地点”相簿效果实现浅谈

作者: 软件iOS开发 | 来源:发表于2018-02-02 11:33 被阅读16次

著名的有才无德科学家曾说过:“如果我看得比别人更远些,那是因为我站在巨人的肩膀上。”能完成这个特效,感谢我爱的人,感谢月饼提供的部分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很少,而且体验很不错,是一位不错的开发人员。这样我就很高兴了。

相关文章

网友评论

      本文标题:iOS苹果相册“地点”相簿效果实现浅谈

      本文链接:https://www.haomeiwen.com/subject/gbiszxtx.html