前言 📝

射线法即从P点引出一条射线，看这条射线和多边形相交的次数。假如P点在多边形外，那么P点射线和多边形相交情况一定是：穿入 -> …(中间可能有N次穿入穿出)… ->穿出，即穿入穿出的次数是偶数次，交点是偶数个。假如P点在多边形内，那么P点射线和多边形相交的情况一定是:穿出 -> …（后面可能有N次穿入穿出）…，总之最后一定是穿出，交点是奇数个。是不是不明白，懵逼的你和我一起看一下图。

本网站的图片截图于：https://blog.csdn.net/qq_23447231/article/details/121920282

1. 一般情况

1.1 P点在多边形外

image.png

结论： 要么一个相交点也没有，要么是双数个

1.2 P点在多边形内

image.png

结论：相交点总共是1个或者奇数个

2. 特殊情况（不考虑）

因为所有方向的射线都是一样的，所以为了分析方便，我们使用从P点开始的一条水平线作为射线来分析。 然而还有特殊情况：

2.1 P点在多边形顶点

image.png

2.2 P点和多边形的交点是顶点

image.png

2.3 P点在多边形线段上

image.png

2.4 P点的射线刚好经过多边形的一条边

image.png

2.5 P点的射线刚好经过多边形一条边，并且P点在这条边上

image.png

3. 编程思路

如果我们采用左射线的方法，那是不是直接相反，当交叉数量是奇数的时候，说明我们的点在多边形内。反之则在外面。
为什么要采用左射线的方法呢，我感觉容易理解一点。我们先看一下思路，我们采用左射线的情况思路：
我们先一条线一条线的判断，比如说我们的(x1,y1),(x2,y2)组成的一条线，如果说我们的P点不在两个点之间，则不可能会有交点。继续判断下一条边。如果说在中间的情况下，P点的左射线可能会和我们的线段有交点。然后我们可以利用几何方法得到P点的水平直线与该边交点的x坐标。然后判断交点的X坐标是在P点的左侧还是右侧。左侧则相交数量+1，右侧则继续判断下一条线段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
function IsPtInPoly(aLat, aLon, pointList) {
  /* 
  :param aLon: double 经度 
  :param aLat: double 纬度 
  :param pointList: list [{latitude: 22.22, longitude: 113.113}...] 多边形点的顺序需根据顺时针或逆时针，不能乱 
  */
  var iSum = 0  
  // 坐标点的个数
  var iCount = pointList.length

  // 两点一线，三点一面。如果小于三个点直接返回false
  if(iCount < 3) {
      return false 
  }
  //  待判断的点(x, y) 为已知值
  var y = aLat
  var x = aLon
  for(var i = 0; i < iCount; i++) {
      var y1 = pointList[i].latitude  
      var x1 = pointList[i].longitude
      
      if(i == iCount - 1) {
	      // 最后一圈，这是一个闭环的图形，最后收尾的一定是起点坐标
          var y2 = pointList[0].latitude
          var x2 = pointList[0].longitude
      } else {
	      // 当前坐标的下一个相邻的坐标 
          var y2 = pointList[i + 1].latitude  
          var x2 = pointList[i + 1].longitude
      }
      
      // 当前边的 2 个端点分别为 已知值(x1, y1), (x2, y2)
      // ((y >= y1) && (y < y2)成立说明y2在y1上面，p点的纵坐标（y）在y2和y1之间，或者在y1上
      // ((y >= y2) && (y < y1))成立说明y2在y1下面，p点的纵坐标（y）在y2和y1之间，或者在y2上
      // 主要目的是查看当前的p点纵坐标是否在某个相邻的两个点之间
      if (((y >= y1) && (y < y2)) || ((y >= y2) && (y < y1))) {
          //  y 界于 y1 和 y2 之间
          //  假设过待判断点(x, y)的水平直线和当前边的交点为(x_intersect, y_intersect)，有y_intersect = y（具体看下图）
          // 则有（2个相似三角形，公用顶角，宽/宽 = 高/高）：|x1 - x2| / |x1 - x_intersect| = |y1 - y2| / |y1 - y|
          if (Math.abs(y1 - y2) > 0) {
              var x_intersect = x1 - ((x1 - x2) * (y1 - y)) / (y1 - y2);  
              // 判断焦点是否在P点的左边
              if(x_intersect < x) {
                  iSum += 1 
              }
          }
      } 
  }
  if(iSum % 2 != 0) {
      return true  
  }else {
      return false 
  }  
}
module.exports = {
  IsPtInPoly: IsPtInPoly,
};

image.png