[GIS算法] 2.6.1 判断点是否在多边形内
目录
文章目录
射线法 | 奇偶测试法
射线法,也叫奇偶测试法
简单的射线法
【交点数目】一条射线从点P开始,穿过多边形的边界的次数称为交点数目
【判断】
- 交点数目=偶数 => P在多边形外部
- 交点数目=奇数 => P在多边形内部
【适用情况】多边形是简单的(没有自相交点)
【缺点|不适用的情况】对于非简单多边形,是不适用的
改良后的射线法
【改良思路】
- 确保只有会改变出入特性的穿越才被计算。特别是,有些特殊的情况下射线会经过顶点,这时必须要进行适当的处理
- 决定在多边形边界上的点是在多边形内部还是外部
一个标准是:在左边界或下边界上的点认为是在多边形内部,在右边界或上边界的点认为是在多边形外部
【好处】如果两个不同的多边形共享一个公共边,那么在这条边上的点会在一个多边形的内部而在另一个多边形的外部
【规则】
- 方向向上的边包括其开始点,不包括其终止点
- 方向向下的边不包括其开始点,包括其终止点
- 水平边不参与穿越测试
- 射线和多边形的边的交点必须严格在点P的右边
转角法
【环绕数】多边形环绕点P的次数称为环绕数
【判断】
- 环绕数=0 => P在多边形外部
- 环绕书≠0 => P在多边形内部
转载自:https://blog.csdn.net/summer_dew/article/details/83982367