Canvas有透明图像轮廓查找——Marching Squares算法

效果如下：

实现思路

1. 找到一个在图片边缘上的像素(此步骤与算法无关)，会从这个像素开始分析
2. 考虑一个2×2像素正方形，它包含当前像素，通常位于正方形的左上角或右下角
3. 此时，您有4个像素，每个像素都可以是透明的或不透明的。所以我们将有16个可能的2×2正方形，尽管所有透明像素或所有不透明像素的情况永远不会发生，因为我们在图像边缘周围移动。
4. 根据2×2正方形中不透明像素的数量和位置，我们可以猜测轮廓的方向，沿着该方向移动当前像素，并从步骤2继续，直到再次到达步骤1中找到的像素

如何找到第一个像素（步骤一中的像素）

我们需要逐像素扫描图像，直到我们找到一个不透明的像素。

 function getFirstNonTransparentPixelTopDown(canvas){
    var context = canvas.getContext("2d");
    var y, i, rowData;
    for(y = 0; y < canvas.height; y++){
        rowData = context.getImageData(0, y, canvas.width, 1).data;
        for(i=0; i<rowData.length; i+=4){
            if(rowData[i+3] > 0){
                return {x : i/4, y : y};
            }
        }
    }
    return null;
};

完整代码见：MarchingSquaresJS
此方法查找出的轮廓，只包含最外部的，如果图片中间有透明部分不会查找出来。如果图片中间透明部分也查找出来，可以参考另一个包MarchingSquares

这个使用的时候会稍微复杂一些，需要手动获取imageData, 并根据像素是否透明转换为0和1，然后将数据传入获取最终路径。使用代码参考下面代码

function runMarchingSquares(){
            var sourceCanvas = document.createElement("canvas");
            sourceCanvas.width = canvas.width + 0;
            sourceCanvas.height = canvas.height + 0;
            sourceContext = sourceCanvas.getContext("2d");
            sourceContext.drawImage(canvas,1,1);

            let context = sourceContext;
            var y, i, rowData;
            var result = []
            for(y = 0; y < sourceCanvas.height; y++){
                rowData = context.getImageData(0, y, sourceCanvas.width, 1).data;
                var rowResult = [];
                for(i=0; i<rowData.length; i+=4){
                    rowResult.push(rowData[i+3] > 0?1:0)
                }
                result.push(rowResult)
            }
            const outlinePoints = MarchingSquaresJS .isoLines(result,  0.5, { linearRing: true })
            renderOutline(outlinePoints)
        }
        function renderOutline(outlinePoints){
            context.strokeStyle = "red";
            context.lineWidth = 2;
            outlinePoints.forEach(points => {
                context.beginPath();
                let last;
                points.forEach(([x,y]) => {
                    if(!last){
                        context.moveTo(x, y);
                    } else {
                        context.lineTo(x, y);
                    }
                    last = x+y;
                });
                context.stroke();
            });
        }

此库使用时，传入参数和输出结构都是二维数组，从上面代码能看出，我传入的参数每行数据是一组数据。它的输出结果是imageData的最外层，可根据情况自行处理。

不足

边缘不够平滑，待改进

优化方向

如果路径过多，会导致绘制时间长，可以使用路径简化算法减少路径点，可参考下面链接，第一篇文章有Ramer–Douglas–Peucker algorithm与Douglas-Peucker两种算法的对比;第二篇提供了实现，可以直接测试。

Line simplification algorithms

Ramer-Douglas-Peucker algorithm

参考

Marching Squares

Metaballs and Marching Squares

原文链接：https://juejin.cn/post/7350124562482135055 作者：青蛙眼罩