前言

在小程序中集成电子围栏的功能，即用户进入某个区域后，必须完成相应操作才可以离开，否则会给用户告警提示，大概是这样的：

开始以为很简单，因为各大地图都有相应的api，结果发现存在问题：

比如腾讯的js api，确实提供了相应的api，但是问题就在于，它没有小程序版本的API，同时又不提供npm包，而且目前只提供在线方式加载类似这样：

1
<script src="https://map.qq.com/api/gljs?v=1.exp&key=OB4BZ-D4W3U-B7VVO-4PJWW-6TKDJ-WPB77"></script>

所以，需要自己去实现这个电子围栏算法。

射线法

引自百度百科

射线法。该法中常用水平扫描线法或垂直线法来判断一点是否在区域内。假若有一疑问点P(x，y)，要判斯它是否在多边形内，可从该疑问点向左引水平扫描线(即射线)。

计算此线段与区域边界的相交次数c。如果c为奇数，认为疑问点在多边形内；为偶数，则疑问点在多边形外。

如何理解呢？

其实，对于平面内任意闭合曲线，曲线都把平面分割成了内、外两部分。对于平面内任意一条直线，在穿越多边形边界时，有且只有两种情况：进入多边形或穿出多边形。即：

  • 如果点在多边形内部，射线第一次穿越边界一定是穿出多边形。
  • 如果点在多边形外部，射线第一次穿越边界一定是进入多边形。

由于直线可以无限延伸，而闭合曲线包围的区域是有限的，因此最后一次穿越多边形边界，一定是穿出多边形，到达外部。

由上可推断，从一点做一条射线，计算它跟多边形边界的交点个数，如果交点个数为奇数，那么点在多边形内部，否则点在多边形外部。

点斜式方程

根据上面的方法，我们只需要判断目标点的平行射线是否与边有交叉点，该交叉点是否在线段内，而非在边的延长线上

思路如下：

  1. 先判断y值是否在yi和yi+1之间

  2. 判断A值是否在xi和xi+1之间

  3. 判断A值大于还是小于x值，以此判断是左边交点，还是右边交点

  4. 左边交点nl，右边交点nr，如果满足1和2，且A值小于x值，那么左边交点nl+1,；如果满足1和2，且A值大于x值，那么右边交点nr+1

注意，如果焦点在多变形的拐点处，只算一次相交。

A值得算法，可以根据几何函数点斜式方程来计算：(yi-y)/(yi-yi+1)=(A-xi)/(xi+1-xi)，由此可知A=(y-yi)/(yi+1-yi)*(xi+1-xi)+ xi

具体代码

理论上只计算单边的奇偶数即可

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
export const isPointInPolygon = (point, points) => {
  const { lng, lat } = point;
  var iSum = 0,
    iCount;
  var dLon1, dLon2, dLat1, dLat2, dLon;
  if (points.length < 3) return false;
  iCount = points.length;
  for (var i = 0; i < iCount; i++) {
    if (i == iCount - 1) {
      dLon1 = points[i].lng;
      dLat1 = points[i].lat;
      dLon2 = points[0].lng;
      dLat2 = points[0].lat;
    } else {
      dLon1 = points[i].lng;
      dLat1 = points[i].lat;
      dLon2 = points[i + 1].lng;
      dLat2 = points[i + 1].lat;
    }
    //以下语句判断A点是否在边的两端点的水平平行线之间，在则可能有交点，开始判断交点是否在左射线上
    if (((lat >= dLat1) && (lat < dLat2)) || ((lat >= dLat2) && (lat < dLat1))) {
      if (Math.abs(dLat1 - dLat2) > 0) {
        console.log('=======================');
        //得到 A点向左射线与边的交点的x坐标：
        dLon = dLon1 - ((dLon1 - dLon2) * (dLat1 - lat)) / (dLat1 - dLat2);
        console.log(dLat1, dLon2, dLat2, dLon2, lat, lng, dLon)
        if (dLon < lng)
          iSum++;
      }
    }
  }
  if (iSum % 2 != 0)
    return true;
  return false;
}