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

这样,网格选择就分成了两步:
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,那就说明点在三角形中。

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

源码地址