V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
dai269619118
V2EX  ›  程序员

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

  •  
  •   dai269619118 · 2016-01-08 17:32:36 +08:00 · 6356 次点击
    这是一个创建于 2153 天前的主题,其中的信息可能已经有所发展或是发生改变。

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


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

    36 条回复    2016-01-09 17:32:47 +08:00
    Strikeactor
        1
    Strikeactor   2016-01-08 17:42:03 +08:00   ❤️ 1
    跟多边形顶点连一下判断交点奇偶?
    rock_cloud
        2
    rock_cloud   2016-01-08 17:43:41 +08:00   ❤️ 4
    dai269619118
        3
    dai269619118   2016-01-08 17:45:51 +08:00
    @Strikeactor
    @rock_cloud 谢谢 我研究下
    NeoAtlantis
        4
    NeoAtlantis   2016-01-08 18:45:15 +08:00
    我直觉认为应该是如果逆时针考察多边形的各个边,则点应该在各个边(的向量)的左边。
    strahe
        5
    strahe   2016-01-08 18:49:04 +08:00
    我们公司也用到这种情况,不过不是我,听同事们讨论貌似是用的 mongodb 自带的什么功能
    jsyangwenjie
        6
    jsyangwenjie   2016-01-08 18:49:43 +08:00
    凸包。
    guoxx_
        7
    guoxx_   2016-01-08 19:11:15 +08:00 via Android
    以三角行为例,你的多边形是可以切成小的三角形的。
    一个方法 @NeoAtlantis 已经说了。不过这种做法没办法判断边界条件。比如点在三角形边的延长线的时候。

    另一个常见做法是,根据要判断的点和三角形。生成三个新的三角形。如果这三个新三角形的面积等于原来的三角形的面积,那么这个点落在这个三角形之内。
    deangl
        8
    deangl   2016-01-08 19:16:30 +08:00 via Android
    经典的回答不是:上色填充多边形,然后查看该点的颜色吗?
    bobuick
        9
    bobuick   2016-01-08 19:49:53 +08:00
    geo 算法就可以了。
    而且能用 db 来解决, pg 一类的数据库已经能直接支持了, 就是点和二维面交点, contain 的关系问题
    mcone
        10
    mcone   2016-01-08 20:01:24 +08:00
    @NeoAtlantis @jsyangwenjie 题主没有说配送的多边形是凸多边形,如果是凹的话,就不能这么弄了(凹多边形配送区域在 LBS 服务里面其实挺常见的,例如沿着直线马路,配送距离可以稍微远一些;如果有什么死胡同的话,可能死胡同后面区域就会放弃掉)

    @dai269619118 可以参考楼上那个链接,就是传说中的 geo 算法系列应该都行。但是实用中我觉得一般都是送到很集中的写字楼或者小区吧,分块,然后直接暴力也许就行了(捂脸……
    slixurd
        11
    slixurd   2016-01-08 20:03:15 +08:00
    这种东西如果没有非常好的算法基础和工程知识就不要自己写了
    用 Elastic Search 这样的解决方案简单快捷。
    zanpen2000
        12
    zanpen2000   2016-01-08 20:07:00 +08:00
    @deangl 这个想法厉害
    mzer0
        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 是在多边形内.
    SeanChense
        14
    SeanChense   2016-01-08 20:22:28 +08:00
    @mcone 第一反应就是要分凹凸然后什么都不知道了 、= =
    mzer0
        15
    mzer0   2016-01-08 20:25:06 +08:00
    @mcone

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

    最后, 计算机基本功很重要, 我在 V2EX 一直是这个观点.
    feng32
        16
    feng32   2016-01-08 20:25:13 +08:00
    我之前有篇论文是涉及这个问题的 (point in polygon detection)
    等会儿我来回答一下吧
    killerv
        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
    jsyangwenjie
        18
    jsyangwenjie   2016-01-08 20:44:31 +08:00
    @mcone sorry ,想当然以为凸包可以处理了。
    feng32
        19
    feng32   2016-01-08 20:52:04 +08:00   ❤️ 2
    仔细看了一下,基本方法好像楼上都有提到了,就不重复了。要是楼主有空的话,可以看看这个链接(英文):

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

    基本上把所有的方法原理都梳理了一遍。里面一个简单的优化方法是所谓的 Grid Method 。在参数配置合理的情况下可以把时间复杂度控制在 O(1),但是 O(1) 的算法都是需要预处理的
    jinwyp
        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 坐标 请注意国内的坐标系, 百度坐标系 国标火星坐标系和全世界通用的坐标系, 要先转成全世界通用的坐标系在计算
    jinwyp
        21
    jinwyp   2016-01-08 21:27:59 +08:00   ❤️ 1
    Isight
        22
    Isight   2016-01-08 21:39:51 +08:00 via Android
    楼上正解,大多数 CAD 系统都是用射线法来判断点的内外位置
    liujiangbei
        23
    liujiangbei   2016-01-08 22:56:02 +08:00
    geohash
    cmingxu
        24
    cmingxu   2016-01-08 23:14:39 +08:00
    mysql5.6 天生支持的, ST_CONTAINS
    mzer0
        25
    mzer0   2016-01-08 23:17:52 +08:00
    @feng32 你发的链接打不开(翻墙也打不开, 美国 ip), 你说的 Grid Method 是什么?

    @jinwyp 很遗憾, 你的实现是错的, 你计算的是射线, 而不是线段.
    mzer0
        26
    mzer0   2016-01-08 23:51:15 +08:00
    @jinwyp 纠正一下我刚才说的话.

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

    2. 我刚才读了一下你引用的参考链接(已读完), pnpoly 只能用来判断某些多边形(例如凸边形), StackOverflow 的问题下面已经有人提到了这个问题, 那个老外水平不咋地, StackOverflow 别的问答里也提到他在网页上写的 C 代码是错的(除法精度问题)......
    MCVector
        27
    MCVector   2016-01-08 23:53:17 +08:00
    @feng32 应该就是 marching cube. Volumetric rendering 会用到的。
    mzer0
        28
    mzer0   2016-01-09 00:06:08 +08:00
    @jinwyp 不好意思......出大丑了, ray-casting 就是射线法......我确实误解了 pnpoly......别的 StackOverflow 问答上提到的是他写的 C 语言代码没有用 epsilon 比较, 因此有精度问题.
    mzer0
        29
    mzer0   2016-01-09 00:14:11 +08:00
    @MCVector 请问 marching cube. Volumetric rendering 是什么?
    dingyaguang117
        30
    dingyaguang117   2016-01-09 00:17:26 +08:00
    我习惯用射线法
    Ricepig
        31
    Ricepig   2016-01-09 00:29:26 +08:00
    射线法是 GIS 里解决 Point in Polygon 的标准算法了

    填色法是并行性相对好的近似解法
    MCVector
        32
    MCVector   2016-01-09 02:15:12 +08:00
    @mzer0 A grid based rendering technique. https://en.wikipedia.org/wiki/Marching_cubes
    mcone
        33
    mcone   2016-01-09 09:28:40 +08:00
    @mzer0
    > 顺便一提, GEO 只能实现方法一中的"逆时针方向"(我一般用 KNN 算法), 而判断点是否在多边形内是做不到的.

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


    > 最后, 计算机基本功很重要, 我在 V2EX 一直是这个观点.
    这句好无厘头
    mzer0
        34
    mzer0   2016-01-09 13:42:19 +08:00 via iPhone
    @mcone

    我昨天的发言又失妥当(装逼失败),在此抱歉。我对 geo 算法的印象是,它只能求最小近邻问题,而求不了点在多边形内。如有错误请指出,我对 geo 不熟悉。
    cruisehu
        35
    cruisehu   2016-01-09 14:09:58 +08:00
    毕业论文做的就是这个哈哈哈(捂脸
    beneo
        36
    beneo   2016-01-09 17:32:47 +08:00
    我觉得 LZ 的关键词没有搜对,这类问题其实早就有最优解的

    https://en.wikipedia.org/wiki/Point_in_polygon
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2684 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 117ms · UTC 13:00 · PVG 21:00 · LAX 05:00 · JFK 08:00
    ♥ Do have faith in what you're doing.