highlight: a11y-dark

近期，有接手到一个echarts地图图表项目，因为采集的散点数据很多打不到准确的地图点上，故有了这个问题。

一般而言，标题的两个问题其是同一个问题，因为对与一个地图数据，也就是geoJson来说，其实就是一个有很多个点的多边形。

目前来说判断点是否在一个多边形内，江湖上流传的主要方法有射线法，面积法，叉积(凸多边形)等等很多方法。但就笔者看各种技术文章，以及多方探(bai)索(du)研究（google）的情况下来看，射线法是比较常用的一种，基于射线法又派生出奇偶规则（Odd-even Rule）和非零环绕数规则（Nonzero Winding Number Rule）。

全文可能就只会用到一个数学公式直线方程的两点式:

\(\frac{y-y2}{y1-y2} = \frac{x-x2}{x1-x2}\)

射线法

基本思想：所谓射线法，就是指，从被测点引出一条射线，而后判断与多边形的交点。与边的交点的个数决定了当前点是否在多边形内，这是奇偶规则与非零环绕数规则的共同点，两者的不同点在于是否考虑被交边的方向以及对点的交点个数的判断。

`奇偶规则（Odd-even Rule）`

所谓奇偶规则是指，若交点数为奇数则点在多边形内，否则点在多边形外。

图示:

代码示例

/**
 * 
 * @param {*} param0 [number,number]
 * @param {*} points [number,number][]
 * @returns 
 */
function oddEvenRule([x,y], points) {

  let ans = false;
  if (points.length < 3) {
    return ans;
  }

  for (let i = 0, L = points.length - 1; i < L; i++ ) {
    const point1 = points[i];
    const point2 = points[i+1]

    const [x1, y1] = point1;
    const [x2, y2] = point2;

    if (y < Math.min(y1, y2) || y > Math.max(y1, y2)) { // 限定 y 在  y1 及y2之间
      continue;
    }
    // 在 point1及point2确定的直线上，根据待测点的y，求出交点坐标x
    // 直线方程。两点式(y-y2)/(y1-y2) = (x-x2)/(x1-x2)
    let crossoverX = (y - y2) * (x1 - x2) /(y1 - y2) + x2;
    if (y1 === y2) { // 水平边的交点即为待测点的坐标 暂时先不管了 感兴趣可以自己处理一下
      // crossoverX = x;
      continue;
    }
    if (crossoverX > x) { // 只考虑一个方向
      ans = !ans; 
    }

  }

  return ans;
    
}

判断一般的多边形，奇偶规则判断就够了，但是奇偶规则有个限制，就是一个多边形有多部分构成的时候，考虑如下场景：

此时再使用奇偶规则去判断就不能准确判断了，由此引出下面一个方法：

`非零环绕数规则（Nonzero Winding Number Rule）`

所谓非零环绕，是指，基于射线法，当射线穿过多边形边的时候，根据多边形边的方向，给总的交点数加1或者减1，最后判断总的节点数是不是0，不是0则为多边形内部，否则就是多边形外部。

图示:

可以看到非零环绕规则很好的解决了上边的问题

代码示例

这里援引一下zRender的contain源码

var EPSILON = 1e-8;
function isAroundEqual(a, b) {
    return Math.abs(a - b) < EPSILON;
}
function contain(points, x, y) {
    var w = 0;
    var p = points[0];
    if (!p) {
        return false;
    }
    for (var i = 1; i < points.length; i++) {
        var p2 = points[i];
        w += windingLine(p[0], p[1], p2[0], p2[1], x, y);
        p = p2;
    }
    // Close polygon
    var p0 = points[0];
    if (!isAroundEqual(p[0], p0[0]) || !isAroundEqual(p[1], p0[1])) {
        w += windingLine(p[0], p[1], p0[0], p0[1], x, y);
    }
    return w !== 0;
}
function windingLine(x0, y0, x1, y1, x, y) {
    if ((y > y0 && y > y1) || (y < y0 && y < y1)) {
        return 0;
    }
    // Ignore horizontal line
    if (y1 === y0) {
        return 0;
    }
    var t = (y - y0) / (y1 - y0);
    var dir = y1 < y0 ? 1 : -1;
    // Avoid winding error when intersection point is the connect point of two line of polygon
    if (t === 1 || t === 0) {
        dir = y1 < y0 ? 0.5 : -0.5;
    }
    var x_ = t * (x1 - x0) + x0;
    // If (x, y) on the line, considered as "contain".
    return x_ === x ? Infinity : x_ > x ? dir : 0;
}