Приблизительный минимальный набор Обложка Python

Question

У меня есть список списков, каждый список содержит длины ребер многоугольника. Например:

[[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]]

Я хотел бы иметь возможность найти приблизительно минимальное "покрытие" в том смысле, что для каждого элемента "покрытия" все его значения находятся в пределах определенного допуска элементов, которые он покрывает. Например, если допуск равен.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 и при этом считаться одинаковыми). Я пытаюсь найти минимальный набор панелей, которые можно было бы изготовить, и при этом все еще покрывать поверхность панелями.

Answer 1

Найти оптимальное решение здесь будет довольно сложно с вычислительной точки зрения - кажется, вы чего-то просите, но оно не должно быть идеальным.

В остальном я собираюсь обсудить предложенный алгоритм для одномерного случая на том основании, что его проще описать, но вы можете расширить алгоритм до 3d. Я объявляю "диапазон" [мин, макс].

Для каждой точки сделайте следующее:
- Проверьте список диапазонов, чтобы увидеть, попадает ли точка в один из них.
---- если это так, сделайте этот диапазон сейчас [max(min, точка-интервал), min(max, точка + интервал)].
---- если нет, добавьте новый диапазон [точка-интервал, точка + интервал]
После завершения список выходных точек становится центром каждого диапазона.

Идея здесь состоит в том, чтобы представить каждую точку как приемлемый диапазон, в который она вписывается. Как только вы это сделаете, любые перекрывающиеся диапазоны могут быть сведены к их пересечению, поскольку любое место в этом пересечении приемлемо для обеих начальных точек. Этот процесс можно продолжать до тех пор, пока оставшиеся диапазоны не пересекаются.