封闭曲线检测

近期开发需求上有这么一个功能,用户自己通过画圈去查找物品。效果如下:

test.gif

那么问题来了,如何判断用户画的是一个封闭的曲线?

area.png

从图上可知

1. 封闭曲线必然会存在至少一个交点,并且该交叉点是由尾部曲线回到起始点或穿过前面的曲线形成。
2. 交叉点在X轴和y轴上与曲线上的点都应存在距离。(排除曲线由起点到终点,再由终点回到起点。这种情况存在交叉点但它是一条直线)

function getClosedCurvePoints(points){
  let intersectPArray = [];
  var isLine = true;
  for(var i=0; i<points.length; i++){
    let p = points[i];
    for(var j=points.length-1; j>=0; j--){
      if((j - i) < points.length / 2) continue;
      let eP = points[j];
      let xDis = p.x - eP.x;
      let yDis = p.y - eP.y;
      let dis = Math.sqrt(Math.pow(xDis,2) + Math.pow(yDis,2));

      if(Math.abs(xDis) >= 20 && Math.abs(yDis) >= 20){
        isLine = false;
      }

      if(dis <= this._maxDis){//dis=0才是真正有交叉点的情况,但是用户不一定每次都能画出完美存在交叉点的圈 这种情况下应给予一个合理的误差值
        // console.log("存在相交点",p);
        // console.log("i="+i+",j="+j);
        intersectPArray.push({
          p: p,
          dis: dis,
          leftIdx: i,
          rightIdx: j
        });
      }
    }
}

得到交叉点后,下一步则是获取封闭曲线上的点(存在多交叉点的情况不做分析)

area2.png

情况1: 可直接把所有的点都认为是封闭曲线上的点

情况2: 需去除交叉点下方的2条曲线的点

废话不多说,上代码i,j所在的区间就是封闭曲线上的点

function getClosedCurvePoints(points){
  let intersectPArray = [];
  var isLine = true;
  for(var i=0; i<points.length; i++){
    let p = points[i];
    for(var j=points.length-1; j>=0; j--){
      if((j - i) < points.length / 2) continue;
      let eP = points[j];
      let xDis = p.x - eP.x;
      let yDis = p.y - eP.y;
      let dis = Math.sqrt(Math.pow(xDis,2) + Math.pow(yDis,2));

      if(Math.abs(xDis) >= 20 && Math.abs(yDis) >= 20){
        isLine = false;
      }

      if(dis <= this._maxDis){//dis=0才是真正有交叉点的情况,但是用户不一定每次都能画出完美存在交叉点的圈 这种情况下应给予一个合理的误差值
        // console.log("存在相交点",p);
        // console.log("i="+i+",j="+j);
        intersectPArray.push({
          p: p,
          dis: dis,
          leftIdx: i,
          rightIdx: j
        });
      }
    }
  }

  if(isLine){
    console.log("绘制的是直线");
    return null;
  }
  if(intersectPArray.length == 0){
    console.log("不存在交叉点");
    return null;
  }

  intersectPArray.sort((a,b)=>{return a.dis - b.dis});
  let intersectP = intersectPArray[0];
  if(intersectP.leftIdx < intersectP.rightIdx){
    return points.slice(intersectP.leftIdx,intersectP.rightIdx + 1);
  }else{
    return points.slice(intersectP.rightIdx,intersectP.leftIdx + 1);
  }
}

获取到封闭曲线上的点后,我们可以通过这些点得到封闭曲线的外接矩形,通过判断物品是否在该矩形内判断用户是否圈中物品。

获取封闭曲线在X轴上最左、最右的点和Y轴上最下、最上的点所形成的矩形则为封闭曲线的外接矩形

QQ图片20220401164028.jpg

    function getBoundRect(){
      let minX = points[0].x;
      let maxX = points[0].x;
      let minY = points[0].y;
      let maxY = points[0].y;

      for(var i=1; i<points.length; i++){
        let p = points[i];
        if(p.x > maxX){
          maxX = p.x
        }
        if(p.x < minX){
          minX = p.x
        }
        if(p.y > maxY){
          maxY = p.y
        }
        if(p.y < minY){
          minY = p.y
        }
      }

      return {l:minX,t:minY,r:maxX,b:maxY};
    }

优化

由于判断物品是否在闭合曲线内是采用闭合曲线的外接矩形去判断的,那么如何减小框选区域误差值则可转换成如何计算闭合曲线的最小外接矩形,我们知道在旋转不同角度下得到的最大外接矩形的面积是不一样的,当闭合曲线与X轴或Y轴垂直时,此时的外接矩形应为最小外接矩形。如下图:

QQ截图20220402142727.png

由于闭合曲线是无规律的图形所以很难去计算它是否处于水平或垂直状态,但经过0-90度旋转后必然会出现水平或垂直状态,此时它的外接矩形面积最小。计算步骤如下:

1. 计算重心(锚点)

2. 以锚点为中心旋转0-90计算外接矩形面积,筛选出面积最小的外接矩形,并记录下当前旋转的角度θ

3. 以锚点为中心反向旋转θ度,得到最小外接矩形

  function getBoundRect(){
    let anchorP = ShapeHepler.calcAnchorPoint(closedCurvePoints); //计算锚点, 锚点=(avgX,avgY)

    //计算0-90度下所有外接矩形,并获取面积最小的矩形,该矩形则为外接最小矩形
    let minBoundRectWrap = {}
    for(var i=0; i<90; i++){
      let rotatePS = [];
      let angle = i * Math.PI/180; //弧度制
      closedCurvePoints.forEach(p=>{
        var rP = ShapeHepler.rotatePoint(p, anchorP, angle);
        rotatePS.push(rP);
      });
      let boundRect = ShapeHepler.getBoundRect(rotatePS);
      let area = (boundRect.r - boundRect.l) * (boundRect.b - boundRect.t);

      if(!minBoundRectWrap.area || minBoundRectWrap.area > area){
        minBoundRectWrap = {
          rect: boundRect,
          angle: angle,
          anchorP: anchorP,
          area: (boundRect.r - boundRect.l) * (boundRect.b - boundRect.t)
        }
      }
    }

    //将外接最小矩形逆时针旋转回去
    let rotateMinRectPS = [];
    [
      {x: minBoundRectWrap.rect.l,y: minBoundRectWrap.rect.t},
      {x: minBoundRectWrap.rect.r,y: minBoundRectWrap.rect.b},
    ].forEach(p=>{
      let rP = ShapeHepler.rotatePoint(p, anchorP, -minBoundRectWrap.angle);
      rotateMinRectPS.push(rP);
    });

    return {
      l: rotateMinRectPS[0].x,
      t: rotateMinRectPS[0].y, 
      r: rotateMinRectPS[1].x, 
      b: rotateMinRectPS[1].y,
      angle: minBoundRectWrap.angle,
      anchorP: anchorP
    }
  }

注意:在判断点P是否在闭合曲线的外接矩形内时,要先判断是否有发生旋转,有的话需要把点P和外接矩形以锚点为中心旋转后再判断

测试效果如下:

QQ截图20220402110114.png