这是一个创建于 3279 天前的主题，其中的信息可能已经有所发展或是发生改变。
这几天折腾地图，给一个门店设置了一个配送范围 是一个多边形。
然后每次用户下单，需要判读这个用户所在的地方的经纬度是否在这个门店设置范围内。
对地图没有深入研究...网上有 C#的例子 我自己拿来翻译成 php 的用起来不对。
有人能提供个例子吗？
 |
1
Strikeactor 2016-01-08 17:42:03 +08:00  1
跟多边形顶点连一下判断交点奇偶？
|
 |
2
rock_cloud 2016-01-08 17:43:41 +08:00 4
|
 |
3
dai269619118 OP |
 |
4
NeoAtlantis 2016-01-08 18:45:15 +08:00
我直觉认为应该是如果逆时针考察多边形的各个边，则点应该在各个边（的向量）的左边。
|
 |
5
strahe 2016-01-08 18:49:04 +08:00
我们公司也用到这种情况，不过不是我，听同事们讨论貌似是用的 mongodb 自带的什么功能
|
 |
6
jsyangwenjie 2016-01-08 18:49:43 +08:00
凸包。
|
 |
7
guoxx_ 2016-01-08 19:11:15 +08:00 via Android
以三角行为例，你的多边形是可以切成小的三角形的。
一个方法 @NeoAtlantis 已经说了。不过这种做法没办法判断边界条件。比如点在三角形边的延长线的时候。 另一个常见做法是，根据要判断的点和三角形。生成三个新的三角形。如果这三个新三角形的面积等于原来的三角形的面积，那么这个点落在这个三角形之内。 |
 |
8
deangl 2016-01-08 19:16:30 +08:00 via Android
经典的回答不是：上色填充多边形，然后查看该点的颜色吗？
|
 |
9
bobuick 2016-01-08 19:49:53 +08:00
geo 算法就可以了。
而且能用 db 来解决， pg 一类的数据库已经能直接支持了， 就是点和二维面交点， contain 的关系问题 |
 |
10
mcone 2016-01-08 20:01:24 +08:00
@NeoAtlantis @jsyangwenjie 题主没有说配送的多边形是凸多边形，如果是凹的话，就不能这么弄了（凹多边形配送区域在 LBS 服务里面其实挺常见的，例如沿着直线马路，配送距离可以稍微远一些；如果有什么死胡同的话，可能死胡同后面区域就会放弃掉）
@dai269619118 可以参考楼上那个链接，就是传说中的 geo 算法系列应该都行。但是实用中我觉得一般都是送到很集中的写字楼或者小区吧，分块，然后直接暴力也许就行了（捂脸…… |
 |
11
slixurd 2016-01-08 20:03:15 +08:00
这种东西如果没有非常好的算法基础和工程知识就不要自己写了
用 Elastic Search 这样的解决方案简单快捷。 |
 |
12
zanpen2000 2016-01-08 20:07:00 +08:00
@deangl 这个想法厉害
|
 |
13
mzer0 2016-01-08 20:22:11 +08:00 3
@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 是在多边形内. |
 |
14
SeanChense 2016-01-08 20:22:28 +08:00
@mcone 第一反应就是要分凹凸然后什么都不知道了 、= =
|
|
15
mzer0 2016-01-08 20:25:06 +08:00
|
 |
16
feng32 2016-01-08 20:25:13 +08:00
我之前有篇论文是涉及这个问题的 (point in polygon detection)
等会儿我来回答一下吧 |
 |
17
killerv 2016-01-08 20:25:27 +08:00
百度地图开源库有这个算法， js 的，你可以转成你想要的
http://developer.baidu.com/map/library.htm http://api.map.baidu.com/library/GeoUtils/1.2/examples/simple.html |
|
18
jsyangwenjie 2016-01-08 20:44:31 +08:00
@mcone sorry ，想当然以为凸包可以处理了。
|
|
19
feng32 2016-01-08 20:52:04 +08:00 2
仔细看了一下，基本方法好像楼上都有提到了，就不重复了。要是楼主有空的话，可以看看这个链接（英文）：
http://erich.realtimerendering.com/ptinpoly/ 基本上把所有的方法原理都梳理了一遍。里面一个简单的优化方法是所谓的 Grid Method 。在参数配置合理的情况下可以把时间复杂度控制在 O(1)，但是 O(1) 的算法都是需要预处理的 |
 |
20
jinwyp 2016-01-08 21:26:13 +08:00 1
请叫我雷锋, 不用面积和 bitmap
完全用点与线交点判断 https://github.com/substack/point-in-polygon https://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html 如果还不会一会我给源码, 注意如果用国内的 GPS 坐标 请注意国内的坐标系, 百度坐标系 国标火星坐标系和全世界通用的坐标系, 要先转成全世界通用的坐标系在计算 |
|
21
jinwyp 2016-01-08 21:27:59 +08:00 1
|
 |
22
Isight 2016-01-08 21:39:51 +08:00 via Android
楼上正解，大多数 CAD 系统都是用射线法来判断点的内外位置
|
 |
23
liujiangbei 2016-01-08 22:56:02 +08:00
geohash
|
 |
24
cmingxu 2016-01-08 23:14:39 +08:00
mysql5.6 天生支持的， ST_CONTAINS
|
|
25
mzer0 2016-01-08 23:17:52 +08:00
|
|
26
mzer0 2016-01-08 23:51:15 +08:00
@jinwyp 纠正一下我刚才说的话.
1. 你实现的 pnpoly 是错的, 一方面是除法导致的精度问题(你应该把除法变成乘法), 一方面是你公式弄错了(如果我没误解 pnpoly 理论). 2. 我刚才读了一下你引用的参考链接(已读完), pnpoly 只能用来判断某些多边形(例如凸边形), StackOverflow 的问题下面已经有人提到了这个问题, 那个老外水平不咋地, StackOverflow 别的问答里也提到他在网页上写的 C 代码是错的(除法精度问题)...... |
|
28
mzer0 2016-01-09 00:06:08 +08:00
@jinwyp 不好意思......出大丑了, ray-casting 就是射线法......我确实误解了 pnpoly......别的 StackOverflow 问答上提到的是他写的 C 语言代码没有用 epsilon 比较, 因此有精度问题.
|
 |
30
dingyaguang117 2016-01-09 00:17:26 +08:00
我习惯用射线法
|
 |
31
Ricepig 2016-01-09 00:29:26 +08:00
射线法是 GIS 里解决 Point in Polygon 的标准算法了
填色法是并行性相对好的近似解法 |
 |
32
MCVector 2016-01-09 02:15:12 +08:00
@mzer0 A grid based rendering technique. https://en.wikipedia.org/wiki/Marching_cubes
|
|
33
mcone 2016-01-09 09:28:40 +08:00
@mzer0
> 顺便一提, GEO 只能实现方法一中的"逆时针方向"(我一般用 KNN 算法), 而判断点是否在多边形内是做不到的. (1)为什么做不到？地理围栏算法判断点在闭合多边形内的算法，以及后续的 tricks 和优化已经很成熟了好吧…………之前我就在用……如果可以麻烦证明一下为何不可行呗？ (2)另外麻烦看清楼主的前提，楼主已经得到了一个“一个多边形”，由于没有多提及，这里只能假设楼主已经有了点和点点连线的集合（不然的话一群离散点完全晕了），相当于拓扑结构已知。这里已经没有必要求逆时针方向了 > 最后, 计算机基本功很重要, 我在 V2EX 一直是这个观点. 这句好无厘头 |
|
34
mzer0 2016-01-09 13:42:19 +08:00 via iPhone
|
 |
35
cruisehu 2016-01-09 14:09:58 +08:00
毕业论文做的就是这个哈哈哈（捂脸
|
 |
36
beneo 2016-01-09 17:32:47 +08:00
|
Select Language