將許多矩形組合成更少的矩形

我想要將許多不重疊的矩形壓縮成更大的矩形時它們相鄰。我現在的算法將許多矩形組合成更少的矩形

僞代碼：

do 
    compress horizontally using sweep and prune 
    compress horizontal output vertically using sweep and prune 
while (this output is small than previous output)

這裏有一個link to sweep and prune。

這是行之有效的，但我想知道是否有辦法導致更少的矩形輸出。我認爲這比我現在做的更復雜。

來源

2013-07-16 William Morrison

我根據新的標準，更新了我的答案。 – Ted

Downvoter，原因？ –

所以這聽起來像是你的問題是你有矩形之間的小間隙，防止他們被收集到一塊。如果您有權訪問掃描和剪除方法的源代碼，則可以將「緩衝區」添加到「重疊」測試，但我認爲考慮使用R-Tree會更理想。這將索引的矩形空間而不對間隙等

R-Tree Wiki

與限制搞亂這裏是由Sellis等相關論文。人。描述R +樹：

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=50ECCC47148D9121A4B39EC1220D9FB2?doi=10.1.1.45.3272&rep=rep1&type=pdf

這裏是一個C＃實現的的R-樹

http://sourceforge.net/projects/cspatialindexrt/

[編輯 - 意見後1]

因此，讓我看看，如果我可以捕捉當前的問題。

矩形連接成水平/垂直鄰接測試的通過。
如果兩者的相鄰邊界相等，則只加入矩形。
任何連接的中間結果也必須形成一個有效的矩形。
結果是非最佳的，因爲加入的順序。

我想你實際上是在尋找一個直線多邊形的矩形的最小解剖。第一步是將所有感人的矩形連接在一起，而不管它們是否構成矩形。我認爲你在這個過程的每個步驟的中間階段遇到問題，也需要完整的矩形解構，導致次優結果。如果將它們合併爲一個直線多邊形，則可以使用圖論機制。

Minimum Dissection into Rectangles of a Rectilinear Polygon

您可以通過David Eppstein

退房Graph-Theoretic Solutions to Computational Geometry Problems或調查Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping通過Gareth Rees

來源

2013-07-21 15:12:08 Ted

感謝您的回覆！ Rtree看起來很有趣，但我不認爲它適用於我。這裏如果有間隙，矩形不能合併。輸出應該與輸入具有相同的面積並覆蓋完全相同的地。 –

第二個鏈接聽起來像我正在尋找的。一旦我有時間閱讀它，我會回覆或接受。我很感謝你在這裏的時間。 –

這正是我所尋找的，我無法感謝你。希望解決方案不會超出我的深度。複雜的東西。 –

將許多矩形組合成更少的矩形

回答

相關問題