地图，根据一个点，判读这个点是否在某个多边形范围内

[dai269619118]

这几天折腾地图，给一个门店设置了一个配送范围 是一个多边形。
然后每次用户下单，需要判读这个用户所在的地方的经纬度是否在这个门店设置范围内。

---

对地图没有深入研究...网上有 C#的例子 我自己拿来翻译成 php 的用起来不对。
有人能提供个例子吗？

[Strikeactor]

跟多边形顶点连一下判断交点奇偶？

[rock_cloud]

http://www.cnblogs.com/LBSer/p/4471742.html

[dai269619118]

@Strikeactor
@rock_cloud 谢谢 我研究下

[NeoAtlantis]

我直觉认为应该是如果逆时针考察多边形的各个边，则点应该在各个边（的向量）的左边。

[strahe]

我们公司也用到这种情况，不过不是我，听同事们讨论貌似是用的 mongodb 自带的什么功能

[jsyangwenjie]

凸包。

[guoxx_]

以三角行为例，你的多边形是可以切成小的三角形的。
一个方法 @NeoAtlantis 已经说了。不过这种做法没办法判断边界条件。比如点在三角形边的延长线的时候。

另一个常见做法是，根据要判断的点和三角形。生成三个新的三角形。如果这三个新三角形的面积等于原来的三角形的面积，那么这个点落在这个三角形之内。

[deangl]

经典的回答不是：上色填充多边形，然后查看该点的颜色吗？

[bobuick]

geo 算法就可以了。
而且能用 db 来解决， pg 一类的数据库已经能直接支持了， 就是点和二维面交点， contain 的关系问题

[mcone]

@NeoAtlantis @jsyangwenjie 题主没有说配送的多边形是凸多边形，如果是凹的话，就不能这么弄了（凹多边形配送区域在 LBS 服务里面其实挺常见的，例如沿着直线马路，配送距离可以稍微远一些；如果有什么死胡同的话，可能死胡同后面区域就会放弃掉）

@dai269619118 可以参考楼上那个链接，就是传说中的 geo 算法系列应该都行。但是实用中我觉得一般都是送到很集中的写字楼或者小区吧，分块，然后直接暴力也许就行了（捂脸……

[slixurd]

这种东西如果没有非常好的算法基础和工程知识就不要自己写了
用 Elastic Search 这样的解决方案简单快捷。

[zanpen2000]

@deangl 这个想法厉害

[mzer0]

@Strikeactor
@rock_cloud
@NeoAtlantis
@strahe
@jsyangwenjie
@guoxx_
@deangl

数学系实力作答. 有两种方法可以判断, 第一种方法要求服务器做预处理, 占用内存少. 第二种方法不需要, 但空间复杂度为 N^2(占内存多). 以下假设用户坐标为 P.

方法一

你拥有关于配送范围多边形的 N 个顶点, 你需要计算"逆时针方向"----随机选取第一个点 P1, 求出在 P1 左边离 P1 最近的点 P2, 接着求出在 P2 左边离 P2 最近的点 P3, 重复此过程, 直到所有 N 个点被数完, 你将得到一个序列 P1...PN, 这就是"逆时针方向". 对于任意一个点 P, 你只要用余弦定理计算: P 和 P1,P2 的夹角, 加上 P 和 P2,P3 的夹角, ..., 一直加到 P 和 PN-1, PN 的夹角, 判断其合是否等于 360 度, 若等于, 则在多边形内.

方法二

利用 bitmap(位图排序中的 bitmap), 将 N 个点映射到 bitmap 上, 从左到右数, 直到数到点 P, 判断点 P 是否存在左邻, 右邻; 下上往下数, 判断点 P 是否存在上邻, 下邻. 如果 P 的上下左右邻能构成一个菱形, 即左邻和友邻在上邻和下邻之间, 上邻和下邻同样在左邻和友邻之间, 则 P 是在多边形内.

[SeanChense]

@mcone 第一反应就是要分凹凸然后什么都不知道了 、= =

[mzer0]

@mcone

顺便一提, GEO 只能实现方法一中的"逆时针方向"(我一般用 KNN 算法), 而判断点是否在多边形内是做不到的.

最后, 计算机基本功很重要, 我在 V2EX 一直是这个观点.

[feng32]

我之前有篇论文是涉及这个问题的 (point in polygon detection)
等会儿我来回答一下吧

[killerv]

百度地图开源库有这个算法， js 的，你可以转成你想要的
http://developer.baidu.com/map/library.htm
http://api.map.baidu.com/library/GeoUtils/1.2/examples/simple.html

[jsyangwenjie]

@mcone sorry ，想当然以为凸包可以处理了。

[feng32]

仔细看了一下，基本方法好像楼上都有提到了，就不重复了。要是楼主有空的话，可以看看这个链接（英文）：

http://erich.realtimerendering.com/ptinpoly/

基本上把所有的方法原理都梳理了一遍。里面一个简单的优化方法是所谓的 Grid Method 。在参数配置合理的情况下可以把时间复杂度控制在 O(1)，但是 O(1) 的算法都是需要预处理的

[jinwyp]

请叫我雷锋, 不用面积和 bitmap
完全用点与线交点判断

https://github.com/substack/point-in-polygon

https://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

如果还不会一会我给源码, 注意如果用国内的 GPS 坐标 请注意国内的坐标系, 百度坐标系 国标火星坐标系和全世界通用的坐标系, 要先转成全世界通用的坐标系在计算