解析二維數組矩形

我正在尋找一種方法來轉換一個二維數組，以儘可能少的矩形就像這個例子：解析二維數組矩形

 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＃中做到這一點，但任何形式的幫助表示讚賞。

（它甚至沒有要儘可能少的矩形，但更好:)較少）

提前感謝！

來源

2012-09-30 theAdam

這兩種表示之間沒有明顯的關係。你會詳細說明嗎？ – casperOne

我編輯了OP，我希望現在更容易理解，對於混淆抱歉。 – theAdam

兩點如何形成一個矩形？我知道你試圖在那裏表達一些明顯的東西，但這並不直觀。 – swiftgp

我認爲你正試圖用最小的矩形數量覆蓋2D平面中的一組點。對Find k rectangles so that they cover the maximum number of points的回答表示這是一個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）對於大問題，獲得絕對最佳答案的方法不太可行，因此您可能需要花費大量時間才能針對某些意義上的小問題獲得確切答案，方法是耗盡所有可能的或者可能使用分支和邊界之類的東西，或者選擇負擔得起的方法 - 比如貪婪的搜索或者波束搜索或者有限的差異搜索 - h不保證給你絕對最好的答案。

2）在這種情況下，似乎有更多限制版本的這個問題不是NP完全的。您可能會閱讀一篇論文，發現您的問題存在一些細節，這意味着此方法適用於您。一個例子是「用於構建矩形區域的一種算法：獨立性和最小生成集合對於期間的集合*」Franzblau和Kleitman--我在ACM數字圖書館中發現了這一點 - 但我不知道它是否一般無障礙。它適用於一組受限制的多邊形。

來源

2012-09-30 05:01:06 mcdowella

是的，這粗略地定義了我的問題，但是在快速瀏覽這些文檔之後，他們並沒有真正提供一種算法來解決問題本身（至少沒有我能夠在C＃中理解和再現的）。不過謝謝，無論如何，我一定會閱讀它們，看看我能不能做點什麼。 – theAdam

我在我的評論中編輯了這些論文的相關性 - 這大部分是我發現某些東西是NP完全的我通常的反應。 – mcdowella

謝謝，我想我會自己寫一個優化，然後檢查高度爲1的矩形，當我在數組中循環時，它會檢查連續的行。 – theAdam

這可能會幫助您開始。如果轉換爲二進制數據的數字，你會得到這樣的：

那麼，曾經有連續的數量相等，有一個矩形。

來源

2012-09-30 02:38:36

不錯的想法，但我認爲它不會工作，如果有多個矩形部分在行中。 – theAdam

遲到的新要求？我確信這從來沒有發生過。 –

解析二維數組矩形

回答

相關問題