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

[dai269619118]

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

---

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

[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