ホーム > カテゴリ > 数学・アルゴリズム >

塗りつぶしのアルゴリズム[ペイント系]

ペイント系アプリなどで使用される指定した色でキャンバスを塗りつぶす「塗りつぶし」のアルゴリズムです。アルゴリズムの解説だけではなく、実際にこのページで塗りつぶしを体験できますのでロジックが理解しやすいと思います。

「塗りつぶし」の機能があるペイント系アプリは、国内では100本も発表されていないと思いますが、いざ作ろうと思うと、アルゴリズムとテスト作業に数時間はかかってしまうと思いますので、どなたかのお役になれば幸いです。

記事の後半にはJavaScriptによるサンプルプログラムがあります。時間がない方は先にそちらを参照すると良いです。

塗りつぶしの体験

この16x16のキャンバスで「塗りつぶし」を体験できます。

ペンは点を描画します。マウスボタンを押しながらマウスを移動すると連続して描画可能です。「ペン」「塗りつぶし」や「色」を変更しながら試してみてください。

このドット絵用のキャンバスは私が作成したブラウザで動作する「アイコンエディタ」の試作品となっています。このキャンバスは「DIV」で作成されていますが、アイコンエディタの方は高速化の為にHTML5のcanvasを使用しています。

アルゴリズム

塗りつぶしのアルゴリズムは言葉にすると次のようになります。

マウスダウンした座標から上下左右に走査して他の色にぶつかるまで続けます。その次に1回目の走査で取得した「塗りつぶす座標」を元に再度、上下左右に走査します。これを「塗りつぶす座標」分、繰り返し行います。

他にも手法はあると思いますが、私はこのロジックにしました。速度もそんなに遅くはないと思います。※JavascriptのDIVエレメントの操作は遅いで注意してください。

[1回目の走査図]

1回目の走査ではマウスダウンをした座標を除く上下左右に塗りつぶされているのがわかりますね。2回目以降はこの黒色の座標(塗りつぶす座標)を元に上下左右に走査します。そして、再度、取得した「塗りつぶす座標」を元に繰り返し走査を行います。

サンプルプログラム

最初の「塗りつぶしの体験」と同じコードとなります。粗雑なコードが12kぐらいありますので各パーツ毎に分けて記載します。

※JavaScriptはHTMLの<head></head>の中に入れてください。

HTML

<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<style>
#PaletteArea table{
  margin: 12px 8px 0 18px;
  border-collapse: collapse;
}

#PaletteArea table td{
  padding:1px;
  border:0px;
}

#CanvasArea table{
  margin: 12px 8px 0 18px;  
  border: 3px solid #1e90ff;  
  border-collapse: collapse;
}

#CanvasArea table td{
  padding:0px;
  border:1px dotted #1e90ff;
}
</style>
</head>
<body>

<div style="margin: 12px 8px 0 18px;">
  <input type="radio" name="mode" value="1" id="type1" checked="checked" onclick="canvas_penmode_flg=1;">
  <label for="type1" onclick="canvas_penmode_flg=1;">ペン</label>
  <input type="radio" name="mode" value="2" id="type2" onclick="canvas_penmode_flg=2;">
  <label for="type2" onclick="canvas_penmode_flg=2;">塗りつぶし</label>  
  <button onclick="createCanvasArea();">クリア</button>
</div>
<p id="PaletteArea"></p>
<p id="CanvasArea"></p>

</body>  
</html>

JavaScript - グローバル変数

<script>
  var canvas_mousedown_flg = 0;   // マウスダウンフラグ
  var canvas_penmode_flg   = 1;   // 1:ペン 2;塗りつぶし
  var canvas_block = new Object;  // 連想配列のピクセルデータ
  var canvas_data  = new Array(); // 配列のピクセルデータ
  
  var canvas_width  = 16; // キャンバスの横幅
  var canvas_height = 16; // キャンバスの縦幅
  
  var palette_select_id = 'H1xW1'; // パレットの選択ID
  
  var COLOR_BACK = '#FFFFFF'; // 背景色  
  
  // 基本16色パレット
  var PALETTE = ["#000000","#ffffff","#c0c0c0","#808080","#ff0000",
                 "#ffff00","#00ff00","#00ffff","#0000ff","#ff00ff",
                 "#800000","#808000","#008000","#008080","#000080",
                 "#800080"];                  
</script>

JavaScript - HTMLの生成

<script>
  // キャンバスの作成(ドット絵用)
  function createCanvasArea(){
    var html = '';
      
    // テーブルの枠を選択した際にその下にあるセルを擬似的に選択
    // 最後に「return false」にする事によってエレメントのドロップを解除 
    html += '<table id="tbl_canvas" ';  
    html += ' onmousedown="OnMousedown(document.elementFromPoint(event.clientX,event.clientY+1),null);return false;">';

      // マスの作成
      var key;
      canvas_block = new Object;
      for (var i = 0; i < canvas_height; i++) {
        html += '<tr>';     
        for (var j = 0;j < canvas_width; j++) {
          key =  'R' + (i+1) +'xC'+(j+1);
          
          html += '<td>';
            html += '<div id="' + key + '"';
              html += ' style="width:18px;height:18px;background-color:' + COLOR_BACK + '"';
              html += ' onmousemove="OnMousemove(this,event);"';
              html += ' onmouseup="OnMouseup(event);"';
            html += '></div>';
          html += '</td>';
          
          canvas_block[key] = Color2RGB(COLOR_BACK);
        }
        html += '</tr>';
      }
      
    html += '</table>';
    html += '<p></p>'
    
    document.getElementById('CanvasArea').innerHTML = html;
    
    // ピクセルデータの保存
    OnMouseup();
  }
  
  // パレットエリアの作成
  function craetePaletteArea() {
    var html = '';

    html  = '<table> ';
      var cnt = 0;
      for (var i = 0; i < 1; i++) {
        html += '<tr>';         
          for (var j = 0;j < 16; j++) {                  
            html += '<td>';
              html += '<div style="width:15px;height:15px;">' ;
                html += '<div id="H' + (i+1) +'xW'+(j+1) +'" onmousedown="OnPalette_Mousedown(this,event);"';
                  html += ' style="width:13px;height:13px;background-color:';
                
                  html += PALETTE[cnt++] + ';';
                
                  if (palette_select_id == ('H' + (i+1) +'xW'+(j+1)))
                    html += 'border:2px solid #1e90ff;"';
                  else
                    html += '"';
                   
                html += '></div>';
              html +='</div>';
            html += '</td>';                
          }
        html += '</tr>';
      }
    html += '</table>';   
    html += '<p></p>';

    document.getElementById('PaletteArea').innerHTML = html;       
  } 
</script>

JavaScript - 内部関数

<script>
  // 塗りつぶす座標を取得する
  // x,y          : マウスダウンした座標
  // targetcolor  : 塗りつぶす色 
  // imgdata      : ピクセルデータ(R,G,B)
  // fill_list    : 塗りつぶす座標のリスト(戻り値)  
  // already_list : 走査済みの座標のリスト
  // 備考
  //   1回目はベースのx,y座標を除く十字型になる
  //   2回目以降は新規座標を元に再帰処理
  function getFillList(x,y,targetcolor,imgdata,fill_list,already_list){
    var newlist = new Array();
    var index;
    
       function AddNewList(ax,ay){
        if(fill_list['R'+ay +'xC'+ax] == 1){
          // none
        }else{
          fill_list['R'+ay +'xC'+ax] = 1;
          newlist[newlist.length] = {'x':ax,'y':ay};
        }
       }

    // 左
    for (var i = x; i >= 1; i--) {
      
      // ベース座標は除外
      if (i == x) continue   
      
      // 既に走査済みは除外
      if (already_list[(i-1) +((y-1)*canvas_width)] == 1) break;    
      already_list[(i-1) +((y-1)*canvas_width)] = 1;
      
      // 他の色にぶつかるまでループ
      index = (y-1) * canvas_width + (i-1);
      if (!(imgdata[index].r == targetcolor.r &&
            imgdata[index].g == targetcolor.g &&
            imgdata[index].b == targetcolor.b)){
        break;
      }
      
      AddNewList(i,y);
    } 
      
    // 右
    for (var i = x; i <= canvas_width; i++) {
      
      if (i == x) continue
           
      if (already_list[(i-1) +((y-1)*canvas_width)] == 1) break;    
      already_list[(i-1) +((y-1)*canvas_width)] = 1;
           
      index = (y-1) * canvas_width + (i-1);     
      if (!(imgdata[index].r == targetcolor.r &&
            imgdata[index].g == targetcolor.g &&
            imgdata[index].b == targetcolor.b)){
        break;
      }      
      AddNewList(i,y);
    }
    
    // 上
    for (var i = y; i >= 1; i--) {
      
      if (i == y) continue
           
      if (already_list[(x-1) +((i-1)*canvas_width)] == 1) break;    
      already_list[(x-1) +((i-1)*canvas_width)] = 1;
               
      index = (i-1) * canvas_width + (x-1);         
      if (!(imgdata[index].r == targetcolor.r &&
            imgdata[index].g == targetcolor.g &&
            imgdata[index].b == targetcolor.b)){
        break;
      }     
      AddNewList(x,i);
    }
    
    // 下
    for (var i = y; i <= canvas_height; i++) {
      
      if (i == y) continue         
      
      if (already_list[(x-1) +((i-1)*canvas_width)] == 1) break;    
      already_list[(x-1) +((i-1)*canvas_width)] = 1;

      index = (i-1) * canvas_width + (x-1);
      if (!(imgdata[index].r == targetcolor.r &&
            imgdata[index].g == targetcolor.g &&
            imgdata[index].b == targetcolor.b)){
        break;
      }      
      AddNewList(x,i);
    } 
   
    // 新規に取得した座標で再帰処理
    for (var i = 0; i < newlist.length; i++) {    
      getFillList(newlist[i].x,newlist[i].y,targetcolor,imgdata,fill_list,already_list);
    }    
  }
  
  // ID(R256xR256,R32xC32,R1xC1)からXY座標を取得
  function getXY(value){
     var result = {'x':0,'y':0};
     
     if (value[2] == 'x'){
       result.y = value[1];
       result.x = value.slice(4);
     }else if (value[3] == 'x'){
       result.y = value[1] + value[2];
       result.x = value.slice(5);
     }else if (value[4] == 'x'){
       result.y = value[1] + value[2] + value[3];
       result.x = value.slice(6);
     }
     return result;
  }
    
  // backgroundColorからRGB値を返す
  function Color2RGB(backgroundcolor) {  
    
    // [IE/Chrome/FireFox] rgb(255,255,255)の文字列形式からRGBを取得する 
    var result = backgroundcolor.replace("rgb(","");
    result = result.replace(")","");
    result = result.replace(/ /g,"");
    result = result.split(",");
    
    // [Opera] #ffffff の文字列形式からRGBを取得する 
    var buffer; 
    if (result[0][0] == '#'){
      buffer = new Array();
      buffer[0] = parseInt(result[0].slice(1,3),16);
      buffer[1] = parseInt(result[0].slice(3,5),16);
      buffer[2] = parseInt(result[0].slice(5,7),16);
      result = buffer;
    }
    
    result[0] = parseInt(result[0],10);
    result[1] = parseInt(result[1],10);
    result[2] = parseInt(result[2],10);
    
    return {'r':result[0],'g':result[1],'b':result[2]}; 
  }
</script>

JavaScript - イベント

<script>
  window.onload = function(){
    craetePaletteArea();
    createCanvasArea();
  } 
   
  window.onmouseup = function(){
    OnMouseup();    
  }    
     
  // パレット     
  function OnPalette_Mousedown(obj,event) {
    
    // パレットの選択解除
    var target;
    for (var i = 0; i < 16; i++) {
      for (var j = 0;j < 16; j++) {
        target = document.getElementById('H'+(i+1)+'xW' + (j+1));
        if (target){
          target.style.borderStyle = "none";
        }
      }
    }
    
    // パレットの選択
    obj.style.borderStyle = "solid";
    obj.style.borderWidth = "2px";
    obj.style.borderColor = "#1e90ff" ; 
    
    palette_select_id = obj.id;
  } 
    
  function OnMousedown(obj,event) {
    
    if (obj.id[0] != 'R') return;

    // ペン
    if (canvas_penmode_flg == 1){
      var color_pen = document.getElementById(palette_select_id).style.backgroundColor;
      obj.style.backgroundColor = color_pen;
      canvas_block[obj.id] = Color2RGB(color_pen);
      
      canvas_mousedown_flg = true; 
      
    // 塗りつぶし 
    }else if (canvas_penmode_flg == 2){
      
      // 現在の座標と色を取得
      var point = getXY(obj.id);  
      var targetcolor = Color2RGB(document.getElementById(obj.id).style.backgroundColor); 
      
      // 探索用の配列を生成
      var fill_list = new Object();
      var already_list = new Object();
      for (var i = 0; i < canvas_height; i++) {
        for (var j = 0; j < canvas_width; j++) {
           fill_list['R' + (i+1) + 'xC' +  (j+1)] = 0;
           already_list[already_list.length] = 0;
        }
      }

      // 塗りつぶすブロックを取得 
      getFillList(point.x,point.y,targetcolor,canvas_data,fill_list,already_list);

      // 現在の座標を設定
      fill_list['R' + point.y + 'xC' +  point.x] = 1;
      
      // 塗りつぶす座標を元にキャンバスを描画
      var color_fill = document.getElementById(palette_select_id).style.backgroundColor;
      for(var key in fill_list) {       
         if (fill_list[key] == 1){
            document.getElementById(key).style.backgroundColor = color_fill;
            canvas_block[key] = Color2RGB(color_fill);
         }
      }      
    }     
  }
  
  function OnMousemove(obj,event) {
    
    if (canvas_mousedown_flg){
      obj.style.backgroundColor = document.getElementById(palette_select_id).style.backgroundColor;
      canvas_block[obj.id] = Color2RGB(document.getElementById(palette_select_id).style.backgroundColor);
    }
  }

  function OnMouseup(event) {

    canvas_mousedown_flg = false; 
    
    // ピクセルデータを保存  
    canvas_data = new Array();
    for (var y = 0; y < canvas_height; y++) {
      for (var x = 0;x < canvas_width; x++) {
         canvas_data[canvas_data.length] = canvas_block['R' + (y+1) +'xC'+(x+1)];
      }
    }
  }  
</script>

以上となります。粗雑で改善の余地はありますが、各人で改良して下さいね。

参考リンク

Web IconEditor





関連記事


前の記事：ナンプレの問題を自動で作成する
次の記事：LZW圧縮アルゴリズム[実践的なGIFファイルの作成]

公開日：2016年02月21日 最終更新日：2016年02月23日
記事NO：01787