LoginSignup
3
2

More than 5 years have passed since last update.

@gushwell(出井 秀行)

最大面積の正方形と最大面積の長方形の領域を探す

Last updated at Posted at 2019-04-08

どんなプログラムなのか

まずは、実行例を。

マウスのドラッグやクリックで、以下のように、領域の一部を塗りつぶします。Shiftキーを押しながらドラッグすれば、その領域をクリアできます。

この塗りつぶした領域のなかから、最大面積となる正方形または長方形を求めるというプログラムです。

それぞれのsolveボタンを押すと、結果が得られます。以下は、正方形の領域を求めたところです。

薄い紫色が最大面積の正方形です。size=81と表示されるので、9 * 9 の正方形であることがわかります。

実際に動きを確認できるように、この記事の最後に、CodePenのページを埋め込んでいます。

どうやって求めているか

最大面積の正方形を求める

すべての地点に対し、その地点を正方形の左上としたしたときの面積を求め、一番大きなのがどれかを求めています。
すごく当たり前のことをやっているだけですね。

どうやって正方形かどうかを判断するかですが、
例えば、以下の図で、△部分が黒の正方形であると分かっている場合を考えます。

△△△△☆
△△△△☆
△△△△☆
△△△△☆
★★★★◆

△部分の右下を(x,y)地点とすると、

  1. (x+1,y+1) が黒
  2. ☆部分がすべて黒
  3. ★部分がすべて黒

を満たした場合、正方形の辺の長さは + 1 となり、△部分が増えることになります。
これを繰り返していけば、正方形の辺の長さが求まることになります。

再帰処理の応用としてとらえることができますね。

最大面積の長方形を求める

面積が最大の長方形を求める方法ですが、こちらは正方形よりも泥臭い方法で最大面積を求めています。

まず、注目している点が長方形の左上とした時の、高さが１の長方形の面積を求めます。次に高さが２の長方形の面積を求めます。高さが3,4,5... と求めていき、最大の長方形を求めます。これをすべての点で実行しています。

Canvasのマウスイベントを処理する

このプログラムでは、HTML5のCanvasをラッピングしたMyCanvasクラスを定義しています。そこでマウスイベントに対応するための処理を書いています。

たとえば、MouseDownイベントに対応するために、MyCanvasクラスのコンストラクタで以下のようなコードを書いています。

this.canvas.onmousedown = (e) => {
    var rect = this.canvas.getBoundingClientRect();
    let x = e.clientX - rect.left;
    let y = e.clientY - rect.top;
    if (this.onMouseDown)
        this.onMouseDown(x, y);
    return false;
};

onmousedownがCanvasに定義されているイベントハンドラです。
ここで求めているx,y は、canvas要素の左上からの座標です。これを引数にしてMyCanvasクラスの独自のonMouseDowncallback関数を呼び出しています。つまり、MouseDownベントを発行しているということですね。このイベントを処理するハンドラは、Boardクラスに以下のように定義してあります。

this.canvas.onMouseDown = (x, y) => {
    let loc = this.toLocation(x,y);
    this.startSelection(loc);
};

このイベントハンドラでは、ピクセル単位の座標(x, y)を行(row)と桁(col)に変換し、ドラッグの処理を開始しています。具体的には実際のコード（後述）をみてください。

JavaScriptのコード

Program.js

import { Board } from './board.js';
import { Solver } from './solver.js';

export class Program {
    constructor() {
        this.board = new Board('mycanvas', 30, 30);              
    }

    run() {
        document.getElementById('solve1Button')
            .addEventListener('click', () => this.solve(true), false);
        document.getElementById('solve2Button')
            .addEventListener('click', () => this.solve(false), false);
        document.getElementById('clearButton')
            .addEventListener('click', () => this.clearAll(), false);
    }

    solve(isSquare) {
        let solver = new Solver(this.board);
        let area = solver.solve(isSquare);
        this.board.redraw();
        for (let r = area.top; r < area.top + area.height; r++) {
            for (let c = area.left; c < area.left + area.width; c++) {
                this.board.drawPoint(r, c, '#E6D3FF');
            }
        }
        let div = document.getElementById('status');
        div.textContent = 'Size=' + area.size;

    };

    clearAll() {
        for (let r = 0; r < this.board.height; r++) {
            for (let c = 0; c < this.board.width; c++) {
                this.board. clearPoint(r, c);
            }
        }
    };
}

Solver.js

import { Board } from './board.js';
import { Area } from './area.js';

export class Solver {
    constructor (board) {
        this.board = board;
    }

    solve(isSquare = true) {
        let maxarea = new Area(0, 0, 0, 0);
        for (let loc of this.board.getLocations(true)) {
            let area = isSquare 
              ? this.getSquare(loc.row, loc.col, 1)
              : this.getMaxRectangle(loc.row, loc.col, 1);
                if (area.size > maxarea.size)
                    maxarea = area;
        }
        return maxarea;
    }

    getSize(area) {
        return area.width * area.height;
    }

    // 左上が(x,y)の最大正方形を求める
    getSquare(top, left, sideLen) {
        let maxarea = new Area(top, left, sideLen, sideLen);
        // 右下が黒じゃなければ、今まで求めたwidthが、正方形の辺の長さ
        if (this.board.get(top + sideLen, left + sideLen) === false)
            return maxarea;
        // 横方向がすべて黒でないならば、今まで求めたwidthが、正方形の辺の長さ
        if (this.getHorBlackCount(top + sideLen, left) < sideLen + 1)
            return maxarea;
        // 縦方向がすべて黒でないならば、今まで求めたwidthが、正方形の辺の長さ
        if (this.getVirtBlackCount(top, left + sideLen) < sideLen + 1)
            return maxarea;
        // width+1の可能性があるので、右下まで広げて調べる（再帰処理）
        return this.getSquare(top, left, sideLen + 1);
    }

    // 最大の長方形を求める
    getMaxRectangle() {
        let maxarea = new Area(0, 0, 0, 0);
        for (let r = 0; r < this.board.height; r++) {
            for (let c = 0; c < this.board.width; c++) {
                let area = this.getRectangle(r, c);
                if (area.size > maxarea.size)
                    maxarea = area;
            }
        }
        return maxarea;
    }

    // 左上が(x,y)の最大長方形を求める (GetMaxRectangleの下請け)
    getRectangle(row, col) {
        let area = new Area(row, col, 0, 0);
        if (this.board.get(row,col)=== false)
            return area;
        let hsize = 1;
        let wminsize = this.getHorBlackCount(row, col);
        for (let r of this.getVirtIndexes(row+1, col)) {
            wminsize = Math.min(this.getHorBlackCount(r, col), wminsize);
            hsize++;
            if (hsize * wminsize > area.size) {
                area.width = wminsize;
                area.height = hsize;
            }
        }
        return area;
    }

    // 縦方向の連続する黒石の位置を列挙する 
    *getVirtIndexes(row, col) {
        for (let r= row; r < this.board.height; r++) {
            if (this.board.get(r, col))
                yield r;
            else
                break;
        }
    }

    // 横方向の黒の色をカウント
    getHorBlackCount(row, col) {
        let count = 0;
        for (let c = col; c < this.board.width; c++) {
            if (this.board.get(row, c))
                count++;
            else
                return count;
        }
        return count;
    }

    // 縦方向の黒の色をカウント
    getVirtBlackCount(row, col) {
        let count = 0;
        for (let r = row; r < this.board.height; r++) {
            if (this.board.get(r, col))
                count++;
            else
                return count;
        }
        return count;
    }

}

area.js

export class Area {
    constructor (top, left, width, height ) {
        this.top = top;
        this.left = left;
        this.width = width;
        this.height = height;

    }

    get size() {
        return this.width * this.height;
    }
}

board.js

import { MyCanvas } from './canvas.js';

export class Board {
    constructor (id, width, height) {
        let wpx = this.toPixel(width) + 1;
        let hpx = this.toPixel(height) + 1;
        this.area = Array.from(new Array(height), () => new Array(width).fill(false));
        this.width = width;
        this.height = height;
        this.canvas = new MyCanvas(id, wpx, hpx);    
        this.lastloc = { row: 0, col: 0 };
        this.drag = false;

        this.drawGrid();
        this.canvas.onMouseClick = (x, y) => {
            if (this.drag) {
                this.drag = false;
                return;
            }
            let loc = this.toLocation(x,y);
            this.togglePoint(loc);
        };

        this.canvas.onMouseDown = (x, y) => {
            let loc = this.toLocation(x,y);
            this.startSelection(loc);
        };

        this.canvas.onMouseUp = (x, y) => {
            this.startloc = undefined;
        };

        this.canvas.onMouseMove = (x, y, leftbuttonDown, shiftKey) => {
            if (leftbuttonDown) {
                let loc = this.toLocation(x,y);
                this.lastloc = loc;
                this.moveSelection(loc, shiftKey);
            }
        };
    }

    *getLocations(exists) {
        for (let r = 0; r < this.height; r++) {
            for (let c = 0; c < this.width; c++) {
                if (this.area[r][c])
                    yield  { row: r, col: c };
            }
        }
    }

    get(row, col) {
        if (0 <= row && row < this.height &&
            0 <= col && col < this.width)
            return this.area[row][col];
        return false;
    }

    togglePoint(loc) {
        if (this.area[loc.row][loc.col]) {
            this.clearPoint(loc.row, loc.col);
        } else {
            this.drawPoint(loc.row, loc.col);
        }
    }

    startSelection(loc) {
        this.startloc = loc;
    }

    moveSelection(loc, shiftKey) {
        if (this.startloc === undefined)
            return;
        this.drag = true;
        let col1 = this.startloc.col;
        let row1 = this.startloc.row;
        let col2 = loc.col;
        let row2 = loc.row;
        for (let r = row1; r <= row2; r++) {
            for (let c = col1; c <= col2; c++) {
                if (shiftKey)
                    this.clearPoint(r, c);
                else
                    this.drawPoint(r, c);
            }
        }
    }

    redraw() {
        for (let r = 0; r < this.height; r++) {
            for (let c = 0; c < this.width; c++) {
                if (this.get(r,c))
                    this.drawPoint(r, c);
                else
                    this.clearPoint(r, c);
            }
        }
    }
    drawPoint(row, col, color = '#ccc') {
        this.area[row][col] = true;
        let ny = this.toPixel(row) + 1;
        let nx = this.toPixel(col) + 1;
        this.canvas.drawPoint(nx, ny, color, 8);
    }

    clearPoint(row, col) {
        this.area[row][col] = false;
        let ny = this.toPixel(row) + 1;
        let nx = this.toPixel(col) + 1;
        this.canvas.drawPoint(nx, ny, '#fff', 8);
    }

    drawGrid() {
        for (let x = 0; x <= this.width; x++) {
            this.canvas.drawLine(this.toPixel(x)+0.5, this.toPixel(0)+0.5, this.toPixel(x)+0.5, this.toPixel(this.height)+0.5, '#eee');
        }
        for (let y = 0; y <= this.height; y++) {
            this.canvas.drawLine(this.toPixel(0)+0.5, this.toPixel(y)+0.5, this.toPixel(this.width)+0.5, this.toPixel(y)+0.5, '#eee');
        }
    }

    toPixel(p) {
        return p * 10;
    }

    toLocation(x, y) {
        return {
            row: Math.floor(y / 10),
            col: Math.floor(x / 10)
        };
    }

}

canvas.js

export class MyCanvas {
    constructor (id, width, height) {
        this.canvas = document.getElementById(id);
        this.ctx = this.canvas.getContext('2d');
        if (width)
            this.ctx.canvas.width = width;
        if (height)
            this.ctx.canvas.height = height;
        this.width = this.ctx.canvas.width;
        this.height =  this.ctx.canvas.height;
        // ユーザが定義するイベントハンドラ
        this.onClick = null;
        this.onMouseDown = null;
        this.onMouseMove = null;
        this.onMouseUp = null;

        //let self = this;
        this.canvas.onclick = (e) => {
            var rect = this.canvas.getBoundingClientRect();
            let x = e.clientX - rect.left;
            let y = e.clientY - rect.top;
            if (this.onMouseClick)
                this.onMouseClick(x, y);
            return false;
        };

        this.canvas.onmousedown = (e) => {
            var rect = this.canvas.getBoundingClientRect();
            let x = e.clientX - rect.left;
            let y = e.clientY - rect.top;
            if (this.onMouseDown)
                this.onMouseDown(x, y);
            return false;
        };

        this.canvas.onmousemove = (e) => {
            var rect = this.canvas.getBoundingClientRect();
            let x = e.clientX - rect.left;
            let y = e.clientY - rect.top;
            var data = e.buttons;
            var buttonl = ((data & 0x0001) ? true : false);
            if (this.onMouseMove)
                this.onMouseMove(x, y, buttonl, e.shiftKey);
            return false;
        };

        this.canvas.onmouseup = (e) => {
            var rect = this.canvas.getBoundingClientRect();
            let x = e.clientX - rect.left;
            let y = e.clientY - rect.top;
            if (this.onMouseUp)
                this.onMouseUp(x, y);
            return false;
        };


    }

    // 線
    drawLine(x1, y1, x2, y2, color = null, width = 1) {
        this.ctx.save();
        if (color != null)
            this.ctx.strokeStyle = color;
        this.ctx.lineWidth = width;
        this.ctx.beginPath();
        this.ctx.moveTo(x1, y1);
        this.ctx.lineTo(x2, y2);
        this.ctx.closePath();
        this.ctx.stroke();
        this.ctx.restore();
    }

    drawPoint(x1, y1, color, size = 3) {
        this.ctx.save();
        this.ctx.beginPath();
        this.ctx.fillStyle = color;
        this.ctx.fillRect(x1, y1, size, size);
        this.ctx.restore();
    }

    // 矩形を描く
    drawRect(x1, y1, width, height, color = null, linewidth = 1, fill = false) {
        this.ctx.save();
        this.ctx.beginPath();
        if (fill) {
            if (color != null)
                this.ctx.fillStyle = color;
            this.ctx.fillRect(x1, y1, width, height);
        } else {
            if (color != null)
                this.ctx.strokeStyle = color;
            this.ctx.lineWidth = linewidth;
            this.ctx.strokeRect(x1, y1, width, height);
        }
        this.ctx.restore();
    }

    // すべてをクリア
    clearAll() {
        this.ctx.clearRect(0, 0, this.width, this.height);
    }
}

index.html

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <title>Max Area Size</title>
  <style>
      canvas {
          margin: 11px;
      }
  </style>
</head>
<body>
  <div>
  <input id="solve1Button" type="button" value="Solve(正方形)" >
  <input id="solve2Button" type="button" value="Solve(長方形)" >
  <input id="clearButton" type="button" value="Clear" >
</div>
  <div>
      <canvas id="mycanvas"></canvas>
  </div>
  <div id="status"></div>

  <script type="module">
      import { Program } from './program.js';
      var program = new Program();
      program.run();
  </script>
</body>
</html>

CodePenの埋め込み

上記コードをCodePenで書いて、埋め込んでみました。

マウスのドラッグで、矩形を塗りつぶせます。シフトキーを押しながらドラッグすれば、塗りつぶした領域をクリアすることができます。マウスのクリックでその位置を反転させます。

Solve(正方形)ボタンで、最大の正方形を求めます。
Solve(長方形)ボタンで、最大の長方形を求めます。

See the Pen Max Area Size by Gushwell (@gushwell) on CodePen.

3
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
2