以下問題： 給定的是任意多邊形。它應以給定半徑的最小圓圈數覆蓋100％。用給定直徑的最小圓圈數覆蓋多邊形
注意： 1）自然界必須重疊。 2）我嘗試解決任意多邊形的問題。但也欣賞CONVEX多邊形的解決方案。 3）據Im通報，這個問題是NP-hard（an algorithm to find the minimum size set cover for the Set-cover problem） 選擇：U =多邊形和S1 ... Sk =具有任意中心的圓。
我的解決方案： 我已經閱讀了一些論文，並嘗試了一些我自己的東西。我想出的最有前途的想法實際上已經在Covering an arbitrary area with circles of equal radius中指出過。
所以我想這是最好的，我很快嘗試描述我自己的想法，然後提煉我的問題。
圖片給你已經是我做什麼
IDEA和問題闡述 1.我與它們對應的六邊形和鑲嵌整個R2，即近似於圓一個不錯的主意足夠大的面積;關鍵字六邊形最接近的包裝。 （青色...細分，紅色虛線，青色六邊形的中心） 2.我將多邊形放置在此棋盤格區域的中間位置，並計算覆蓋多邊形所需的六邊形數量。
在下面的進出口試圖最小化N，這是爲覆蓋多邊形需要數ofhexagons，通過步驟圍繞步驟移動該多邊形，每個步驟之後「計數」 N
解決該問題： 所以這就是困難時（對我來說）。我不知道任何優化器能夠正確解決這個問題，因爲它們都是在多邊形移動一點之後終止並且沒有觀察到任何變化。
我的解決辦法是： 首先請注意，這是一個週期的問題： 1.多邊形可在水平方向移動x，其中的一個週期的3 * R（邊長=半徑r）六邊形。 2.多邊形可以在垂直方向y上移動，週期爲六角形的cos（2/3 * pi）的一個週期r^2 + r^2-2 * r r。 3.多邊形可以以2/3 * pi的週期旋轉phi。
這意味着，必須搜索可能解決方案的有限區域以找到最佳解決方案。 因此，我所做的是，我選擇（x，y，phi）的步長，並簡單地蠻力計算所有可能的解決方案，挑選出最佳值。
提煉我的問題 1）問題的解決是否智能化？現在我正在研究一個只鑲嵌一個非常小的區域的算法，以便儘可能少的六邊形必須被計算出來。 2）是否有更智能的優化器來解決這個問題？3）最後：我也很難找到合適的文獻，因爲我不認爲我不知道正確的關鍵詞。所以，如果任何人能夠提供給我的文學，它也會受到很多讚賞。
其實我可以繼續嘗試其他的事情，但我認爲你們中的任何一個人都不想在整個下午花點時間閱讀我的問題。
Thx提前給每個需要時間考慮的人。
墊
PS我實現MATLAB算法我
@ 1個大cricle： 這些圓的半徑給定爲在非常提到第一行，因此我不能只選擇一個大圓圈，因爲給定的半徑可能不夠大。如果1個圓圈足夠大，則說明正確 - 那麼1個圓圈就是最佳解決方案。 @circles必須走出去： 1）我在第二行中提到注1：自然界必須重疊。 2）是的，這些圈子自然也不得不超出多邊形的範圍，但是我添加了任何禁止的限制。這正是你從上下文中所暗示的。 因此，ID說我的問題是明確定義的 –
簡而言之：只要仔細閱讀前3行，並回答所有問題 –
@MatthiasHofmair：你說得對，沒有提到任何限制超出多邊形這不是包裝問題）。那麼對於這種情況，1個大圓圈是一個簡單的解決方案，其中圓的半徑足夠大以覆蓋所有的多邊形。問題是明確的，可以解決的。 – nrz