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