如何实现基于商圈和地标的位置搜索

简介

标题中包含了两个关键词,商圈和地标,先来解释一下商圈和地标这两个名词。商圈是一个地理范围,但并不是官方的划分,而是民间大致的划分,它通常提供了民众消费、娱乐的功能,产生了一个相对集中的活动区域,比如王府井、五棵松。地标是地图上的一个点,它通常在某个范围有一定知名度,大家都知道它,它可以是一个大厦、景点、酒店、饭店,比如人民大会堂、北京工人体育场、大裤衩大楼等等。那实现这两个的搜索有什么好处呢?比如我打算去王府井溜达,提前订好吃饭的地方,就可以搜王府井附近有什么饭店,再比如我晚上去工人体育场看演唱会,提前订好住的地方,就可以搜索工人体育场附近有什么酒店。极大丰富了应用中的搜索场景。

商圈如何划定

地标不存在划定的问题,商圈的划定方式大体可以分为三类,多边形、矩形、圆形。

多边形

根据实际的商圈范围,划定边界,形成一个不规则形状。它的边界是由多个坐标点连线组成。

http://developer.baidu.com/map/jsdemo.htm#c2_9

存储时,需要将每个顶点坐标存下来。这样划分商圈会非常精确,就像官方的地理区域划分一样。但当判断一个坐标是否在这个商圈内的算法会比较复杂,可以先设定商圈内一个点X,然后将测定点P和X之间连线PX,如果PX跟商圈边界的交点是偶数个(0,2,4,…),则测定点P在商圈内;如果交点是奇数个(1,3,5,…),则测定点P在商圈外,可以参考java.awt.Polygon.contains的实现。

矩形

使用矩形来划定商圈,但矩形存在一个问题,就是不精确,容易划大或者划小,可以通过多个矩形来解决,精确度次于多边形。

http://developer.baidu.com/map/jsdemo.htm#i1_2

存储时,需要将每个矩形的对角坐标存下来(对角坐标就能确定一个矩形)。判断一个坐标是否在这个商圈内时,直接判断测定点经纬度是否在矩形经纬度的范围内,多个矩形要判断多次。

圆形

使用圆形来划定商圈,圆形比较符合我们对商圈的理解,圈不就是圆嘛。圆形的问题和解决方式同矩形,精确度次于矩形。

http://developer.baidu.com/map/jsdemo.htm#i3_2

存储时,需要将每个圆的圆心坐标和半径存下来。判断一个坐标是否在这个商圈内时,直接算测定点和圆心的距离,如果距离大于半径,则测定点在商圈外;否则在商圈内,多个圆要判断多次。

商圈搜索POI

接下来看一下如何根据商圈搜索POI,不同的划定方式实现是不一样的。

多边形

由于多边形的计算比较复杂,无法实时搜索。只能是将商圈和POI的关系提前建立好。

当新建或更新一个POI时,都需要判定它归属于哪个商圈,判定算法上面提到了,同样,当新建或更新一个商圈时,都需要计算哪些POI能归属到该商圈内,这时怎么计算呢?最笨的办法是遍历一次POI表,依次判断,但计算成本太高了,这里可以优化下,先取到商圈顶点坐标中最大经度、最小经度、最大纬度、最小纬度,这样就拿到了一个经纬度范围(商圈范围∈经纬度范围),然后再用经纬度范围到POI表中查找候选集,最后遍历这个候选集判断。

矩形&圆形

表结构同上,矩形和圆形都可以实时搜索,所以不需要POI和商圈的映射表。可以参照“何实现按距离排序、范围查找”这篇文章,实现方式基本一致,这里不再赘述。

地标搜索POI

地标本身也是POI,它有一个坐标,这个问题就变成了“给定一个坐标,如何搜索附近POI”,也参照“何实现按距离排序、范围查找”这篇文章。

总结

本文列举了三种方式去实现商圈搜索,现在从三个角度对比来看:

#

精确度

复杂度

灵活度

多边形

矩形

圆形

解释一下,精确度:很好理解,就是划定商圈的准确性,无疑多边形是最精准的;复杂度:实现的复杂性,包括前后端的整体实现;灵活度:其实是复杂度的一个延伸属性,复杂的实现肯定会丧失灵活度,比如多边形商圈更新会连带着POI也更新。通常情况下,我们O2O应用中对精确度都没有太高的要求,用户感知不到就好了,所以我建议采用矩形和圆形划定商圈,这样你会额外发现一个好处,所有基于位置去搜索POI的功能(离我最近、按商圈搜、按地标搜),底层的搜索实现都是同一个。如果对精确度有很高要求,只能选择多边形。

引用

http://stackoverflow.com/questions/8721406/how-to-determine-if-a-point-is-inside-a-2d-convex-polygon http://developer.baidu.com/map/jsdemo.htm

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏DannyHoo的专栏

iOS开发中使用算法之二分搜索算法

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u010105969/article/details/...

612
来自专栏生信宝典

R语言学习 - 富集分析泡泡图

功能富集泡泡图 功能富集分析用来展示某一组基因(一般是单个样品上调或下调的基因)倾向参与哪些功能调控通路,对从整体理解变化了的基因的功能和潜在的调控意义具有指导...

3329
来自专栏深度学习与数据挖掘实战

Kaggle竞赛:《NIPS 2017 Adversarial Learning Challenges》

Batch normalization potentially helps in two ways: faster learning and higher ov...

722
来自专栏小樱的经验随笔

“盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛题解&&源码【A,水,B,水,C,水,D,快速幂,E,优先队列,F,暴力,G,贪心+排序,H,STL乱搞,I,尼姆博弈,J,差分dp

黑白图像直方图 发布时间: 2017年7月9日 18:30   最后更新: 2017年7月10日 21:08   时间限制: 1000ms   内存限制: 12...

2995
来自专栏生信技能树

【r<-ROC|包】分析与可视化ROC——plotROC、pROC

在【r<-绘图|ROC】ROC的计算与绘制这篇文章中我讲了ROC曲线的本质以及如何计算和绘制ROC曲线。注意,我这里谈到的ROC并未曾涉及机器学习模型的拟合与预...

1452
来自专栏数据结构与算法

1142 奖学金 sort做法

个人博客:doubleq.win 1142 奖学金 2007年NOIP全国联赛普及组  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 白...

2675
来自专栏数据结构与算法

06:寻宝

06:寻宝 总时间限制: 2000ms 内存限制: 65536kB描述 传说很遥远的藏宝楼顶层藏着诱人的宝藏。小明历尽千辛万苦终于找到传说中的这个藏 宝楼,...

4227
来自专栏CreateAMind

Auto-Encoding GAN

Mihaela Rosca, Balaji Lakshminarayanan, David Warde-Farley, Shakir Mohamed

521
来自专栏calmound

图的着色

图着色问题,相邻的点颜色不同       基础知识:http://wenku.baidu.com/view/d7242fd1c1c708a1284a444d.h...

2607
来自专栏ACM算法日常

消防车Firetruck(DFS+回溯)- UVA 208

中心城市消防部门与运输部门合作,维护反映城市街道现状的城市地图。消防员需要能够选择从火警站到火警的路线。 中心城市分为不重叠...

652

扫码关注云+社区