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

[ChunkitAu]

如题:

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

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

有什么资料可以参考吗?

[wayne1007]

碰撞检测算法有很多的，我只记得射线法了

[grimpil]

资料有很多，去找百度或者谷歌免费提取

[aihgf]

python shapely 库

[codehz]

首先确保边界坐标按一定顺序排列，指可以一笔画完的那种，然后保证都是逆时针或者都是顺时针（这里假设是逆时针），可以存在交叉，凹陷，甚至在多边形内部挖孔，只要确保最终是封闭的就好。
然后做个矩形范围快速检测，也就是确保目标点落在图形的矩形范围内。
然后可以选择一个参考轴，这里假设是水平 x 轴，其实可以为任何角度，选择一个就好。
接着从目标点出发向那个方向发出一个射线，然后对每一个图形上的每一个线段做相交判定，这就是一个初中数学问题，计算射线和线段的交点，如果不相交，跳过，反之，通过线段 y 轴坐标之差的符号，判定是进入了图形还是离开了图形。
然后遍历完所有线段后，将离开图形的次数和进入图形的次数相减（算法实现上可以在相交的时候计算），只有 3 个可能的值，出现别的说明你算法写糊了或者图形有重叠，-1 说明你点的顺序拿反了，整个图形的外部被认为是内部，0 说明点没进图形，1 说明点在图形内部

[wpblank]

哈哈 我当时面试就被问的这个问题，搜索引擎搜一下就有了

[fightingZ]

约束 x，判断 y 是否在线段内？

[gulu]

首先选定区域内一个点 P
从你的点 M 往点 P 方向做一条射线
如果该射线与多边形的 N 条边相交，且 N 为偶数，则点在多边形外部

[morethansean]

你直接 Google 一下 point in polygon 就能找到很多吧，最常见的 ray casting，从点做射线，判断和多边形边的相交次数，偶数在外部，奇数在内部。

[ChunkitAu]

@codehz 虽然没完全理解你的说法，但有思路了。如果按坐标为原点 ，假设一个象限空间，如果坐标在图形内，原点与边上的点的差值会排布到所有象限了。

[renmu123]

你找找 geo 库应该有类似的函数

[kay666]

你是想做地图电子围栏？

[700388]

网上提供的方法只适用于简单规则封闭曲线， 稍微复杂点，算法就会失效。比如 在一个不规则的封闭曲线中，谁是中心点都难以判断那种。 我测试了很多次的。目前数学界根本没有，不规则封闭曲线判定方法。

[wasd6267016]

点积

[wasd6267016]

对于特定点 N 和凸多边形边界点 ABCD……
先保证边界点是依次（比如顺时针）排列的
然后向量 AN 和向量 AB 的点积有个正负 再看 BN 和 BC 的 如果这写正负都一样 则在凸多边形内

[wasd6267016]

@wasd6267016 点积