Share an algorithm question related to the front-end

Let’s talk about an algorithm question that is somewhat related to the front-end and interesting.

Title:

There are several unspecific shapes on the plane, as shown in the figure below. Please write a program to find the number of objects and the area of ​​each different object.

Analysis

If you want to know how many graphics there are, the first thing that comes to mind is to get every pixel in the picture. Click and then judge to get the background color (RGBA) of the pixel. If you want to get every pixel in the picture, you can think of using h5 canvas.
is as follows:

The getimagedata method of canvas in the novice tutorial

• Write html tags.

  <canvas id="canvas" height="200" width="350">对不你，你的浏览器不支持Canvas</canvas>

  Copy after login

• js gets the canvas object

  let ctxt = canvas.getContext('2d');

  Copy after login

• js creates the image object

  let img = new Image;
  img.src = './image.png'; //图片路径
  img.onload = function(){}  //加载成功后的执行函数，之后的代码就写在其中

  Copy after login

• Create the stored image Two-dimensional array of pixels

  let coordinates = [];for(let i=0; i<200; i++){
       coordinates[i] = [];
  }

  Copy after login

• Get the pixels, that is, use the getimagedata method.

  ctxt.drawImage(img, 0, 0);  //将图片画如canvas
  let data = ctxt.getImageData(0, 0, 350, 200).data;//读取整张图片的像素。

  Copy after login

• Save pixels into a two-dimensional array

  let x=0,y=0;  //二维数组的行和列， x：列  y：行
  for(let i =0,len = data.length; i<len;i+=4){
        let red = data[i],//红色色深
        green = data[i+1],//绿色色深
        blue = data[i+2],//蓝色色深
        alpha = data[i+3];//透明度      //把每个像素点，以二位数组的形式展开
        if(`${red} ${green} ${blue}` === &#39;210 227 199&#39;){
            coordinates[y][x] = 0;
        }else{
            coordinates[y][x] = 1;
        }
        x++;
        if(x >= 350){
            x = 0;
            y++;
        }
  }

  Copy after login

• The current code is as follows:

  (function(){
        let ctxt = canvas.getContext('2d');
        let img = new Image;
        let coordinates = [];
        let h = 200,
            w = 350;
        for(let i=0; i<200; i++){
            coordinates[i] = [];
        }
        img.src = './image.png'; //图片路径
        img.onload = function(){
            ctxt.drawImage(img, 0, 0);
            let data = ctxt.getImageData(0, 0, 350, 200).data;//读取整张图片的像素。
            let x=0,y=0;
            for(let i =0,len = data.length; i= 350){
                        x = 0;
                        y++;
                    }
                }
                console.log(coordinates);
        }
    })();

  Copy after login

• As shown in the picture:

• forms a two-dimensional array similar to the following:
  0,0,0,0,0,0,0,0,0,0,0,0

  0,0,1,1,1,0,0,0,0,0 ,0,0
  0,1,1,1,1,0,0,0,0,0,0,0
  0,1,1,1,0,0,0,1,1 ,1,1,0
  0,0,0,0,0,0,1,1,1,0,0,0
  0,0,0,0,0,0,1,1 ,1,0,0,0
  0,0,0,0,0,0,0,0,0,0,0,0
  

Then we only If you need to know how many consecutive blocks of 1 there are in the two-dimensional array, you know how many shapes there are in the picture, and how many 1's there are in the block, then the area of ​​the block is the number of 1's.

Recursive Backtracking Algorithm

//计算连续的面积和个数
const linkSum = (i,j,num)=>{//走过的路就置0
      coordinates[i][j] = 0;
      num++;      //向上
      if((i+1 < h) && coordinates[i+1][j] == 1){
        num = linkSum(i+1 , j , num);
      }      //向下
      if((j+1 < w) && coordinates[i][j+1] == 1){
        num = linkSum(i , j+1 , num);
      }      //向左
      if((i-1 >= 0) && coordinates[i-1][j] == 1){
        num = linkSum(i-1 , j , num);
      }      //向右
    if((j-1 >= 0) && coordinates[i][j-1] == 1){
        num = linkSum(i , j-1 , num);
    }

    return num;
}

Copy after login

If you are not familiar with it, just go to Baidu. I won’t go into details here. In fact, the code reflects a lot of information.

Use algorithms, statistics and calculate the results.

const getCountAndArea = () =>{let sum = [];let count = 0;for(let i = 0; i < h; i++)  //遍历二维数组
    {      for(let j = 0; j < w; j++)
      {       //连续1的个数       if(coordinates[i][j] == 1)
       {let buf = 0;  //连续1的个数
        buf = linkSum(i,j,buf);count++;  //形状的总数
        sum.push({
            index: count,   //第几个形状
            area: buf         //形状的面积
        });
       }
      }
    }return {count,
        sum
    };
}

Copy after login

The final code

(function(){
        let ctxt = canvas.getContext('2d');
        let img = new Image;
        let coordinates = [];
        let h = 200,
            w = 350;
        for(let i=0; i<200; i++){
            coordinates[i] = [];
        }
        img.src = './image.png'; //图片路径
        img.onload = function(){
            ctxt.drawImage(img, 0, 0);
            let data = ctxt.getImageData(0, 0, 350, 200).data;//读取整张图片的像素。
            let x=0,y=0;
            for(let i =0,len = data.length; i= 350){
                        x = 0;
                        y++;
                    }
                }
                // console.log(coordinates);
                let rst = getCountAndArea();
                // console.log(rst);
                console.log('个数： ' + rst.count);
                for(let i=0; i{
            let sum = [];
            let count = 0;
            for(let i = 0; i < h; i++)
            {
              for(let j = 0; j < w; j++)
              {
               //连续1的个数
               if(coordinates[i][j] == 1)
               {
                let buf = 0;
                buf = linkSum(i,j,buf);
                count++;
                sum.push({
                    index: count,
                    area: buf
                });
               }
              }
            }
            return {
                count,
                sum
            };
        }

        //计算连续的面积和个数
        const linkSum = (i,j,num)=>{
            //走过的路就置0
          coordinates[i][j] = 0;
          num++;
          //向上
          if((i+1 < h) && coordinates[i+1][j] == 1){
            num = linkSum(i+1 , j , num);
          }
          //向下
          if((j+1 < w) && coordinates[i][j+1] == 1){
            num = linkSum(i , j+1 , num);
          }
          //向左
          if((i-1 >= 0) && coordinates[i-1][j] == 1){
            num = linkSum(i-1 , j , num);
          }
          //向右
        if((j-1 >= 0) && coordinates[i][j-1] == 1){
            num = linkSum(i , j-1 , num);
        }

        return num;
        }
    })();

Copy after login

The result of the operation:

The above is the detailed content of Share an algorithm question related to the front-end. For more information, please follow other related articles on the PHP Chinese website!