在多邊形內擬合矩形的算法

我有一種切割問題。有一個不規則的多邊形，沒有任何孔和一個標準大小的矩形瓷磚及其值的列表。在多邊形內擬合矩形的算法

我想要一個高效的算法來找到適合這個多邊形的單個最有價值的瓷磚;或者一個算法，它只是說一個單獨的tile可以放在多邊形內部。對於不到100個頂點的不規則多邊形，它應該在確定的時間內運行。

請考慮你可以旋轉多邊形和瓷磚。讚賞凸和非凸多邊形的答案/提示。

2013-03-13 aisa

上[多邊形內部矩形]谷歌搜索將返回了一些有趣的結果，包括該研究論文的源代碼：http://www.mpi-inf.mpg.de/~ jeschmid/public/Knauer2012.pdf和一些SO問題：http://stackoverflow.com/q/610462/56778和http://stackoverflow.com/q/10214829/56778 – 2013-03-13 12:55:54

你提到你的多邊形是不規則的。它們是凸的嗎？ – phs 2013-03-13 20:12:23

當然我之前已經使用過Google。但謝謝你的指導。我編輯了這個問題。 – aisa 2013-03-16 09:19:31

許多絕望的搜索後，我覺得沒有任何特定的算法針對此問題。直到，我發現this old paper about polygon containment problem.
這個提到的文章，提出了一個非常好的算法來考慮如果一個多邊形與n點可以適合多邊形與米點或不。
對於兩個可移動和可旋轉的2D多邊形，該算法通常爲O（n^3 m^3（n + m）log（n + m））。

我希望它可以幫助你，如果你正在計算幾何中尋找這樣一個不規則的算法。

來源

2013-08-13 20:13:16 aisa

聲明：我從來沒有讀過任何有關這方面的文獻，所以可能有更好的方法來做到這一點。這個解決方案正是我在閱讀完你的問題後想到的。

一個矩形，有兩個重要的測量 - 它的高度，現在，如果我們開始與多邊形和矩形它的寬度

：

polygon and rectangle

1：去身邊的多邊形的周長和請注意所有矩形的高度將適合多邊形（您可以將其存儲爲多邊形*）：

where will the hight fit?

2：去身邊剛剛完成的新多邊形的周長，並採取所有地方的矩形寬度將適合在多邊形的說明（同樣，你可以在此存儲爲一個多邊形）：

3：矩形應該適應這種新的多邊形內（只是要小心，你正確定位多邊形內部的矩形，因爲這是一個多邊形的 - 而不是一個矩形。如果您將矩形的左上角節點與此新多邊形的左上角對齊，則應該沒問題）

4：如果沒有找到矩形可以放入的區域，則將多邊形旋轉一對度，然後再試一次。

*注：在某些多邊形，你會得到多個地方的矩形可以裝：

來源

2013-04-09 20:18:15 stormCloud

感謝您的回答;但這不是我想要的。我想要一個算法來解決**矩形問題**的多邊形遏制問題。 – aisa 2013-05-01 08:52:11

@aisa我的算法會告訴你一個矩形在每個給定的旋轉中將在多邊形內適合多少個不同的位置。所以如果地方的數量是零，矩形將不適合在那個旋轉。如果位置數量>零，矩形將適合該旋轉。所以用一個簡單的條件語句，你可以檢查你需要什麼。除非您真的想要解決這個問題，因爲您的公差極其嚴格，您應該能夠將您算法的每次迭代所需的度數調整爲您的方案。 – stormCloud 2013-05-01 22:37:30

這可能有幫助。它配備了編寫的Java

http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/

來源

2013-10-11 04:45:11

感謝您的幫助。但我提到多邊形可以旋轉。它不一定是凸面的。無論如何，再次感謝您的鏈接。 – aisa 2015-02-17 08:08:06

在多邊形內擬合矩形的算法

回答

相關問題