注意:著者は初心者なので間違ってることがあるので注意してください。

今回は友人の研究に使う３次元fillプログラムを作ったのでまとめてみます。
ついでにテスト駆動開発の練習も兼ねたので、それもまとめたいと思います。

環境

*利用しているライブラリについて記載していなかったので追記しておきます。

python	3.7.4
pytest	5.2.2

pip install pytest

仕様

画像データは３次元配列の0または1の二値データとします。
fillしたい部分の一点を指定すると、その周囲の同じ値のデータが２に書き換えられたデータが出力されます。
テストで使った３次元の配列を以下に書いておきます。

利用データ

[
        [
            [0,1,0,1,0],
            [0,0,1,0,0],
            [0,1,1,1,0],
            [0,0,1,0,0],
            [0,1,0,1,0],
        ],
        [
            [0,0,1,0,0],
            [0,0,1,0,0],
            [1,1,1,1,1],
            [0,0,1,0,0],
            [0,0,0,1,0],
        ],
        [
            [0,1,0,1,0],
            [0,0,1,0,0],
            [1,0,0,0,1],
            [0,0,1,1,0],
            [0,1,0,1,0],
        ],
    ]

テスト駆動開発ってなんぞ

プログラムが想定通りの動作をしているかのテストを行いながら開発すること、かな？
たぶんテストを書いておくことで想定した動作のプログラムを書くことができるのが利点かな？
詳しくはまだ理解できていないので、覚えていきたい所存。
取り合えず、最初にテスト作るらしいので、テストを作っていく。

テストの作成

まず、最初の１点を指定して値を変更させる関数を作成したいので、そのテストを作りましょう。
入力は３次元データ,座標データです。座標データは{"x":2,"y":2,"z":1}のような形式です。
また、フォルダ名はtest_….pyのように頭にtest_をつける必要があり、関数にも同じようにtestをつける必要があります。

test_fill.py

def test__plot_point():
    image_list=[
        [
            [0,1,0,1,0],
            [0,0,1,0,0],
            [0,1,1,1,0],
            [0,0,1,0,0],
            [0,1,0,1,0],
        ],
        [
            [0,0,1,0,0],
            [0,0,1,0,0],
            [1,1,1,1,1],
            [0,0,1,0,0],
            [0,0,0,1,0],
        ],
        [
            [0,1,0,1,0],
            [0,0,1,0,0],
            [1,0,0,0,1],
            [0,0,1,1,0],
            [0,1,0,1,0],
        ],
    ]
    ans_list=[
        [
            [0,1,0,1,0],
            [0,0,1,0,0],
            [0,1,1,1,0],
            [0,0,1,0,0],
            [0,1,0,1,0],
        ],
        [
            [0,0,1,0,0],
            [0,0,1,0,0],
            [1,1,2,1,1],
            [0,0,1,0,0],
            [0,0,0,1,0],
        ],
        [
            [0,1,0,1,0],
            [0,0,1,0,0],
            [1,0,0,0,1],
            [0,0,1,1,0],
            [0,1,0,1,0],
        ],
    ]    
    plot={"x":2, "y":2, "z":1}
    data, defaultvalue, x, y, z = two_fill.plot_point(image_list, plot)
    assert data == ans_list, "正しくFIllできてません。" 
    assert x == plot["x"], "ポイントが移動しています。" 
    assert y == plot["y"], "ポイントが移動しています。" 
    assert z == plot["z"], "ポイントが移動しています。" 
    assert defaultvalue == 1, "デフォルトの数値が変わっています"

このようにテストを書きました。
assert -- == ~~, "***"は、--が~~と等価だった場合は正しく、異なっていた場合はエラーとなり***と表示する、というようになっています。

では、この仕様に合ったプログラムを組んでみましょう。
とりあえず関数だけ作ってテストしてみます。

fill.py

def plot_point(image_list, plot):
    data = defaultvalue = x = y = z = 0
    return data, defaultvalue, x, y, z

さて、こちらをテストしてみましょう。
テストをするにはテストのあるディレクトリに移動した後にpytestコマンドを実行するだけです。特定ファイルを実行したい場合はpytest test_fill.pyのように記述するとできます。
今回のテストを実行すると以下のような結果になりました。

PS

PS C:\work\> pytest
================================================================================================== test session starts ===================================================================================================
platform win32 -- Python 3.7.4, pytest-5.2.2, py-1.8.0, pluggy-0.13.0
rootdir: C:\work\
collected 2 items

test_two_fill.py F                                                                                                                                                                                                  [100%]

======================================================================================================== FAILURES ======================================================================================================== 
____________________________________________________________________________________________________ test__plot_point ____________________________________________________________________________________________________

    def test__plot_point():
        image_list=[
            [
                [0,1,0,1,0],
                [0,0,1,0,0],
                [0,1,1,1,0],
                [0,0,1,0,0],
                [0,1,0,1,0],
            ],
            [
                [0,0,1,0,0],
                [0,0,1,0,0],
                [1,1,1,1,1],
                [0,0,1,0,0],
                [0,0,0,1,0],
            ],
            [
                [0,1,0,1,0],
                [0,0,1,0,0],
                [1,0,0,0,1],
                [0,0,1,1,0],
                [0,1,0,1,0],
            ],
        ]
        ans_list=[
            [
                [0,1,0,1,0],
                [0,0,1,0,0],
                [0,1,1,1,0],
                [0,0,1,0,0],
                [0,1,0,1,0],
            ],
            [
                [0,0,1,0,0],
                [0,0,1,0,0],
                [1,1,2,1,1],
                [0,0,1,0,0],
                [0,0,0,1,0],
            ],
            [
                [0,1,0,1,0],
                [0,0,1,0,0],
                [1,0,0,0,1],
                [0,0,1,1,0],
                [0,1,0,1,0],
            ],
        ]
        plot={"x":2, "y":2, "z":1}
        data, defaultvalue, x, y, z = two_fill.plot_point(image_list, plot)
>       assert data == ans_list, "正しくFIllできてません。"
E       AssertionError: 正しくFIllできてません。
E       assert 0 == [[[0, 1, 0, 1, 0], [0, 0, 1, 0, 0], [0, 1, 1, 1, 0], [0, 0, 1, 0, 0], [0, 1, 0, 1, 0]], [[0, 0, 1, 0, 0], [0, 0, 1, 0,..., 0, 1, 0, 0], [0, 0, 0, 1, 0]], [[0, 1, 0, 1, 0], [0, 0, 1, 0, 0], [1, 0, 0, 
0, 1], [0, 0, 1, 1, 0], [0, 1, 0, 1, 0]]]

test_two_fill.py:52: AssertionError
============================================================================================== 1 failed, 1 passed in 0.64s ===============================================================================================

当然の如くエラーです。このようにエラーが起こった個所が出力されるのでバグ修正がやりやすかったり、想定通りのエラーが出るかのテストなどができるのかなと思います。
では、この調子でテストをがーっと作っていきましょう。
...と、今回上下左右直上直下の６つの関数をテストしようと思ったのですが、それぞれの関数でおおもとの関数を再起呼び出しすることになり、一つ一つのテストができないことがわかってしまいました。（再起呼びだし部分を特定のテスト時のみ実行しないみたいなことができたらいいんですが…）
なので今回は一点を指定する関数と、全体を塗りつぶす関数、一連の動作を行う関数の３つのテストを作成したいと思います。
今回のテストは以下のようになりました。

test_fill.py

import two_fill

def test__plot_point():
    image_list=[
        [
            [0,1,0,1,0],
            [0,0,1,0,0],
            [0,1,1,1,0],
            [0,0,1,0,0],
            [0,1,0,1,0],
        ],
        [
            [0,0,1,0,0],
            [0,0,1,0,0],
            [1,1,1,1,1],
            [0,0,1,0,0],
            [0,0,0,1,0],
        ],
        [
            [0,1,0,1,0],
            [0,0,1,0,0],
            [1,0,0,0,1],
            [0,0,1,1,0],
            [0,1,0,1,0],
        ],
    ]
    ans_list=[
        [
            [0,1,0,1,0],
            [0,0,1,0,0],
            [0,1,1,1,0],
            [0,0,1,0,0],
            [0,1,0,1,0],
        ],
        [
            [0,0,1,0,0],
            [0,0,1,0,0],
            [1,1,2,1,1],
            [0,0,1,0,0],
            [0,0,0,1,0],
        ],
        [
            [0,1,0,1,0],
            [0,0,1,0,0],
            [1,0,0,0,1],
            [0,0,1,1,0],
            [0,1,0,1,0],
        ],
    ]    
    plot={"x":2, "y":2, "z":1}
    data, defaultvalue, x, y, z = two_fill.plot_point(image_list, plot)
    assert data == ans_list, "正しくFIllできてません。" 
    assert x == plot["x"], "ポイントが移動しています。" 
    assert y == plot["y"], "ポイントが移動しています。" 
    assert z == plot["z"], "ポイントが移動しています。" 
    assert defaultvalue == 1, "デフォルトの数値が変わっています"

def test__fill_main():
    image_list=[
        [
            [0,1,0,1,0],
            [0,0,1,0,0],
            [0,1,1,1,0],
            [0,0,1,0,0],
            [0,1,0,1,0],
        ],
        [
            [0,0,1,0,0],
            [0,0,1,0,0],
            [1,1,2,1,1],
            [0,0,1,0,0],
            [0,0,0,1,0],
        ],
        [
            [0,1,0,1,0],
            [0,0,1,0,0],
            [1,0,0,0,1],
            [0,0,1,1,0],
            [0,1,0,1,0],
        ],
    ]
    ans_list=[
        [
            [0,1,0,1,0],
            [0,0,2,0,0],
            [0,2,2,2,0],
            [0,0,2,0,0],
            [0,1,0,2,0],
        ],
        [
            [0,0,2,0,0],
            [0,0,2,0,0],
            [2,2,2,2,2],
            [0,0,2,0,0],
            [0,0,0,2,0],
        ],
        [
            [0,1,0,1,0],
            [0,0,2,0,0],
            [2,0,0,0,2],
            [0,0,2,2,0],
            [0,1,0,2,0],
        ],
    ]    
    plot={"x":2,"y":2,"z":1}
    data = two_fill.fill_main(image_list, plot["x"], plot["y"], plot["z"], 1)
    assert  data == ans_list, "正しくFIllできてません。" 


def test__fill():
    image_list=[
        [
            [0,1,0,1,0],
            [0,0,1,0,0],
            [0,1,1,1,0],
            [0,0,1,0,0],
            [0,1,0,1,0],
        ],
        [
            [0,0,1,0,0],
            [0,0,1,0,0],
            [1,1,1,1,1],
            [0,0,1,0,0],
            [0,0,0,1,0],
        ],
        [
            [0,1,0,1,0],
            [0,0,1,0,0],
            [1,0,0,0,1],
            [0,0,1,1,0],
            [0,1,0,1,0],
        ],
    ]
    ans_list=[
        [
            [0,1,0,1,0],
            [0,0,2,0,0],
            [0,2,2,2,0],
            [0,0,2,0,0],
            [0,1,0,2,0],
        ],
        [
            [0,0,2,0,0],
            [0,0,2,0,0],
            [2,2,2,2,2],
            [0,0,2,0,0],
            [0,0,0,2,0],
        ],
        [
            [0,1,0,1,0],
            [0,0,2,0,0],
            [2,0,0,0,2],
            [0,0,2,2,0],
            [0,1,0,2,0],
        ],
    ]    
    plot={"x":2,"y":2,"z":1}
    data = two_fill.fill(image_list, plot)
    assert  data == ans_list, "正しくFIllできてません。"

これが正しく動作するような関数を作成していけばいいようですね。
では本題の3次元fillを作りましょう。
手法は簡単でして、全探索を行います。探索は4近傍で行います。
探索のアルゴリズムは下のgifのようになっています。

これが３次元（直上、直下）にも移動するようにしたのが今回のプログラムとなっています。

まずは、最初の一点を指定して色を塗る関数を作成しましょう。

fill.py

def plot_point(data, plot):
    defaultvalue = data[plot["z"]][plot["y"]][plot["x"]]
    data[plot["z"]][plot["y"]][plot["x"]]=2
    return data, defaultvalue, plot["x"], plot["y"], plot["z"]

次に自分の付近１セルを探索し、移動し、色を塗る関数をそれぞれ作成しましょう。
今回は右に塗る関数だけ記述しますね。

fill.py


def fill_right(data, x, y, z, defaultvalue):
    try:
        if defaultvalue==data[z][y][x+1]:
            x=x+1
            data[z][y][x]=2
            move_flag=True
            fill_main(data, x, y, z, defaultvalue)
        else:
            move_flag=False
    except IndexError:
        move_flag=False
    except Exception as e:
        raise e
    return data

続いて、これらを実行する関数を作成します。

fill.py

def fill_main(data, x, y, z, defaultvalue):
    # point_data=PointData(plot)
    data = fill_right(data, x, y, z, defaultvalue)
    data = fill_down(data, x, y, z, defaultvalue)
    data = fill_buttom(data, x, y, z, defaultvalue)
    data = fill_left(data, x, y, z, defaultvalue)
    data = fill_up(data, x, y, z, defaultvalue)
    data = fill_top(data, x, y, z, defaultvalue)
    return data

最後に、データと点の座標を渡すと、点と周りを塗ってくれる関数を作成しましょう。

fill.py

def fill(data, plot):
    data, defaultvalue, x, y, z = plot_point(data, plot)
    data = fill_main(data, x, y, z, defaultvalue)
    return data

これでできたと思います。
実際にテストを動かしてみると

SP

PS C:\work> pytest
================================================================================================== test session starts =================================================================================================== 
platform win32 -- Python 3.7.4, pytest-5.2.2, py-1.8.0, pluggy-0.13.0
rootdir: C:\work
collected 3 items                                                                                                                                                                                                          

fill.py ...                                                                                                                                                                                                [100%] 

=================================================================================================== 3 passed in 0.56s ====================================================================================================

となりました。fill.pyの後ろに...とありますが、これはテスト３つがすべてクリアしたことを表します。例えば、２つ目のテストでエラーが出た場合は.F.と出ます。
どうやら想定通りの関数が書けたようです。

まとめ

今回は３次元のfill関数を作成してみました。
実験したところ自分のPCだと3300以上の容量をfillしようとするとスタックオーバーフローになってしまいました。どうにか改良したいところです。