近似最小集合覆盖的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

回答

相关问题