判断一个点是否在一个多边形区域内
作者:秋了秋 发表时间:2018年08月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; }
点与多边形的关系图解:
9
文章作者: “秋了秋”个人博客,本站鼓励原创。
转载请注明本文地址:http://netblog.cn/blog/496.html