2D配列を長方形に解析します

Question

この例のように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＃でやりたいのですが、あらゆる種類の助けが高く評価されています。

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

事前にありがとう！

Answer 1

最小必要数の長方形の2D平面内の一連の点をカバーしようとしていると思います。 彼らは最大ポイント数がNP完全な問題であり、 http://www.almaden.ibm.com/u/kclarkson/set_cover/p.pdf （これは私のために機能します）Google検索は 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）この場合、この問題のバージョンがより制限されていないようです。あなたはおそらく紙を読み、あなたの問題のいくつかの詳細があるかもしれないということを見つけるかもしれません、この方法があなたに適用されることを意味します。一例は「長方形で領域を構築するためのアルゴリズムです。 独立性と最小生成セット 「FranzblauとKleitmanによる」 - ACMデジタルライブラリでこれを見つけました。

Answer 2

これはあなたが始めるのに役立つかもしれません。バイナリデータを数字に変換すると、これが取得されます。

0
28
56
56
56
0

.

それで、連続した等号があるところは、長方形があります。