近似最小集合覆蓋的Python

我必須列出每個列表包含一個多邊形的邊長的列表。例如：近似最小集合覆蓋的Python

[[0, 1, 2], 
[0, 1.1, 2], 
[0, 1.2, 2], 
[0, 1.3, 2], 
[4.5, 1.1], 
[4.4, 1.1], 
[5, 1, 2], 
[5, 1.1, 2], 
[5, 1.2, 2] 
[6, 1, 7, 4], 
[6, 1.1, 7, 4.1]]

我希望能夠在這個意義上找到了大約最小「蓋」，對於「覆蓋」的每一個元素都它的值是它的元素在規定範圍覆蓋。例如，如果公差爲0.1給出的列表上面我想獲得：

[[0, 1, 2], 
[0, 1.2, 2], 
[4, 1], 
[4.5, 1.1], 
[5, 1.1, 2], 
[6, 1, 7, 4],]

我有些新的Python，所以希望我的術語的使用是不是太遙遠。也許這有助於解釋我的動機。我是一名設計師，試圖優化給定的表面面板。由於製造公差帶有長度相差一定數量的邊的面板可以被認爲是相同的（在上面的示例中，所有邊可以相差0.1，並且仍然被認爲是相同的）。我試圖找到可以生產並仍然鑲嵌表面的最小組鑲板。

來源

2014-09-22 Jon

你有沒有試圖解決這個問題？請記住，這不是一個代碼寫入服務。 – 2014-09-22 20:26:02

你有一個子列表'[4,1]'。這意味着一個雙面多邊形。現在我很困惑 – inspectorG4dget 2014-09-22 20:38:08

你所有的最終值是你的容差值的倍數（或者你願意改變他們，以便他們）？如果是這樣，你可以簡單地舍入值，然後做一個'set'來消除重複。 – Blckknght 2014-09-22 21:43:16

要在這裏找到最佳的解決方案將是計算相當困難 - 你似乎在要求的東西，但它不會是完美的。

本作的休息，我將討論算法的一維的情況下，理由是它的簡單來形容，但你可以擴展算法爲3D。我宣佈「範圍」爲[最小，最大]。

對於每一個點，請執行下列操作：
- 檢查，看看範圍列表如果點落在他們
之一----如果它，使該系列目前[MAX（分鐘，點間隔），min（最大，點+間隔）]。
----如果它沒有，添加一個新的範圍[點區間，點+間隔]
完成後，你的輸出點列表是每個範圍的中心。

的這裏的想法是表示每個點，因爲它在適合的可接受的範圍。一旦你的，任何重疊範圍可以被減少到它們的交點，因爲在該交叉點的任何位置是可以接受的兩個初始點。該過程可以繼續，直到剩餘的範圍不重疊。

來源

2014-09-22 20:38:25 zebediah49

近似最小集合覆蓋的Python

回答

相關問題