# 射线法介绍

在地图应用上,我们会经常需要判断一个点是否位于多边形区域内,这里介绍下采用射线法如何实现。

算法思想:从待判断的点向某一个方向引射线,计算和多边形交点的个数,如果个数是偶数或者0,则点在多边形外,如果是奇数,则在多边形内,如下图: 这里有两种情况需要特殊处理:

  • 1) 射线经过顶点:当射线经过顶点时,判断就会出现异常情况。
  • 2) 点在边上:这种情况也不能用交点个数的奇偶性来判断了,要快速地判断这个点是否在边上:

GeoUtils.isPointInPolygon = (point, polygon)=> {
 if(!point || point.length<2) {
  console.error('坐标点格式错误')
  return false;
 }
 if(!polygon || polygon.length<4) {
  console.error('多边形格式错误')
  return false;
 }

 var pts = JSON.parse(JSON.stringify(polygon));
 // 下述代码来源:http://paulbourke.net/geometry/insidepoly/,进行了部分修改
 // 基本思想是利用射线法,计算射线与多边形各边的交点,如果是偶数,则点在多边形外,否则
 // 在多边形内。还会考虑一些特殊情况,如点在多边形顶点上,点在多边形边上等特殊情况。

 var boundOrVertex = true; // 如果点位于多边形的顶点或边上,也算做点在多边形内,直接返回true
 var intersectCount = 0; // cross points count of x
 var precision = 2e-10; // 浮点类型计算时候与0比较时候的容差
 var p1, p2; // neighbour bound vertices
 var p = point; // 测试点
 var N = pts.length;

 p1 = pts[0]; //left vertex 左顶点
 for (var i = 1; i <= N; ++i) { // check all rays
  if (p.lat == p1.lat && p.lng ==p1.lng) { // 如果点位于多边形的顶点或边上,也算做点在多边形内,直接返回true
   return boundOrVertex; // p is an vertex
  }

  p2 = pts[i % N]; // right vertex 右顶点
  // 如果判断点小于(p1、p2纬度最小) 或者 判断点 大于(p1、p2纬度最大) 如果全部不符合大于最小,小于最大的条件intersectCount = 0 没有处于内部
  if (p.lat < Math.min(p1.lat, p2.lat) || p.lat > Math.max(p1.lat, p2.lat)) { // ray is outside of our interests
   p1 = p2;
   continue; // next ray left point
  }

  // 如果纬度 大于最小并且小于最大,说明处于中间
  if (p.lat > Math.min(p1.lat, p2.lat) && p.lat < Math.max(p1.lat, p2.lat)) { // ray is crossing over by the algorithm (common part of)
   if (p.lng <= Math.max(p1.lng, p2.lng)) { //x is before of ray 经度小于p1、p2最大
    // 如果纬度p1、p2相等。并且 判断点 大于等于 最小的经度 (也就是说他们处于一条水平上)
    if (p1.lat == p2.lat && p.lng >= Math.min(p1.lng, p2.lng)) { // overlies on a horizontal ray
     return boundOrVertex;   
    }

    if (p1.lng == p2.lng) { // ray is vertical
     if (p1.lng == p.lng) { // overlies on a vertical ray 
      return boundOrVertex;
     } else { // before ray
      ++intersectCount;
     }
    } else { // cross point on the left side
     // (p纬度-p1纬度)*(p2经度-p1经度)/(p2纬度-p1纬度) + p1经度
     var xinters = (p.lat - p1.lat) * (p2.lng - p1.lng) / (p2.lat - p1.lat) + p1.lng; // cross point of lng
     if (Math.abs(p.lng - xinters) < precision) { // overlies on a ray
      return boundOrVertex;
     }

     if (p.lng < xinters) { // before ray
      ++intersectCount;
     }
    }
   }
  } else { // special case when ray is crossing through the vertex
   if (p.lat == p2.lat && p.lng <= p2.lng) { //p crossing over p2
    var p3 = pts[(i + 1) % N]; //next vertex
    if (p.lat >= Math.min(p1.lat, p3.lat) && p.lat <= Math.max(p1.lat, p3.lat)) { //p.lat lies between p1.lat & p3.lat
     ++intersectCount;
    } else {
     intersectCount += 2;
    }
   }
  }
  p1 = p2; //next ray left point
 }

 if (intersectCount % 2 == 0) { // 偶数在多边形外
  return false;
 } else { // 奇数在多边形内
  return true;
 }
}

参考文献