我在2D空間中有一組矩形和任意形狀。該形狀不是多邊形所必需的（它可以是一個圓形），並且矩形具有不同的寬度和高度。任務是儘可能接近矩形的形狀。我無法更改矩形尺寸，但旋轉是允許的。用給定的一組矩形填充任意的2D形狀
這聽起來非常相似，packing problem和覆蓋問題，但覆蓋面積不是矩形...
我想這是NP問題，我敢肯定，應該有一些文件，顯示良好的啓發式解決呢，但我不知道谷歌是什麼？我應該從哪裏開始？
更新：一個想法剛進入我的腦海，但我不確定是否值得調查。如果我們考慮將形狀限定爲充滿水的物理模型會怎麼樣。每個矩形都被認爲是具有大小的帶正電的粒子。現在放下最小的矩形。然後在隨機點按大小放下下一個。如果矩形太近，它們會相互排斥。繼續添加矩形，直到全部使用。這個方法能工作嗎？
我認爲你可以尋找打包和自動佈局生成算法。自動VLSI佈局生成算法可能需要類似的東西，就像紡織布局的問題...
這篇文章Hegedüs: Algorithms for covering polygons by rectangles似乎解決了類似的問題。既然這篇論文是從1982年開始的，那麼看看papers which cite this one可能會很有趣。此外，this meeting似乎在討論與此相關的研究問題，所以可能是關鍵字或名稱研究人員在這個想法的起點。
我不知道計算幾何的研究是否有針對您的特定問題的算法，或者這些算法是否足夠容易/足以實施。如果我不能查看以前的工作，就必須這樣做，這就是我的方法。這只是一個方向，迄今爲止還不是一個解決方案...
將其表述爲優化問題。你有離散變量，你選擇哪個矩形（是或否）和連續變量（三角形的位置和方向）。現在你可以設置兩個獨立的優化：一個離散優化選擇矩形;並且一旦給出矩形，就會連續優化位置和方向。插入這兩個優化。當然，困難在於優化的制定，以及設計錯誤能量，使其不會陷入一些奇怪的配置（局部最小值）。我試圖得到作爲least squares問題的連續性，以便我可以使用標準優化庫。
我覺得這個問題適合用遺傳算法和/或進化策略算法求解。我在某種進化策略算法的幫助下完成了類似的盒裝問題。檢查出in my blog。
所以，如果你會用這樣的方法 - 編碼成染色體框：
然後嘗試功能 -
儘量減少這種健身y = w1 * box_intersection_area + W2 * box_area_out_of_shape + W3 * average_circle_radius_in_free_space
選擇權重W1，W2，W3等影響因素的重要性。當遺傳算法會找到部分解決方案 - 刪除仍然重疊在一起或變形的盒子 - 並且您至少會得到合法的（但不是最佳的）解決方案。
祝你好運在這個有趣的問題！
這確實是NP難題，因爲它具有高科技應用，合理有效的近似策略甚至不在專利中，更不用說發表的論文。
有限的預算可以做的最好的事情是從限制問題開始。假設所有的矩形都是完全相同的，假設所有矩形是標準矩形的二進制子部分也是允許的，因爲您可以有效地預先打包它們以適合您的核心部門。對於額外的點，你也可以形成幾個固定的模式來粘合核心矩形，以覆蓋幾個大不相同的比例的形狀。假設只要其餘部分（預填充和膠合模式）保持不變，您就可以更改標準矩形/單元格的尺寸 - 這使您可以根據給定的矩形決定核心矩形的近似尺寸。
現在你可以玩高寬比來近似這種有限系統可以保證的誤差。對於第一次迭代，假定它可以具有50％的錯誤，並具有簡單的細分模式，然後改變模式以減少錯誤，但不增加預填充的漸近複雜性。在一天結束時，您總是隻將給定的矩形分配給您的預先計算好的和現在固定的網格和二進制子分區 - 這意味着您根本沒有嘗試進行佈局或回溯 - 您始終對第一個近似值感到滿意適合網格。
從事定義與您的模式很好地包裝在一起的矩形類的工作 - 這又是爲了保持整個過程反轉 - 您從未嘗試真正適合您所給予的東西 - 您正在定義必須給予的東西以便冷杉 - 那麼你打其餘的錯誤，因爲它是近似。
然後你可以嘗試做更多一點，但不要太多 - 任何滑入回溯或釘牢任意小錯誤，它是指數。
如果你在一個研究機構，可以得到一些超級計算機的時間 - 運行一系列詳盡的搜索與病理混合，那裏看看最佳包裝可能是什麼樣子，看看你是否可以得到更多的細分模式和/或矩形集合的類。
這應該是足夠的前2年或研究:-)
你想盡可能密集打包？或者儘可能地逼近形狀？有沒有一個數學函數可以用來優化，還是更美觀？ – brainjam 2010-08-20 20:03:26
關於這個帶電荷的矩形方法，它可能不一定會給出最佳配置，因爲我們首先使用隨機化來放棄它們。 – Lazer 2010-08-23 08:05:38
什麼是優先級 - 追蹤邊界或填充形狀？我的意思是，如果矩形完美地追蹤邊界，但是在某個地方的中間留下了一個洞，那麼這樣可以嗎？ – Lazer 2010-08-23 08:07:25