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

[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 坐标 请注意国内的坐标系, 百度坐标系 国标火星坐标系和全世界通用的坐标系, 要先转成全世界通用的坐标系在计算

[jinwyp]

其实用的算是光线追踪 理论
http://wandergis.github.io/2015/10/15/%E5%88%A4%E6%96%AD%E7%82%B9%E5%9C%A8%E9%9D%A2%E5%86%85/

[Isight]

楼上正解，大多数 CAD 系统都是用射线法来判断点的内外位置

[liujiangbei]

geohash

[cmingxu]

mysql5.6 天生支持的， ST_CONTAINS

[mzer0]

@feng32 你发的链接打不开(翻墙也打不开, 美国 ip), 你说的 Grid Method 是什么?

@jinwyp 很遗憾, 你的实现是错的, 你计算的是射线, 而不是线段.

[mzer0]

@jinwyp 纠正一下我刚才说的话.

1. 你实现的 pnpoly 是错的, 一方面是除法导致的精度问题(你应该把除法变成乘法), 一方面是你公式弄错了(如果我没误解 pnpoly 理论).

2. 我刚才读了一下你引用的参考链接(已读完), pnpoly 只能用来判断某些多边形(例如凸边形), StackOverflow 的问题下面已经有人提到了这个问题, 那个老外水平不咋地, StackOverflow 别的问答里也提到他在网页上写的 C 代码是错的(除法精度问题)......

[MCVector]

@feng32 应该就是 marching cube. Volumetric rendering 会用到的。

[mzer0]

@jinwyp 不好意思......出大丑了, ray-casting 就是射线法......我确实误解了 pnpoly......别的 StackOverflow 问答上提到的是他写的 C 语言代码没有用 epsilon 比较, 因此有精度问题.

[mzer0]

@MCVector 请问 marching cube. Volumetric rendering 是什么?

[dingyaguang117]

我习惯用射线法

[Ricepig]

射线法是 GIS 里解决 Point in Polygon 的标准算法了

填色法是并行性相对好的近似解法

[MCVector]

@mzer0 A grid based rendering technique. https://en.wikipedia.org/wiki/Marching_cubes

[mcone]

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

(1)为什么做不到？地理围栏算法判断点在闭合多边形内的算法，以及后续的 tricks 和优化已经很成熟了好吧…………之前我就在用……如果可以麻烦证明一下为何不可行呗？
(2)另外麻烦看清楼主的前提，楼主已经得到了一个“一个多边形”，由于没有多提及，这里只能假设楼主已经有了点和点点连线的集合（不然的话一群离散点完全晕了），相当于拓扑结构已知。这里已经没有必要求逆时针方向了


> 最后, 计算机基本功很重要, 我在 V2EX 一直是这个观点.
这句好无厘头

[mzer0]

@mcone

我昨天的发言又失妥当（装逼失败），在此抱歉。我对 geo 算法的印象是，它只能求最小近邻问题，而求不了点在多边形内。如有错误请指出，我对 geo 不熟悉。

[cruisehu]

毕业论文做的就是这个哈哈哈（捂脸

[beneo]

我觉得 LZ 的关键词没有搜对，这类问题其实早就有最优解的

https://en.wikipedia.org/wiki/Point_in_polygon