图形选择网格选择

50次阅读

共计 1909 个字符,预计需要花费 5 分钟才能阅读完成。

网格选择,顾名思义,就是把多边形变成网格后选择(此方法只适用于多边形,若是曲线,我们就得将其分段)。

这样,网格选择就分成了两步:
1. 将多边形分解为多个三角形。
2. 判断鼠标点是否在三角形中。

我们先从最基础的判断鼠标点是否在三角形中开始说,我们可以用鼠标点和三角形其它顶点的夹角之和来判断。

  • 点 D 在▲ABC 中:∠ADB+∠BDC+∠CDA=360°
  • 点 D 不在▲ABC 中:∠ADB+∠BDC+∠CDA<360°

接下来我们先说一下一下如何基于三个点计算夹角,如∠mon

先根据三个点画一个角:

const [m,o,n]=[new Vector2(300,50),
    new Vector2(300,200),
    new Vector2(500,200),
];

const poly=new Poly({
    stroke:true,
    vertices:[m,o,n]
});
poly.draw(ctx);

1. 把∠mon 的顶点 o 归零:

m.x-=o.x;
m.y-=o.y;
n.x-=o.x;
n.y-=o.y;

2. 根据余弦定理,可以基于点 m 乘以点 n 的点积,om 的长度乘以 on 的长度,计算∠mon 的余弦值

const dot=(m.x*n.x+m.y*n.y);
const len=Math.sqrt(m.x*m.x+m.y*m.y)*Math.sqrt(n.x*n.x+n.y*n.y);
const cosTheta=dot/len;

3. 根据反余弦方法 acos() 求∠mon,也就是下面的 theta

const theta=Math.acos(cosTheta);

Math.acos() 可以自动把根据余弦取得的弧度限制在 [0,Math.PI] 之内。
如果我们使用 Math.atan2(y,x),会得到基于 x 轴正方向的弧度,而且 y 值为负的时候,atan2(y,x) 的值也是负数,这是不适合夹角求和的。
至于这里面涉及的点积公式,这是个纯数学的知识,大家先知道其用法即可,我们后面得为它再起一章:图形选择 - 点积公式。

我们知道了一个夹角的求法之后,那就可以去求∠ADB+∠BDC+∠CDA 的夹角和了。其和若小于 360°,那就在三角之外,否则在三角之中。
我把这样的方法封装在了 Vector2d 类里:

inTriangle(p0,p1,p2){const [a0,a1,a2]=[p0.includedAngleTo(this,p1),
        p1.includedAngleTo(this,p2),
        p2.includedAngleTo(this,p0),
    ];
    const sum=a0+a1+a2;
    return Math.PI*2-sum<=0.01;
}

注:0.01 是一个用于容差的数。电脑对浮点数的运算不是绝对精确的,所以我没有直接用 Math.PI*2===sum 来做判断,而且是让鼠标点只要靠近了三角形一定范围,就算选择上了。

p1.includedAngleTo(p2,p3) 是求∠p1p2p3 的方法:

includedAngleTo(v1,v2){const [s1,s2]=[this.clone().sub(v1),
        v2.clone().sub(v1),
    ];
    return s1.includedAngle(s2);
}

p1.includedAngle(p2) 求的是角的顶点归零后夹角

includedAngle(v){return  Math.acos(this.clone().dot(v) / (this.length() * v.length()));
}

dot() 就是点积方法

dot(v) {return this.x * v.x + this.y * v.y ;}

length() 是求向量长度的方法

length() {return Math.sqrt( this.x * this.x + this.y * this.y);
}

inTriangle() 的使用方法:

const poly=new Poly({
    stroke:true,
    close:true,
    vertices:[new Vector2(50,50),
        new Vector2(450,50),
        new Vector2(250,200),
    ]
});
poly.draw(ctx);


const p=new Vector2(150,100);
ctx.beginPath();
ctx.arc(p.x,p.y,3,0,Math.PI*2);
ctx.fill();
const bool=inTriangle(p,...poly.vertices);
console.log(bool);

若上面的 bool 为 true,那就说明点在三角形中。

关于判断判断点位是否在三角形中的方法我们就说到这,下一章我们来说:图形选择 - 多边形网格化

源码地址

正文完
 0