Не знаю как правильно сформулировать запрос для такой задачи. Есть фигура в двухмерном пространстве, произвольной неправильной формы, и есть произвольные фигуры которыми нужно максимально заполнить эту площадь, с минимальным остатком свободного места. Притом часть фигур являются обязательными, а остаток пространства заполнить необязательными по максимуму. Все фигуры хоть и имеют произвольную форму, но они интегральны, и кратны пикселям. Такой себе тетрис. Что-то готовое уже должно однозначно быть, ведь задача тривиальна и изобретать велосипед не нужно. Может какие-то швеи используют что-то такое чтоб раскроить полотно с минимальным количеством остатка. Буду признателен за кусок кода на любой языке программирования или готовую библиотеку
На входе задается
1. Форма контейнера
2. Формы всех возможных фигур
3. Обязательные фигуры и количество их необходимых копий в контейнере
На выходе получаем
1. Оптимальное расположение всех фигур
Что-то вроде такого условия
<?php
//Последовательности пикселей
//Отрицательные числа - последовательность пустых пикселей
$input = [
[3],
[4],
[4],
[4],
[2],
[2],
];
$figures = [
"a" => [[2], [2]], //Куб
"b" => [[1], [1], [2]], //L
"c" => [[-1, 1], [2]], //J
"d" => [[4]], //Линия
"e" => [[-1, 1], [1]],
];
//Обязательные фигуры, с количеством
$require = [
"a" => 1,
"d" => 1,
];
//Фигуры которые используеются для остаточного заполнения
$optional = [
"a", "b", "c",
];
//Поиск
function search($input, $figures, $require, $optional) {
//TODO Магия
return [
["b", 0, 0],
["a", 1, 0],
["c", 3, 1],
["d", 0, 3],
["a", 0, 4],
];
}
print_r(search($input, $figures, $require, $optional));
Простой
