Необходимо написать мини-программку, которая рассчитывала бы наиболее экономичную раскладку материала. Дано: фигура произвольной формы и прямоугольный лист материала. Необходимо разложить максимально возможное количество данной фигуры на этом листе так, чтобы между ними оставалось расстояние 2-3мм (можно регулировать). В какую сторону копать? На чем можно реализовать? Хотелось бы на Python, так как более-менее знаю только его.
Ответ
В общем виде эта задача является труднорешаемой, и не имеет эффективного алгоритма решения в принципе (его не существует в природе). Если материал Ваш имеет какую-то особую форму, то ещё можно что-то сделать, а если форма произвольная, то можно попробовать эвристики. Копайте по таким ключевым словам: "задача о плоскостном раскрое" или "Cutting stock problem". На русском, сразу говорю, - мало что полезного найдёте. На английском ищите задачу Cutting stock problem на прямоугольных полосках с бесконечной длиной (или высотой). Там суть почти всех эвристик в том, что делается попытка разместить N фигур на прямоугольной полоске минимальной длиной (высотой) и с фиксированной высотой (длиной). Соответственно, если у вас ширина (высота) уже заданы заранее, то задача о максимальном числе N решается бинарным поиском. Сами же эвристики настолько объёмы по изложению, что расписывать их здесь не смогу.
Отвечаю на второй вопрос: реализовать можно на чём угодно, когда знаешь алгоритм. Готовые библиотеки мне лично не известны. Вообще, это серьёзная научная проблема, коей занимались разные институты (особенно в советское время), нужно довольно хорошо владеть программированием, чтобы всё здесь правильно закодировать.
Комментариев нет:
Отправить комментарий