【JavaScript】Bucket Fill Algorithm【Canvas】

#はじめに
古いプログラムを漁っていたら、Bucket Fill Algorithmのプログラムが見つかったので、自分用に残しておきます。
確か効率の良い<b>凹塗りつぶしアルゴリズム</b>であったと記憶しております。
元は自分が書いたものではありません。
元がES5で書かれていたので、ES6で書き直して、不具合を1件直して、コメントを追記しております。

下の画像を見ると若干塗り残しがあるように見えますが、
これは塗り残しではなく、外枠にアンチエイリアスがかかったためです。

![ダウンロード (1).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/163605/6bfd01d1-42af-21a3-54b5-3516fd840514.png)


#使い方

```js
const bucketFill = new BucketFill(canvas); // newする canvasを渡す
bucketFill.setSeed(pos.x, pos.y); // 塗りつぶし開始座標を渡す
bucketFill.setFillColor(255, 0, 0); // 塗りつぶす色を指定する
bucketFill.paint(); // 塗りつぶす
```

#ソース
BucketFill クラスのソースを掲載します。
割と単純なアルゴリズムですので、ソースのコメントを見れば理解できると思います。

```js
class BucketFill {
    constructor(canvas) {
        this.seeds = [];
        this.setFillColor(0, 0, 0);
        this.canvas = canvas;
        this.imageData = canvas.getContext('2d').getImageData(0, 0, canvas.width, canvas.height);
    }

    // 塗りつぶし色の変更
    setFillColor(r, g, b) {
        this.fillColor = (r << 16) + (g << 8) + b;
    }

    // シードの設定
    setSeed(x, y) {
        this.seeds = [];
        if (x < this.canvas.width && y < this.canvas.height) { // 引数チェック
            this.seeds.push({x, y});
            this.seedColor = this.getColor(x, y);
        }
    }

    // シードによる塗りつぶし
    seedFill(x, y) {
        const seedColor = this.seedColor;
        if(seedColor === this.fillColor) {// 既に塗られている
            return;
        }
        this.setColor(this.fillColor, x, y);

        // 右側へ走査する
        let rightX = x + 1;
        while (rightX < this.canvas.width) {
            const c = this.getColor(rightX, y);            
            if(c === seedColor) {// 現在の色がシードの色と一致する
                this.setColor(this.fillColor, rightX, y);
            } else {
                break;
            }
            rightX++;
        }

        // 左側へ走査
        let leftX = x - 1;
        while (leftX >= 0) {
            const c = this.getColor(leftX, y);            
            if(c === seedColor) {// 現在の色がシードの色と一致する
                this.setColor(this.fillColor, leftX, y);
            } else {
                break;
            }
            leftX--;
        }

        // 上側のシードを見つける
        if(y - 1 >= 0) {
            this.findSeed(leftX, rightX, y - 1);
        }
        // 下側のシードを見つける
        if (y + 1 < this.canvas.height) {
            this.findSeed(leftX, rightX, y + 1);
        }
    }

    // シードを見つける
    findSeed(leftX, rightX, y) {
        let seed = false;
        for(let x = leftX + 1; x < rightX; x += 1) {
            const c = this.getColor(x, y);
            if(this.seedColor === c) {// 現在の色がシードの色
                seed = true;
            } else if(seed) {// 左がシード色で現在の色がシードの色ではない
                this.seeds.push({ x: x - 1, y });
                seed = false;
            }
        }
        if(seed) {
            this.seeds.push({ x: rightX - 1, y });
        }
    }

    // 塗りつぶし
    paint() {
        while (this.seeds.length > 0) {// シードが無くなるまで繰り返す
            const seed = this.seeds.shift();
            this.seedFill(seed.x, seed.y);
        }
        this.canvas.getContext("2d").putImageData(this.imageData, 0, 0);
    }

    getColor(x, y) {
        const pixels = this.imageData.data,
            w = this.canvas.width,
            h = this.canvas.height,
            p = ((w * y) + x) * 4;
        let rgb = 0;
        rgb += (pixels[p] << 16);
        rgb += (pixels[p+1] << 8);
        rgb += (pixels[p+2]);
        return rgb;
    } 

    setColor(color, x, y) {
        const pixels = this.imageData.data,
            w = this.canvas.width,
            h = this.canvas.height,
            p = ((w * y) + x) * 4;
        pixels[p] = ((color & 0xFF0000) >> 16) 
        pixels[p + 1] = ((color & 0xFF00) >> 8) 
        pixels[p + 2] = color & 0xFF
    }
}
```