3

この例のように、2D配列を可能な限り少ない長方形に変換する方法を探しています。

       X
    12345678
    --------
  1|00000000
  2|00011100
  3|00111000
Y 4|00111000
  5|00111000
  6|00000000

長方形のコーナー座標へ：

（x1、y1）;（x2; y2）テンプレートに従う

rectangle #1 (4,2);(6,2)
rectangle #2 (3,3);(5,5)

以前にも同様の質問がありましたが、残念ながら、回答に記載されているリンクが壊れており、確認できなくなりました。

これをC＃で実行したいのですが、どんな種類の助けもありがたいです。

（可能な限り少ない長方形である必要はありませんが、少ないほど良いです:)）

前もって感謝します！

4

2 に答える 2

2

必要最小限の長方形で2D平面の点のセットをカバーしようとしていると思います。最大数のポイントをカバーするようにk個の長方形を検索するための回答は、これはNP完全問題であり、http：//www.almaden.ibm.com/u/kclarkson/set_cover/p.pdf（これは私のために働く）グーグル検索はhttp://2011.cccg.ca/PDFschedule/papers/paper102.pdfを見つけます。

長方形のカバーがNP完全であることに同意する論文がありますが、実際にはそれを証明していません。これに関する参照は、非常にわかりにくいようです-https ://cstheory.stackexchange.com/questions/3957/prove-that-the-problem- of-rectilinear-picture-compression-is-np-complete

私がこれらの文書から取ったものはこれです：

1）大きな問題に対して絶対的に最良の答えを得る手頃な方法がある可能性は低いので、ある意味で小さな問題に対して正確な答えを得るには、可能な限りすべてを使い果たすことによって、多くの時間を費やす必要があります。代替案、または分枝限定法のようなものを使用するか、欲張り検索、ビームサーチ、限定不一致検索などの手頃な方法で解決しますが、絶対に最良の答えが得られるとは限りません。

2）この場合、NP完全ではないこの問題のより制限されたバージョンがあるようです。あなたはおそらく論文を読んで、この方法があなたに適用されることを意味するあなたの問題のいくらかの詳細があることに気付くかもしれません。一例として、FranzblauとKleitmanによる「長方形で領域を構築するためのアルゴリズム：間隔のコレクションの独立性と最小生成セット*」があります。これはACMデジタルライブラリで見つかりましたが、一般的にアクセスできるかどうかはわかりません。制限されたポリゴンのセットに対して機能します。

于 2012-09-30T05:01:06.470 に答える
-1

これはあなたが始めるのを助けるかもしれません。バイナリデータを数値に変換すると、次のようになります。

0
28
56
56
56
0

したがって、連続する等しい数がある場合は常に、長方形があります。

于 2012-09-30T02:38:36.130 に答える