algorithm - 長方形を囲む最小面積?

Question

次の問題を解決するためのアルゴリズムのアイデアが必要です (私はすでにいくつかの個人的な解決策を試しましたが、それらは最適ではないようです)

マークされたゾーンとマークされていないゾーン (マトリックス形式) と、任意の形または位置で操作できる 2 つの四角形を含むサーフェスが与えられた場合、最小限のサーフェスを維持しながらすべてのマークされたゾーンをカバーするような四角形の可能な形状と位置を見つけます。可能エリア。

Answer 1

この回答は、長方形を回転できず、辺が常に x 軸と y 軸に平行であると仮定しています。

まず、領域全体を囲む四角形を見つけます。そのためのアルゴリズムは次のようになります (原点が左上にあると仮定します):

For each marked spot in the matrix:
    if spot.x < rectangle.left:
        rectangle.left = spot.x
    if spot.x > rectangle.right:
        rectangle.left = spot.x
    if spot.y < rectangle.top:
        rectangle.left = spot.x
    if spot.y < rectangle.bottom:
        rectangle.left = spot.x

次に、次のように最大の水平ギャップを見つけます。

largest_gap = -1
For each column in matrix:
     last_marked_spot = 0, 0
     For each spot in column:
         if spot.marked:
             if spot.x - last_marked_spot.x > largest_gap:
                 largest_gap = spot.x - last_marked_spot.x
             last_marked_spot = spot

縦の隙間も同様です。次に、どのギャップが最大かを確認します。

次に、最大のギャップをセパレータとして使用して、すべてを含む長方形を 2 つの部分に分割します。最後のステップは、2 つの長方形を折​​りたたむことです (上のアルゴリズムの逆を使用)。