長方形の交差問題とか

色々調査中…

結局さっさと英語で探した方が色々わかりやすい資料がいっぱい出てくるんな…
時間がかけられるなら自分で考える能力よりも検索する能力の方が問われてるよな…
英語で検索できるのは、やはり大きいか…。

“rectangle intersect case” で検索、長方形、交差、場合分けみたいな.. 場合分けって case でいいのかな?

この2つを組み合わせれば、そこそこの実行速度が得られるだろうか…

1. 交差する長方形の探索

2次元セグメント木が有効か。
動的長方形交差 Dynamic rectangular intersection

結局自分がやろうとしていることは全てのパターンを探さないといけないので…
O(n) -> O(log n) くらいには変わるみたい。

2. 交差した時に生成する長方形

さすが神々の住む stackoverflow 欲しいものが見つかった。
yield とか operator overload も使っているので勉強になりそう。
何よりシンプル。

いま読んでみたけど、このコードはやばい… 凄すぎる…。 若干、求めてたのと違うので、長方形を小分割してしまっている、実装方針はこれで。
詳細な実装方針はナノピコ流を使おう。

参照もとの SFML に intersect だけでなく contains(overlay?) みたいなのものあるので参考に。

○ nor 演算子の自作

できない orz

まず NOR 演算子がない…
python nor operator - Google
Python の演算子の一覧

演算子の自作はできそうだけど…
Python: defining my own operators?

3. ナノピコ教室流に解いて行くか…

結局、長方形見つけないといけないので…

理解するために Python で書き直す。

def rectangle(board):
    """
    考え方
        0) 以下の図について考える。

        1111110
        1101101
        1110110
        0111101
        1111110
        1111111
        0010010


       1) 右下隅の座標
           row0 = 5, col0 = 4 を右下隅に
           もつユニークな長方形が存在する。

           なぜ存在すると言えるのか?
           0 と接する線を有する長方形が存在するからである。

        1111 1 | 1 0
        1101 1 | 0 1
        1110 1 | 1 0
        0111 1 |[0]1
        1111 1 | 1 0
        1111 1 | 1 1
        -------|--
        0010[0]| 1 0


        2) 左上の座標
           あとは左上の座標が求まれば良い。
           どのようにして見つけるか。

           単純に考えると次の3つが考えられる。が..
           left_0_wall ...

           右側の壁の高さよりも高いものであればユニーな物として考えられる。

      ほぼほぼ同じような
      アルゴリズムを座標に適用してしまえばよい。

      もうひとつ c を用意して重複判定を行うか...
      4*4 or 3*3 の board を生成, ユニークな最大の長方形を取得
      kessonnganakereba koushin

      考え方
      窪地長方形 detecting 
        1) 右下の 1 を探す
        while
          2) 左上の 1 を探す

      極端なこういう例がわかりやすい...
      11111111
      11111011
      11011111
      11111111
      1111[1]11
      10111]




        max_0_row[i] ... 各列の一番下の 0 がある行番号, max_0_row
        left_0_wall_col[i] ... max_0_row[j] > max_0_row[i] (j < i) となる列番号 j

        以下は row, col = 5, 3 の時の途中の実行結果



             0  1  2  3  4  5  6  7  8
        a = [8, 4, 2, 0, 4, 4, 4, 3, 4] <- 各列の一番下の 0 がある  行番号
        b = [0, 0, 1, 2, 0, 0, 0, 6, 0] <- a の値より大きくなる左の 列番号 
        max_s = 6

    """
    if __debug__: 
        num_of_rectangle = 0

    extended_board = extend_board(board)
    m = len(extended_board)

    lst_max_0_row = [0]*m
    lst_left_0_wall_col = [0]*m

    lst_max_0_row[0] = m-1
    max_s = 0
    for row in range(1, m-1):
        height_col = 0
        left_0_wall_col = 0
        for col in range(0, m-1):
            # 
            # 左上の値 row0, col0 を調べるために値を保存
            # 

            # その列で一番下の 0 の行
            if extended_board[row][col+1]==0:
                lst_max_0_row[col+1] = row
                
                # 左列には a[j] > a[col+1] (j < col+1) となる列番号 j が
                # 存在しないので 0
                lst_left_0_wall_col[col+1] = 0

                left_0_wall_col = col+1

            elif lst_left_0_wall_col[col+1] < left_0_wall_col:
                lst_left_0_wall_col[col+1] = left_0_wall_col

            # 真下が 0 
            if extended_board[row+1][col]==0:
                height_col = col

            # 
            # 右下の値 row1, col1 の値を検索
            # 
            if lst_max_0_row[height_col] < lst_max_0_row[col+1]:
                if __debug__: 
                    print('right bottom corner detect...')

                while lst_max_0_row[height_col] < lst_max_0_row[col+1]:
                    """
                      この条件式に合致するのはどのような時か?
                      -> 例えば row0, col0 = 3, 3 の時、右に壁を発見した時

                              V 右の壁
                      0 0 0 0 | 0 0
                      0 0 1 1 | 0 0
                      0 1 1 1 |[0]0
                      0 1 1[1]| 1 1
                      --------|----
                      0[0]1 1 | 1 1
                    """
                    row0 = lst_max_0_row[height_col] + 1
                    col0 = lst_left_0_wall_col[height_col] + 1
                    row1 = row
                    col1 = col
                    s = (row1 - row0 + 1)*(col1 - col0 + 1)

                    org_row0 = row0 - 1
                    org_col0 = col0 - 1
                    org_row1 = row1 - 1
                    org_col1 = col1 - 1

                    if s > max_s:
                        org_max_row0 = org_row0
                        org_max_col0 = org_col0
                        org_max_row1 = org_row1
                        org_max_col1 = org_col1
                        max_s = s

                
                    if __debug__:
                        num_of_rectangle += 1
                        print_debuglog(
                                    num_of_rectangle,
                                    row, col, 
                                    extended_board, 
                                    lst_max_0_row, lst_left_0_wall_col,
                                    height_col, left_0_wall_col, 
                                    row0, col0, row1, col1, s)
                    
                    height_col = lst_left_0_wall_col[height_col]
                height_col = col+1

    return max_s, org_max_row0, org_max_col0, org_max_row1, org_max_col1


def input_board():
    """
      read the board
    """
    bit_list = list(map(int, list(input())))
    n = len(bit_list)
    board = [None]*n

    board[0] = bit_list
    for i in range(1, n):
        bit_list = list(map(int, list(input())))
        board[i] = bit_list
    
    return board


def extend_board(board):
    """
      extend the board
    """
    n = len(board)
    extended_board = [None]*(n+2)

    extended_board[0] = [0]*(n+2)
    for i in range(1, n+1):
        extended_board[i] = [x for sublist in [[0], board[i-1], [0]] for x in sublist]
    extended_board[-1] = [0]*(n+2)

    return extended_board



def print_debuglog(
        num_of_rectangle,
        row, col, 
        extended_board, 
        lst_max_0_row, lst_left_0_wall_col,
        height_col, left_0_wall_col, 
        row0, col0, row1, col1, s
    ):
    print('-----')
    print('  num_of_rectangle = ' + str(num_of_rectangle))
    print('  row, col+1 = ' + str(row) + ", " + str(col+1))
    print('  row0, col0, row1, col1, s =' + str((row0, col0, row1, col1, s)));
    print('-----')
    print('extended_board = ')
    print_board(extended_board, row, col)
    print()
    print('lst_max_0_row       = ', end=''); print(lst_max_0_row)
    print('lst_left_0_wall_col = ', end=''); print(lst_left_0_wall_col)
    print('height_col          = ' + str(' '*(1+height_col*3)) + str(height_col))
    print('left_0_wall_col     = ' + str(' '*(1+left_0_wall_col*3)) + str(left_0_wall_col))
    print()
    print()
    print()


def print_board(board, row, col):
    for i in range(row):
        print('                      ', end=''); print(board[i])
    lst = board[row][:col+2]
    print('                      ', end=''); print(lst)


if __name__ == '__main__':
    print(rectangle(input_board()))

4. 動的長方形探索木

日本語で探した時の資料、結局肝心部分のソースコードが dll に入ってるからか知らないけど見れず、使えなかった…

○ ライブラリ, dll

ソースコード文字コード変換…

brew install unar
unar sample01.zip 
brew install nkf
nkf --guess sample01/rectIntsectmain.c 
nkf --overwrite -Sw sample01/rectIntsectmain.c 
nkf --overwrite -Sw sample01/長方形探索木.txt
nkf --overwrite -Sw sample01/rectIntsect.h

markdown