图形选择多边形网格化

4次阅读

共计 4284 个字符，预计需要花费 11 分钟才能阅读完成。

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

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)

正文完