フロントエンドに関連するアルゴリズムの質問を共有する-htmlチュートリアル-php.cn

フロントエンドに関連するアルゴリズムの質問を共有する

零下一度

リリース： 2017-06-24 11:59:18

オリジナル

1311 人が閲覧しました

フロントエンドに関連する興味深いアルゴリズムの質問について話しましょう。

質問:

下の写真に示すように、平面上にいくつかの不特定の形状があります。オブジェクトの数とそれぞれの異なるオブジェクトの面積を見つけるプログラムを書いてください。

分析

グラフィックの数を知りたい場合、まず考えられるのは、画像内の各ピクセルを取得し、次にピクセルの背景色 (RGBA) を決定することです。画像内のすべてのピクセルを取得したい場合は、h5 キャンバスの使用を考えることができます。
以下の通り:

初心者チュートリアルのcanvasのgetimagedataメソッド

HTMLタグの書き方。

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

ログイン後にコピー

js はキャンバスオブジェクトを取得します
```
let ctxt = canvas.getContext(&#39;2d&#39;);
```
ログイン後にコピー

js は画像オブジェクトを作成します

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

ログイン後にコピー

画像のピクセルを格納する 2 次元配列を作成します
```
let coordinates = [];for(let i=0; i<200; i++){
     coordinates[i] = [];
}
```
ログイン後にコピー

ピクセルを取得します、つまり、 getimagedata メソッドを使用します。

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

ログイン後にコピー

ピクセルを二次元配列に保存する

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++;
      }
}

ログイン後にコピー

現在のコードは次のとおりです:

(function(){
      let ctxt = canvas.getContext(&#39;2d&#39;);
      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);
      }
  })();

ログイン後にコピー

図に示すように:

次のような 2 次元配列を形成します:

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,0,0,0,0,0,0

次に、1 の連続ブロックが何個あるかを知る必要があるだけです。 2次元配列を使って絵の中の形を知り、ブロックの中に1がいくつあるか、そのブロックの面積が1の数になります。

再帰的バックトラッキングアルゴリズム

//计算连续的面积和个数
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;
}

ログイン後にコピー

詳しくない場合は、Baidu を参照してください。実際、コードには多くの情報が反映されています。

アルゴリズム、統計を使用し、結果を計算します。

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
    };
}

ログイン後にコピー

最終コード

(function(){
        let ctxt = canvas.getContext(&#39;2d&#39;);
        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;
        }
    })();

ログイン後にコピー

実行結果:

学習プロセス中に問題が発生した場合、または学習リソースを入手したい場合は、学習交換グループへの参加を歓迎します