V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
ChunkitAu
V2EX  ›  问与答

如何判断一个点是否在一个不规则封闭图形里面?

  •  
  •   ChunkitAu · 2021-01-26 12:03:34 +08:00 · 1701 次点击
    这是一个创建于 566 天前的主题,其中的信息可能已经有所发展或是发生改变。

    如题:

    在二维场景中,一个点(x,y) 不规则封闭图形(图形边界坐标数组),怎么判断这个点在个图形里面?

    比如,我一个定位坐标,怎么判断他是否在广东省内(只有边界坐标点)?

    有什么资料可以参考吗?

    15 条回复    2021-01-26 14:53:40 +08:00
    wayne1007
        1
    wayne1007  
       2021-01-26 12:41:55 +08:00
    碰撞检测算法有很多的,我只记得射线法了
    grimpil
        2
    grimpil  
       2021-01-26 12:44:20 +08:00 via Android
    资料有很多,去找百度或者谷歌免费提取
    aihgf
        3
    aihgf  
       2021-01-26 12:49:18 +08:00
    python shapely 库
    codehz
        4
    codehz  
       2021-01-26 12:50:48 +08:00 via Android   ❤️ 1
    首先确保边界坐标按一定顺序排列,指可以一笔画完的那种,然后保证都是逆时针或者都是顺时针(这里假设是逆时针),可以存在交叉,凹陷,甚至在多边形内部挖孔,只要确保最终是封闭的就好。
    然后做个矩形范围快速检测,也就是确保目标点落在图形的矩形范围内。
    然后可以选择一个参考轴,这里假设是水平 x 轴,其实可以为任何角度,选择一个就好。
    接着从目标点出发向那个方向发出一个射线,然后对每一个图形上的每一个线段做相交判定,这就是一个初中数学问题,计算射线和线段的交点,如果不相交,跳过,反之,通过线段 y 轴坐标之差的符号,判定是进入了图形还是离开了图形。
    然后遍历完所有线段后,将离开图形的次数和进入图形的次数相减(算法实现上可以在相交的时候计算),只有 3 个可能的值,出现别的说明你算法写糊了或者图形有重叠,-1 说明你点的顺序拿反了,整个图形的外部被认为是内部,0 说明点没进图形,1 说明点在图形内部
    wpblank
        5
    wpblank  
       2021-01-26 12:52:03 +08:00 via iPhone
    哈哈 我当时面试就被问的这个问题,搜索引擎搜一下就有了
    fightingZ
        6
    fightingZ  
       2021-01-26 12:52:21 +08:00 via Android
    约束 x,判断 y 是否在线段内?
    gulu
        7
    gulu  
       2021-01-26 12:55:17 +08:00 via Android
    首先选定区域内一个点 P
    从你的点 M 往点 P 方向做一条射线
    如果该射线与多边形的 N 条边相交,且 N 为偶数,则点在多边形外部
    morethansean
        8
    morethansean  
       2021-01-26 12:56:17 +08:00
    你直接 Google 一下 point in polygon 就能找到很多吧,最常见的 ray casting,从点做射线,判断和多边形边的相交次数,偶数在外部,奇数在内部。
    ChunkitAu
        9
    ChunkitAu  
    OP
       2021-01-26 13:03:26 +08:00 via Android
    @codehz 虽然没完全理解你的说法,但有思路了。如果按坐标为原点 ,假设一个象限空间,如果坐标在图形内,原点与边上的点的差值会排布到所有象限了。
    renmu123
        10
    renmu123  
       2021-01-26 13:09:26 +08:00 via Android
    你找找 geo 库应该有类似的函数
    kay666
        11
    kay666  
       2021-01-26 13:44:25 +08:00
    你是想做地图电子围栏?
    700388
        12
    700388  
       2021-01-26 14:21:47 +08:00
    网上提供的方法只适用于简单规则封闭曲线, 稍微复杂点,算法就会失效。比如 在一个不规则的封闭曲线中,谁是中心点都难以判断那种。 我测试了很多次的。目前数学界根本没有,不规则封闭曲线判定方法。
    wasd6267016
        13
    wasd6267016  
       2021-01-26 14:42:53 +08:00
    点积
    wasd6267016
        14
    wasd6267016  
       2021-01-26 14:50:55 +08:00
    对于特定点 N 和凸多边形边界点 ABCD……
    先保证边界点是依次(比如顺时针)排列的
    然后向量 AN 和向量 AB 的点积有个正负 再看 BN 和 BC 的 如果这写正负都一样 则在凸多边形内
    wasd6267016
        15
    wasd6267016  
       2021-01-26 14:53:40 +08:00
    @wasd6267016 点积
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3271 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 34ms · UTC 04:50 · PVG 12:50 · LAX 21:50 · JFK 00:50
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.