这是一个创建于 1426 天前的主题，其中的信息可能已经有所发展或是发生改变。
如题:
在二维场景中,一个点(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 点积
|
Select Language