乐趣区

图形选择多边形网格化

在说多边形网格化之前,我们先画个复杂点的多边形出来。
准备一组用于逆时针绘图的顶点:

const points=[new Vector2(0,0),
    new Vector2(0,600),
    new Vector2(600,600),
    new Vector2(600,200),
    new Vector2(200,200),
    new Vector2(200,400),
    new Vector2(300,400),
    new Vector2(300,300),
    new Vector2(500,300),
    new Vector2(500,500),
    new Vector2(100,500),
    new Vector2(100,100),
    new Vector2(600,100),
    new Vector2(600,0)
];

基于这组顶点绘制一个多边形:

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

思路解析

接下来,我们就说一下网格化思路:
1. 先判断 points 中的顶点数量,若等于 3,那就直接将这三个点存储起来。否则,下一步。
2. 把多边形里的第一个点作为起点

3. 从起点连接下下个点,构成一个三角形,如▲012

4. 对上面的三角形做两个判断:

  • 三角形是否包含了其它顶点,如上图▲012
  • 三角形是否为凹三角形,如下图▲678

若出现上面任何一种情况,就把起点的下一个点做为起点,执行第 1 步。
若上面的情况都不存在,如下图▲456,那就把构成这个三角形的顶点存储起来,把下一个点从 points 中删除,把下下个点做为起点,执行第 1 步。

到这里,网格化的思路就说完了,这是一个递归方法,最终效果如下:

接下来,咱们就说一下这整个逻辑中涉及的两个知识点:
1. 三角形是否包含了其它顶点。
这个方法我们上一章说过,遍历其它顶点,逐一判断即可,在此便不再赘述。
2. 判断三角形的凹凸。
首先我们在定点的时候要遵守一个规则,这里是逆时针定点。
这样我们在用叉乘的方法求三角形的面积的时候,面积为正,那就是凹三角形;面积为负,那就是凸三角形。
求三角形面积的方法:

function triangleArea(p0,p1,p2){const [bx,by,cx,cy]=[
        p1.x-p0.x,
        p1.y-p0.y,
        p2.x-p0.x,
        p2.y-p0.y,
    ];
    return (bx*cy-cx*by)/2;
}

这个求面积方法用到的是一个叉乘算法。利用这个算法还可以计算任意边数的多边形面积,详情我写过的另一篇文章:多边形面积

整体代码的实现步骤

1. 绘制多边形

const points=[new Vector2(0,0),
    new Vector2(0,600),
    new Vector2(600,600),
    new Vector2(600,200),
    new Vector2(200,200),
    new Vector2(200,400),
    new Vector2(300,400),
    new Vector2(300,300),
    new Vector2(500,300),
    new Vector2(500,500),
    new Vector2(100,500),
    new Vector2(100,100),
    new Vector2(600,100),
    new Vector2(600,0)
];
const poly=new Poly({position:new Vector2(50,50),
    stroke:true,
    close:true,
    lineWidth:2,
    vertices:[...points]
});
poly.draw(ctx);

2. 声明用于存储三角形的数组 triangles[] 和起点

const triangles=[];
let start=0;

3. 建立网格

crtMesh(start);

function crtMesh(start){
    const len=points.length;
    const [i0,i1,i2]=[
        start%len,
        (start+1)%len,
        (start+2)%len
    ];
    const [p0,p1,p2]=[points[i0],
        points[i1],
        points[i2],
    ];
    if(len===3){triangles.push([p0,p1,p2]);
    }else{const area=triangleArea(p0,p1,p2);
        if(area>=0||hasOtherPointInTriangle(p0,p1,p2)){
            // 凹三角
            crtMesh(i1);
        }else{
            // 凸三角
            triangles.push([p0,p1,p2]);
            points.splice(i1,1);
            crtMesh(i1);
        }
    }
}

len 是 points 顶点长度
i0,i1,i2 是通过取余的方法获取三角形顶点的索引,因为网格化可能会对 points 循环遍历。
len===3 是如果 points 长度为三,就直接将三角形顶点放到 triangles 集合里,这也是个终止递归的条件,后面 points 会不断删除三角形的第 2 个顶点,从而不断变小。
area>=0||hasOtherPointInTriangle(p0,p1,p2) 便是思路 4 中的两个情况:

  • 若满足其中之一,就把下一个顶点作为参数,递归执行 crtMesh(i1) 方法。
  • 若都不满足,就存储三角形,冲 points 中删除三角形的第二个顶点,将三角形的第二个顶点作为起点参数,执行 crtMesh(i1) 方法。

好了,整个网格化的实现过程就是这样。
要选择多边形的话,那就遍历 triangles 里的三角形即可,鼠标点只要在一个三角形中,那也就在多边形中了。

最后我把上面的过程进行了封装,建立了一个 Mesh 类:

/*Mesh 网格对象
*   points 所有的顶点
*   triangles 三角形集合
*   tmpPoints 顶点的暂存区,用于做递归删除
*   update() 更新方法,建立网格
*   crtMesh(start) 建立网格的方法
*   hasOtherPointInTriangle(p0,p1,p2) 判断▲p0p1p2 是否包含了其它顶点
*   triangleArea(p0,p1,p2) ▲p0p1p2 的面积
*   inMesh(v) 点 v 是否在多边形中
*   crtPolys() 根据三角形集合建立多边形集合
*   draw(ctx) 绘图
* */
export default class Mesh{constructor(points=[]) {
        this.points=points;
        this.triangles=[];
        this.tmpPoints=[];
        this.update();}
    update(){this.tmpPoints=[...this.points];
        this.crtMesh(0);
    }
    crtMesh(start){
        const points=this.tmpPoints;
        const len=points.length;

        const [i0,i1,i2]=[
            start%len,
            (start+1)%len,
            (start+2)%len
        ];
        const [p0,p1,p2]=[points[i0],
            points[i1],
            points[i2],
        ];
        if(points.length===3){this.triangles.push([p0,p1,p2]);
        }else{const area=this.triangleArea(p0,p1,p2);
            if(area>=0||this.hasOtherPointInTriangle(p0,p1,p2)){
                // 凹三角
                this.crtMesh(i1);
            }else{
                // 凸三角
                this.triangles.push([p0,p1,p2]);
                points.splice(i1,1);
                this.crtMesh(i1);
            }
        }
    }
    hasOtherPointInTriangle(p0,p1,p2){for (let ele of this.tmpPoints){if(ele!==p0&&ele!==p1&&ele!==p2){if (ele.inTriangle(p0,p1,p2)){return true;}
            }
        }
        return false;
    }
    triangleArea(p0,p1,p2){const [bx,by,cx,cy]=[
            p1.x-p0.x,
            p1.y-p0.y,
            p2.x-p0.x,
            p2.y-p0.y,
        ];
        return (bx*cy-cx*by)/2;
    }
    inMesh(v){
        const len=this.triangles.length;
        for(let ind=0;ind<len;ind++){const triangle=this.triangles[ind];
            if(v.inTriangle(...triangle)){return {ind,triangle};
            }
        }
        return null;
    }
    crtPolys(option){this.triangles.forEach((ele,ind)=>{
            option.vertices=ele;
            const poly=new Poly(option);
            this.polys.push(poly);
        });
    }
    draw(ctx){this.polys.forEach((poly,ind)=>{poly.draw(ctx);
        })
    } 
}

网格实例化和绘制方法:

const mesh=new Mesh(points);
mesh.crtPolys({position:new Vector2(50,50),
    stroke:true,
    close:true,
});
mesh.draw(ctx);

图形选择方法:

canvas.addEventListener('mousemove',mousemoveFn);
let hover=false;
function mousemoveFn(event){const mousePos=getMousePos(event,poly);
    const obj=mesh.inMesh(mousePos);
    const bool=!!obj;
    if(hover!==bool){
        poly.fill=bool;
        ctx.clearRect(0,0,canvas.width,canvas.height);
        poly.draw(ctx);
        mesh.draw(ctx);
        hover=bool;
    }
}

效果:

[源码地址](https://github.com/buglas/interview-01)

退出移动版