当前位置:秋叶网络博客 前端编程 ◊ 判断一个点是否在一个多边形区域内

判断一个点是否在一个多边形区域内

作者:秋叶 发表时间:2018年8月28日

判断一个点,或者说某个物体是否在一个多边形内,或者说是否在某个区域内,在几何算法中还是比较常见的也比较实用的,如何判断呢,这在凸多边形里面应该比较容易,但是不规则多边形就需要比较特殊的方法了。无论是凹多边形,凸多边形,长歪了的各种多边形里面都适用。
射线法判断点是否在多边形内部:

/**
   * @description 射线法判断点是否在多边形内部
   * @param {Object} p 待判断的点,格式:{ x: X坐标, y: Y坐标 }或者"170 21"
   * @param {Array} poly 多边形顶点,数组成员的格式同p: [{ x: X坐标, y: Y坐标 },{ x: X坐标, y: Y坐标 },{ x: X坐标, y: Y坐标 }]/["170 21", "170 21", "170 21"]
   * @return {String} 点 p 和多边形 poly 的几何关系
   */
  function isPointInPolygon(p, poly) {
  	if(typeof p === 'string') {
		p = {
			x: p.split(' ')[0],
			y: p.split(' ')[1]
		}
	}
    var px = p.x,
        py = p.y,
        flag = false
 
    for(var i = 0, l = poly.length, j = l - 1; i < l; j = i, i++) {
    	if(typeof poly[i] === 'string') {
		poly[i] = {
			x: poly[i].split(' ')[0],
			y: poly[i].split(' ')[1]
		}
	}
      var sx = poly[i].x,
          sy = poly[i].y,
          tx = poly[j].x,
          ty = poly[j].y
 
      // 点与多边形顶点重合
      if((sx == px && sy == py) || (tx == px && ty == py)) {
        return true;
      }
 
      // 判断线段两端点是否在射线两侧
      if((sy < py && ty >= py) || (sy >= py && ty < py)) {
         // 线段上与射线 Y 坐标相同的点的 X 坐标
         var x = sx + (py - sy) * (tx - sx) / (ty - sy)
         // 点在多边形的边上
         if(x == px) {
           return true;
         }
         // 射线穿过多边形的边界
         if(x > px) {
          flag = !flag
        }
      }
    }
 
    // 射线穿过多边形边界的次数为奇数时点在多边形内
    return flag;
  }

点与多边形的关系图解:
点与多边形的关系图解

目录: 前端编程 | 标签: , | 2443次阅读