【GIS算法:点在多边形内】射线法判断点在多边形内

已被阅读 2870 次 | 文章分类:gis随笔 | 2022-05-21 00:42

射线法一般情况思路: 从目标点出发朝x轴正方向引一条射线,计算这条射线和多边形所有边的交点数目。如果交点个数为奇数,则目标点在多边形内部;如果交点个数为偶数,则目标点在多边形外部

1 射线法原理

射线法一般情况思路:

                                        
从目标点出发朝x轴正方向引一条射线,计算这条射线和多边形所有边的交点数目。

   如果交点个数为奇数,则目标点在多边形内部;

   如果交点个数为偶数,则目标点在多边形外部
                                        
                                    

演示如下:

小白GIS

2 算法解释

全部的代码如下

                                        
function isPointInPolygon(pt, pts) {
  // 交点个数
  var counter = 0;
  // 水平射线和多边形边的交点x坐标
  var xinters;
  // 线段起点和终点
  var p1, p2;
  // for循环
  for (let i = 0; i <  pts.length; i++) {
      p1=pts[i] 
      p2 = pts[(i+1) % pts.length];// 最后一个点等于起点pts[0]
      if (pt[1] > Math.min(p1[1], p2[1]) &&pt[1] <= Math.max(p1[1], p2[1])) {
          xinters =
              (pt[1] - p1[1]) *
                  (p2[0] - p1[0]) /
                  (p2[1] - p1[1]) +
              p1[0];
          if (p1[1] == p2[1] || pt[0] <= xinters) {
              counter++;
          }
      }
  }
  if (counter % 2 == 0) {
      return false;
  } else {
      return true;
  }
}
                                        
                                    

算法中核心有两步;

                                        
以多边形的P1P2线段为例,其他的线段道理一样,遍历计算即可
1 确定P点在两条虚线中间;
2 判断P点在G点左侧或者右侧

图示如下;
                                        
                                    

小白GIS

(1) 根据y值限定范围

                                        
代码一:pt[1] > Math.min(p1[1], p2[1]) &&pt[1] <= Math.max(p1[1], p2[1])
                                        
                                    

上面代码表示:如果P点的y0值在两条虚线y1和y2内,则算法继续执行;即如果大于最大虚线或者小于最小虚线,那么过P点的射线不可能和线段有交点,直接返回false即可

(2)确定是否有交点/strong>

                                        
代码:pt[0] <= (pt[1] - p1[1]) *(p2[0] - p1[0]) /(p2[1] - p1[1]) +p1[0]
                                        
                                    

上面代码表示:计算水平射线和线段的交点x坐标;因为是朝向x轴正方向的射线,如果交点x在目标点p的右侧,即可判断有交点;count+1;

原理就是先确定P1P2的直线方程(y-y1)/(y2-y1)=(x-x1)/(x2-x1) ;然后将y=y0代入即可求出G点的x0坐标;

(3)最后验证/strong>

打开geojson.io网址

拾取如下的多边形和三个点位的坐标;用上面的函数测试

小白GIS

QQ:3410192267 | 技术支持 微信:popstarqqsmall

Copyright ©2017 xiaobaigis.com . 版权所有 鲁ICP备17027716号