1

我有一个列表列表，每个列表都包含多边形的边长。例如：

[[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 并且仍然被认为是相同的）。我正在尝试找到最少的一组可以生产的面板，并且仍然可以对表面进行面板化。

4

1 回答 1

0

在这里找到一个最佳解决方案在计算上是相当困难的——你似乎在要求一些东西，但它不一定是完美的。

在接下来的内容中，我将讨论针对 1D 情况提出的算法，理由是它更易于描述，但您可以将算法扩展到 3d。我将“范围”声明为 [min,max]。

对于每个点，执行以下操作：
--检查范围列表以查看该点是否属于其中之一
----如果是，则现在使该范围 [max(min,point-interval), min(max ,点+间隔）]。
----如果没有，添加一个新的范围 [point-interval, point+interval]
一旦完成，你的输出点列表就是每个范围的中心。

这里的想法是将每个点表示为它适合的可接受范围。一旦你有了它，任何重叠范围都可以减少到它们的交点，因为该交点中的任何地方都是两个初始点都可以接受的。这个过程可以继续，直到剩余的范围不重叠。

于 2014-09-22T20:38:25.377 回答