矩形模様の最短手順での塗りつぶし。その４

Question

前提

矩形模様の最短手順での塗りつぶし。その３の続きです。

問題

二次元の矩形領域を塗りつぶして、色の模様を描きます。
矩形領域の塗りつぶしという操作では、始点(xs,ys)と終点(xe,ye)と色の名前(color)を指定することで、その矩形範囲を塗りつぶします。
なお、領域上の同じ位置に複数回の塗りつぶしが行われると、後で実行した色で塗りつぶされます。

実現したいこと

このとき、任意で指定された模様を描くために、できるだけ少ない回数で塗りつぶすための操作データ（始点、終点、色）のリストを求めたい。

回答してほしいこと

• 上記を実現するために利用できるアルゴリズム、もしそれに名前があればそのアルゴリズムの名称
• そのアルゴリズムの概要の説明
• そのアルゴリズムを利用して問題をとく、単純な例での具体的な手順
• 具体的に実行可能なPythonコード

ただし、以下の手法以外を提示ください。

• 最小矩形分割問題
• スキャンライン法 (Scanline Algorithm)
• 連結成分ラベリング (Connected Component Labeling)

すなわち、指定された模様を走査していく過程で、異なる色があらわれた時点で探索を止める手法以外での解決方法を探しています。

調べたこと・考えたこと

ChatGPTにたずねたところ「グラフ理論に基づくアプローチ」が利用できるかもしれないと提案されましたが、詳細は確認していません。

また、塗りつぶしは後の操作結果で上書き（重ね合わされる）ことから、レイヤー（層）を意識した手法が必要だと思われます。
たとえば３次元上で複数の矩形の板（ポリゴン）を水平面に層状に重ね合わせ、それを真上から見た場合を考えます。
任意の指定された模様を最小の板の数で実現する問題と等価だと思われます。

たとえば動的計画法なりで模様を走査していく過程で異なる色が現れた時点で探索を止めていますが、
その場合に「この位置はあとの操作で塗りつぶしが必要」として探索を進めるようなアプローチがよりよいように思います。

模様の具体例

pat = [['R','G','G','R'],
       ['R','G','G','R']]

幅4x高さ2の領域に上の模様を描きたい場合は、左上を原点とすると

instructions = [((0,0),(0,1),'R'),  # 左端の赤い矩形
                ((1,0),(2,1),'G'),  # 中央の緑の矩形
                ((3,0),(3,1),'R')]  # 右端の赤い矩形

という３回の操作で描けますが

instructions = [((0,0),(3,1),'R'),  # 全体を赤い矩形で塗りつぶし
                ((1,0),(2,1),'G')]  # 中央に緑の矩形で塗りつぶし

という、より少ない２回の操作で描けます。

問題の制限

指定される色の模様の全体領域サイズは幅と高さともに1024以下。色の種類の数は256色以下です。

Answer 1

この回答はGPT-4による自動生成回答です

この問題に対して、貪欲法 (Greedy Algorithm) を利用することができます。貪欲法は、局所的に最適な選択を行い、最終的に全体の最適解にたどり着くアルゴリズムです。

アルゴリズムの概要:

1. 現在の矩形領域の左上から右下まで走査し、まだ塗られていないセルを見つける。
2. そのセルから始めて、同じ色の最大の矩形領域を見つける。
3. その矩形領域を塗りつぶし、操作データをリストに追加する。
4. 全てのセルが塗られるまで、1-3の手順を繰り返す。

単純な例での具体的な手順:

1. 左上のセル (0, 0) が赤色であることを確認し、最大の赤色矩形領域を見つける。この場合、(0, 0) から (0, 1) までの矩形領域が最大です。
2. その矩形領域を塗りつぶし、操作データ ((0, 0), (0, 1), 'R') をリストに追加する。
3. 次に、(1, 0) から始めて、最大の緑色矩形領域を見つける。この場合、(1, 0) から (2, 1) までの矩形領域が最大です。
4. その矩形領域を塗りつぶし、操作データ ((1, 0), (2, 1), 'G') をリストに追加する。
5. 最後に、(3, 0) から始めて、最大の赤色矩形領域を見つける。この場合、(3, 0) から (3, 1) までの矩形領域が最大です。
6. その矩形領域を塗りつぶし、操作データ ((3, 0), (3, 1), 'R') をリストに追加する。

具体的なPythonコード:

def find_max_rectangle(pattern, x, y):
    color = pattern[y][x]
    width = len(pattern[0])
    height = len(pattern)
    x_end = x
    y_end = y

    while x_end < width and pattern[y][x_end] == color:
        x_end += 1

    while y_end < height and all(pattern[y_end][x] == color for x in range(x, x_end)):
        y_end += 1

    return (x, y), (x_end - 1, y_end - 1), color

def greedy_fill(pattern):
    width = len(pattern[0])
    height = len(pattern)
    instructions = []

    for y in range(height):
        for x in range(width):
            if pattern[y][x] is not None:
                start, end, color = find_max_rectangle(pattern, x, y)
                instructions.append((start, end, color))

                for y_fill in range(start[1], end[1] + 1):
                    for x_fill in range(start[0], end[0] + 1):
                        pattern[y_fill][x_fill] = None

    return instructions

pattern = [['R', 'G', 'G', 'R'],
           ['R', 'G', 'G', 'R']]

instructions = greedy_fill(pattern)
print(instructions)

このコードは、与えられた例で正しい結果 [((0, 0), (0, 1), 'R'), ((1, 0), (2, 1), 'G'), ((3, 0), (3, 1), 'R')] を返します。ただし、このアルゴリズムは最適解を保証するものではありません。最適解を求めるためには、より高度なアルゴリズムやヒューリスティックが必要です。

Comments

[8524ba23]

これもこれまでと同じ手法だと思われます。

Answer 2

この問題を解決するのはいまのGPT-4では難しい
ということが分かったことを成果としてクローズします。

問題を考えるきっかけになったネタ
続・ドラクエ3驚異のマル秘圧縮術公開！　内藤かんチャン

追記

この問題に一番近いと思われる論文を見つけたので備忘録のためにあげておきます。
Compressing Rectilinear Pictures and Minimizing Access Control Lists

a model that also has applications to rectilinear picture compression and figure drawing in common graphics software packages. Here the goal is to create a colored rectilinear pattern within an initially white rectangular canvas, and the basic operation is to choose a subrectangle and paint it a single color, overwriting all previous colors in the rectangle. Rectangle Rule List (RRL) minimization is the problem of finding the shortest list of rules needed to create a given pattern.

このモデルは、一般的なグラフィック ソフトウェア パッケージでの直線画像圧縮や図形描画にも応用できます。ここでの目標は、最初は白い長方形のキャンバス内に色付きの直線パターンを作成することであり、基本的な操作は部分長方形を選択して単一の色でペイントし、長方形内の以前の色をすべて上書きすることです。長方形ルール リスト (RRL) の最小化は、特定のパターンを作成するために必要なルールの最短のリストを見つける問題です。

ただし「Rectangle Rule Lists(RRL)」という言葉が一般的でないのか、類似論文すら見つかりません。