Будни автоматизации или "мне нужна программка для 3D упаковки"

31.07.14

Разработка - Математика и алгоритмы

Автоматизация отечественных предприятий, которой приходиться заниматься, это нужная и высокооплачиваемая, но довольно нервная работа. Выручает юмор. Например, при общении с требовательным клиентом можно вспомнить анекдот: "Держась руками за стену, на ногах еле стоит мужик. К нему пристает ребенок: "Ну, папа, пожалуйста, сделай мне кораблик!", папа отвечает: "Ага! - Сейчас все брошу и пойду делать тебе кораблик!". Про один такой сделанный для клиента "кораблик" и хочется рассказать. Надеюсь, совместное погружение в теплое ламповое (то есть клиентоориентированное) программирование доставит Вам положительные эмоции, да и задача попалась интересная. Поплыли?

Началось все с письма клиента, в котором говорилось что крупный сетевой ритейлер Х (все его знают) потребовал, чтобы отгрузки в его адрес осуществлялись не на паллетах, а в коробах заданного размера. Поэтому менеджеру, курирующему данного клиента, требуется "программка", которая по составу разноразмерных упаковок в заказе определит  необходимое количество коробов и распечатает упаковочные листы. Письмо сопровождалось просьбой не затягивать решение вопроса, поскольку момент перехода на новую систему отгрузок вот-вот наступит, а штрафные санкции могут стоить больше, чем новый автомобиль генерального. Стоимость автомобиля была известна, так как «Феррари» числилась в списке основных средств. Поэтому задача нехотя (всего одно рабочее место из почти пары сотен) была взята в работу и поставлена на контроль. Хотя более массовых задач в тот момент было море: только-только запущено свежеразработанное ПО для терминалов сбора данных на складе сырья, в режиме ошпаренной кошки велась разработка приложения для перевода торговых представителей с КПК на планшеты, отлаживалась система регистрации и контроля перемещений паллет с готовой продукцией и тому подобное.

Беглый анализ показал, что задача “container loading” является NP-полной. Объяснить это клиенту, который регулярно капризным голосом названивал с вопросом "когда же будет моя программка", мы не могли и не пытались. А Вы попробуйте сказать симпатичной девушке-менеджеру по работе с клиентами, что ее задача какая-то там полная. О чем она в первую очередь подумает? И какие у вас после этого шансы? В общем, наивная вера наших клиентов в безграничные возможности компьютеров и всемогущество программистов сыграла в тот раз с нами очередную шутку. Но нужно было выкручиваться и мы это сделали.

Чтобы объяснить приведенное далее решение требуется иметь в виду еще одно обстоятельство. Фреймворк, с которым мы работаем, основан на скриптовом языке. Хотя язык достаточно гибок и обвешен по принципу рождественской елки всякими хлопушками и погремушками, включая даже методы математической статистики, он не очень хорошо приспособлен для задач с объемными вычислениями. Обычный цикл у нас выполняется гораздо дольше, чем в компилируемом языке. Поэтому простые, но массовые вычисления бывает удобнее делать на стороне сервера непосредственно на уровне СУБД. Для работы с базой данных у нас используется язык, очень похожий на T-SQL. Поэтому не сомневаюсь, что приведенный далее код будет всем понятен.

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

В общем, вы поняли, что мы использовали "жадный" алгоритм. Кстати, видимо, увидев это неосторожно написанное слово в листе учета рабочего времени, главный бухгалтер потом долго ворчала и не хотела подписывать счет за переработанные часы.

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

Итак, сначала получаем таблицу чисел от 0 до 255 каскадным возведением в степень таблицы из 0 и 1.

SELECT 0 AS x
	INTO R1                                 
UNION
SELECT 1;

SELECT L.x + 2 * H.x AS x
	INTO R2
	FROM R1 AS L, R1 AS H;

SELECT L.x + 4 * H.x AS x
	INTO R4
	FROM R2 AS L, R2 AS H;

SELECT L.x + 16 * H.x AS x
	INTO R8
	FROM R4 AS L, R4 AS H;

Затем получаем таблицу всех возможных вращений упаковок. Кстати, интересная задача, чтобы проверить свое знание TSQL. Возможно, это новый паззл SQL для Joe Celko!

SELECT id, CASE x WHEN 0 THEN d0 WHEN 1 THEN d1 WHEN 2 THEN d2 END AS dx, x
	INTO Scan
	FROM Items, R2
	WHERE x < 3;
 
SELECT DISTINCT B0.id, B0.dx AS d0, B1.dx AS d1, B2.dx AS d2
	INTO Spin
	FROM Scan AS B0
		JOIN Scan AS B1 ON B0.id = B1.id
		JOIN Scan AS B2 ON B0.id = B2.id
	WHERE NOT(B0.x = B1.x OR B0.x = B2.x OR B1.x = B2.x);

Наконец, инициализируем таблицу решений, умножая координаты сетки на таблицу вращений.

SELECT FromLeft.x AS d0l, FromBack.x AS d1l, FromLeft.x + d0 AS d0h, FromBack.x + d1 AS d1h, 0 AS d2l, d2 AS d2h, 0 AS v, d0 * d1 AS s, id
	INTO Vista
	FROM R8 AS FromLeft, R8 AS FromBack, Spin
	WHERE FromLeft.x + d0 < = &Width AND FromBack.x + d1 < = &Depth AND d2 < = &Height;

 

Теперь выполняем цикл:

Для выбора лучшего варианта используется следующий запрос.

SELECT TOP 1 id, d0l, d1l, d2l, d0h, d1h, d2 
	FROM Vista 
	WHERE d2l + d2 < = &Height 
	ORDER BY s * d2l - v, s * d2 DESC, d2l + d2, d0l, d1l, d0h;

 

То есть на очередном шаге для укладки в короб по этому правилу выбирается упаковка, минимально закрывающая под собой незанятый объем. При равных условиях закрываемой пустоты выбирается упаковка максимального объема, минимально поднимающая верхний уровень упаковок в коробе, с самым левым краем, с самым дальним краем, с самым дальним фронтом. Впрочем, правило легко изменить, изменив порядок сортировки. 

Изменение таблицы решений с учетом того, что некоторое место в коробе становится занятым, делается так:

SELECT Vi.d0l, Vi.d1l
, ISNULL(CASE WHEN It.d2l + It.d2 > Vi.d2l THEN It.d2l + It.d2 END, Vi.d2l) AS d2l
, Vi.d0h, Vi.d1h, Vi.d2
, Vi.v + ISNULL((CASE WHEN It.d1l < Vi.d1l THEN It.d1l ELSE Vi.d1l END - CASE	WHEN It.d0l > Vi.d0l THEN It.d0l ELSE Vi.d0l END) 
* (CASE	WHEN It.d1h < Vi.d1h THEN It.d1h ELSE Vi.d1h END - CASE	WHEN It.d1l > Vi.d1l THEN It.d1l ELSE Vi.d1l END) * It.d2, 0) AS v
, Vi.s,	Vi.id
	FROM Vista AS Vi
		LEFT JOIN Items AS It
		ON (Vi.d1l < = It.d1l AND It.d1l < Vi.d1h OR It.d1l < = Vi.d1l AND Vi.d1l < It.d1h)
			AND (Vi.d0l < = It.d0l AND It.d0l < Vi.d0h OR It.d0l < = Vi.d0l AND Vi.d0l < It.d0h)
	WHERE Vi.id <> &id AND It.id = &id;

 

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

Вот,  в общем-то, и все.

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

Ниже приведен скриншот упаковочного листа, использованного при отладке.

Скриншот упаковочного листа

Настоящий упаковочный лист выглядит довольно скучно: графика 2,5Д упаковщикам оказалась не нужной. Собственно результат работы представляет собой просто еще одну печатную форму, подключаемую к заказу. Работает на типичных заказах данного конкретного клиента достаточно быстро.

В общем, клиент в лице девушки-менеджера остался доволен. Правда, не так, чтобы очень. А вот почему? Вряд ли ее могла расстроить инструкция к программке, в которой говорилось, что она работает только с толстым клиентом в обычных формах (это была десятая редакция). Мы ведь все знаем, что большинство наших клиентов никогда не открывают инструкций. В общем, разгадка мыслей отдельных пользователей это вам не «container loading», а действительно неразрешимая проблема.

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

P.S.: Здесь все правда и ничего не выдумано - коллеги не дадут соврать. Причем наиболее глубокое впечатление почему-то осталось у тех, кого я подвозил тогда на своей синей импрезе. Все запомнили число 200, но это были отнюдь не достигнутые проценты утилизации объема короба. - Вот такой парадокс психологии!

container loading упаковка

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1715    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4316    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7344    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7818    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4414    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8793    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7713    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. ildarovich 7846 24.03.14 20:28 Сейчас в теме
Эта статья написана для публикации на сайте habrahabr.ru, поэтому запросы были переведены на английский.
DrAku1a; support; Evil Beaver; +3 Ответить
2. AlX0id 24.03.14 23:40 Сейчас в теме
(1)
И именно поэтому вот таким вот незамысловатым образом вы описываете 1с? ))
Фреймворк, с которым мы работаем, основан на скриптовом языке. Хотя язык достаточно гибок и обвешен по принципу рождественской елки всякими хлопушками и погремушками, включая даже методы математической статистики, он не очень хорошо приспособлен для задач с объемными вычислениями. Обычный цикл у нас выполняется гораздо дольше, чем в компилируемом языке. Поэтому простые, но массовые вычисления бывает удобнее делать на стороне сервера непосредственно на уровне СУБД. Для работы с базой данных у нас используется язык, очень похожий на T-SQL.
AnatolPopov; simuljakr; master555; DrAku1a; Dionis; dabu-dabu; naumenko_alex; tarassov; hotey; smit1c; +10 Ответить
5. yukon 143 25.03.14 14:15 Сейчас в теме
(2) AlX0id,
И именно поэтому вот таким вот незамысловатым образом вы описываете 1с?


Мне тоже понравилось. Описание просто шикарное.
35. Дмитрий74Чел 234 04.04.14 08:21 Сейчас в теме
(1) Я уж хотел написать "и что эта статья с Хабра делает на Инфостарте"? :-)
123. пользователь 17.02.21 14:22
Сообщение было скрыто модератором.
...
3. Новенький_2209 24.03.14 23:57 Сейчас в теме
Причем наиболее глубокое впечатление почему-то осталось у тех, кого я подвозил тогда на своей синей импрезе. Все запомнили число 200, но это были отнюдь не достигнутые проценты утилизации объема короба. - Вот такой парадокс психологии!


Кто водит из вас авто? Вспомните, как часто у вас такое наблюдается - сели в машину ...вышли из машины. Вопрос - а что в дороге то хоть было? Вот реально - вы ее хоть помните? Угу, 10 раз. Вы едете на автопилоте. Ваш ум занят миллиардами мыслей, которые со скоростью света проносятся, поглощая вас еще сильнее. Какая дорога? "Не знаю такую!". А теперь задумайтесь, сколько времени вы находитесь в таком автопилоте? Метро, транспорт, .... на работе за монитором.

откуда взято
4. kuntashov 449 25.03.14 02:31 Сейчас в теме
Хорошая статья! Должно взлететь )
6. CratosX 112 26.03.14 09:26 Сейчас в теме
про нуралиевку толсто
8. ildarovich 7846 26.03.14 11:00 Сейчас в теме
(6) Так Вы считаете эту шутку лучше убрать? (на хабре)
7. Evil Beaver 8100 26.03.14 10:23 Сейчас в теме
Ildarovich опять творит невозможное запросами. А можно туповатым, вроде меня, объяснить что делают запросы, особенно тот, что с вращением?
9. ildarovich 7846 26.03.14 11:29 Сейчас в теме
(7) Эта задача интересна тем, что у нее есть минимум четыре различных решения:
1) показанное здесь;
2) варианты задаются сканируемой текстовой строкой типа "ДВШ ДШВ ВДШ ВШД ШДВ ШВД ";
3) вращения вокруг каждой оси делаются внутри вложенных запросов;
4) координаты образуются суммой К1 * Ш + К2 * В + К3 * Д, а коэффициенты берутся из искусственной таблицы.
1) выбрано из-за того, что покороче в записи. А вообще, в задаче "container loading" еще учитывается возможность вращения коробки по осям (при укладке бывает важно не класть упаковку на бок, например), поэтому вариант 3) может быть предпочтительнее.

Решение 1) основано на том, что на первом шаге таблица размеров "разворачивается" по измерениям. Каждой позиции таблицы размеров в таблице Scan соответствует три строчки: в первой ширина, во второй глубина, в третьей - высота.
1 : 10 : 20 : 30
->
1 : 10 : 1
1 : 20 : 2
1 : 30 : 3
Потом таблица соединяется с собой два раза. Получается двадцать семь вариантов (ШШШ, ШШД, ..., ВВВ) из которых убираются те, где минимум дважды повторяется одно измерение.
1 : 10 : 10 : 10
1 : 10 : 10 : 20
1 : 10 : 10 : 30
1 : 10 : 20 : 10
1 : 10 : 20 : 20

1 : 10 : 20 : 30
1 : 20 : 10 : 10
...
1 : 30 : 30 : 30

Alias; Boroda444; support; +3 Ответить
10. ildarovich 7846 26.03.14 12:47 Сейчас в теме
Кстати, приведенный упаковочный лист очень хорошо показывает достоинства и недостатки использованного критерия. Видно, что шестая по порядку позиция Classic Jenga кладется выше, чем следующая за ней седьмая. Это от того, что шестая Jenga ложится на нижележащую упаковку без пустот, а под седьмой уже есть пустота, так как длина Jenga 28 см, а Фермера - 26 см. По той же причине Jenga кладется не плоско, а "ребром" - чтобы оставить под собой меньше пустоты.
Иногда выгоднее использовать более простой критерий - учитывать только подъем уровня. Тогда формулы пересчета таблицы Vista упростятся. Наиболее сложное выражение в этом запросе связано как раз с расчетом образующейся под коробкой пустоты.
И еще добавлю, что при выводе картинки размеры упаковок специально чуть сокращены внутрь их объема, так как иначе грани упаковок накладывались друг на друга и было вообще трудно что-либо разобрать. Поэтому расстояние, которое отделяет упаковки друг от друга на картинке не всегда есть в реальности.
11. soap 65 27.03.14 12:21 Сейчас в теме
Действительно описание роскошное.
12. DAnry 8 28.03.14 12:09 Сейчас в теме
Автор красиво излагает. Может пора переквалифицироваться в управдомы, извините в писатели...
13. CheBurator 3119 30.03.14 01:29 Сейчас в теме
может не стоило изобретать велосиеппед а тупо использовать возможности, предоставляемые 3d-packer'om
.
http://www.packer3d.ru/
14. ildarovich 7846 30.03.14 01:55 Сейчас в теме
(13) Это платный сервис. Оправдывает себя при загрузке контейнеров, вагонов, но не коробов. Рассматривалась и эта и другие возможности: есть еще один-два бесплатных сервиса, а также по крайней мере одна "standalone" программа для решения этой задачи. Но проблема их лицензирования и сопряжения с нашей конфигурацией намного сложнее чем подключение одной внешней печатной формы.
Конкретно кода для подключения внешних средств окажется больше, чем в данном решении. Так что это не отдельный велосипед, а удобный встроенный механизм.
Ну и "тупо использовать" что-либо - это вообще не наш метод, как вы, наверное, заметили.
15. RustIG 1301 31.03.14 06:47 Сейчас в теме
сложный для понимания алгоритм :)
Такой вопрос: если мы перевернем основную коробку на бок, получим ли мы то же решение, что и в первоначальном варианте? Если мы будем продолжать вращать основную коробку, будем ли мы получать то же решение, что и в первоначальном решении?

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

Хотелось бы видеть в алгоритмах здравый смысл:
1. по сумме объемов мелких коробок определяется минимальная основная коробка.
2. располагать основную коробку на столе упаковки следует наибольшей по площади гранью.
3. начинать упаковывание следует с более крупных коробок, которые могут быть расположены или на дне основной коробки или вдоль торца основной коробки
4. в оставшиеся "прорези" по возможности упаковываем подходящие мелкие коробочки
5. и т.д. с оставшейся свободной частью основной коробки - хотя понимаю, что реализация здравого смысла приведет как раз-таки к подобному сложному решению - перебору вариантов.
18. ildarovich 7846 31.03.14 12:40 Сейчас в теме
(15) Сложным алгоритм является только на первый взгляд. Я просто не стал его "разжевывать", имея ввиду, что приложены запросы, по которым можно разобраться.
На самом деле по сути это семейство алгоритмов. Общим является способ генерации ВСЕХ возможных вариантов укладки коробки (с учетом дискретизации) на каждом шаге и коррекции этих возможностей после ВЫБОРА одного варианта. Выбор варианта можно производить по разным критериям (эвристикам). Например, как показано в тексте конкретного запроса выбора сначала можно класть ту коробку, под которой будет оставаться минимум пустого пространства. А можно, изменив порядок сортировки (все остальное также) сначала класть наиболее объемную коробку или коробку наибольшей площади.
С точки зрения программирования выбора алгоритм более чем прост - достаточно задать порядок сортировки в соответствующем запросе.
Если повернуть основную коробку на бок - получим другое решение! Но так делать нежелательно, так как загружать коробку сбоку неудобно. Если окажется, что последнюю коробку потребуется поместить к верху задней стенки - в некоторых случаях это будет физически не возможно.
Можете попробовать сформулировать свою эвристику 1-5 в виде порядка сортировки - должно получиться. Можно будет провести испытания. Если в среднем плотность упаковки с использованием вашей эвристики окажется больше, можно выбрать ее.
Испытания приведенной эвристики показали на стандартных тестах (они опубликованы) результат 69-72%. Но у нас не было задачи увеличивать этот процент. Заказчики посчитали его достаточным. Тем более натурные эксперименты показали, что человек-упаковщик обеспечивает примерно такой-же процент.
Судя по литературе, борьба за каждый процент свыше 77% многократно усложняет алгоритм.
19. ildarovich 7846 31.03.14 13:01 Сейчас в теме
(16) Эти ссылки я не использовал точно. Первая хоть и относится к двумерному случаю, но очень интересна, но была просто позже, чем выполнялись работы. Вторая - никак не рассчитана на реализацию на 1С, поскольку использует алгоритм с возвратами к предыдущим шагам укладки - это просто долго на 1С.
Я внимательно прочитал самые первые работы в данной области
BISCHOFF, E. E., JANETZ, F. & RATCLIFF, M. S. W. /1995/. Loading pallets with non-identical items.
European Journal of Operational Research, Vol. 84, pp. 681 - 692.
BISCHOFF, E. E. & RATCLIFF, M. S. W. /1995/. Issues in the development of approaches to container
loading. Omega, Vol. 23, pp. 377-390..
Затем просмотрел более современные ссылки, чтобы определить, какие методы в общем позволяют улучшит результат и до скольких процентов. Выяснил, что улучшения небольшие.
Также скачал стандартные тесты (могу найти ссылку).
Также посмотрел истоки 3Д пакера. Кажется, это разработка команды из МГУ и теоретические основы их метода описаны в соответствующих работах. Там нет одной ясной идеи. Используется композиция приемов сведения задачи к двумерному случаю, если я правильно помню.
17. Evil Beaver 8100 31.03.14 11:04 Сейчас в теме
Кстати, поскольку в общем виде задача является NP-полной, то какие ограничения имеют её существующие прикладные решения?
20. ildarovich 7846 31.03.14 13:20 Сейчас в теме
(17) Не могу сейчас ответить на этот вопрос. Поскольку для этого нужно произвести отдельное исследование. Тем более, кажется, в последнее время появилось еще ряд решений.
Но исходя из соображений "здравого смысла" все предлагаемые решения решают за приемлемое время (секунды) типичные практические задачи: загрузку кузова автомобиля, морского контейнера, вагона. Борьба идет не за проценты полезного использования объема контейнера (именно это касается математической сложности задачи и ее NP-полноты), а за другие вещи: удобство интерфейса, возможность ручных корректировок, наглядность представления получаемой упаковки, учет не прямоугольных упаковок, веса, совместимости грузов, устойчивости укладки и тому подобное.
Предложенный метод ограничен тем, что работает с дискретным положением упаковок (укладка с точностью до сантиметра или НОД длин сторон упаковок). Время его работы прямо пропорционально произведению W x D x K x N, где W, D - размеры дна короба, K - число разноразмерных упаковок, N - число упаковок.
21. a-novoselov 1154 03.04.14 09:47 Сейчас в теме
(0) Молодцы, красивое решение! Особенно после того, как несколько раз приходилось исправлять гениальные отчеты, в которых просроченная задолженность в циклах считается, очень приятно видеть такие решения запросами.

(8) Насчет Хабра, думаю, вас все равно завалят вопросами "Что за скриптовый язык такой?", так что лучше сразу написать что в 1С это делалось. Но и уточнение, что встроенный язык это интерпретатор, не сильно предназначенный для объемных вычислений и тормозящий на больших циклах, тоже опускать не стоит.
22. Ёпрст 1063 03.04.14 12:23 Сейчас в теме
(0)
Это , а алгоритм рисования есть самого упаковочного листа ?
Он должен быть не менее интересным.
23. Alex_IT 140 03.04.14 12:25 Сейчас в теме
(22) +1
И инструмент рисования...
46. пользователь 14.04.14 20:33
Сообщение было скрыто модератором.
...
47. пользователь 14.04.14 20:34
Сообщение было скрыто модератором.
...
24. ildarovich 7846 03.04.14 12:56 Сейчас в теме
(22) (23) Там все очень просто - это табличное поле 1С, используются его объекты-рисунки: линии и прямоугольники. Координаты, определяющие положение фигур считаются как проекции трехмерных координат на плоскость за коробкой. Это несложные формулы с элементами тригонометрии.
В общем-то, если бы было нужно, можно было бы этими средствами и мультфильм, показывающий порядок упаковки, изобразить (своеобразный тетрис 3D).
Но вот если вдруг понадобится удалять невидимые грани, будет непросто, так как нет объекта, который бы позволил залить цветом многоугольную область, чтобы воспользоваться методом z-буфера.
25. Ёпрст 1063 03.04.14 13:04 Сейчас в теме
(24) мот, мини демо-пример?
А то смутно представляю, как "палочки" рисовать в табличном поле, еще и разным цветом, еще и с циферкой в углу.
27. ildarovich 7846 03.04.14 13:17 Сейчас в теме
(25) Вот весь код, который рисует блок
Функция ДобавитьПрямую(Рисунки, x, y, dx, dy, Цвет, a = 0, b = 0, c = 0, d = 0)
	
	Результат = Рисунки.Добавить(ТипРисункаТабличногоДокумента.Прямая); 
	ЗаполнитьЗначенияСвойств(Результат, Новый Структура("Линия, Лево, Верх, Ширина, Высота, ЦветЛинии"
		, Новый Линия(ТипЛинииРисункаТабличногоДокумента.Точечная), Лево + x * Масштаб + a, Верх + y * Масштаб + b, dx * Масштаб + c, dy * Масштаб + d, Цвет));
	Возврат Результат
	
КонецФункции

Процедура НарисоватьБлок(Рисунки, x, y, z, dx, dy, dz, Текст, Цвет)
	
	Каркас = Новый Массив;
	
	x0 = x + z/2; y0 = y + z/2;
	
	//Каркас.Добавить(ДобавитьПрямую(Рисунки, x0, 			y0,				dx, 	0,		Цвет,  3, -1, -4,  0));
	Каркас.Добавить(ДобавитьПрямую(Рисунки, x0, 			y0 - dy, 		dx, 	0,		Цвет,  3,  3, -4,  0));
	Каркас.Добавить(ДобавитьПрямую(Рисунки, x0 + dz/2, 		y0 + dz/2,		dx, 	0,		Цвет,  1, -3, -4,  0));
	Каркас.Добавить(ДобавитьПрямую(Рисунки, x0 + dz/2, 		y0 + dz/2 - dy,	dx, 	0,		Цвет,  1,  1, -4,  0));
	
	Каркас.Добавить(ДобавитьПрямую(Рисунки, x0, 			y0, 			0, 		-dy,	Цвет,  3, -1,  0,  4));
	//Каркас.Добавить(ДобавитьПрямую(Рисунки, x0 + dx, 		y0,				0, 		-dy, 	Цвет, -1, -1,  0,  4));
	Каркас.Добавить(ДобавитьПрямую(Рисунки, x0 + dz/2, 		y0 + dz/2, 		0, 		-dy,	Цвет,  1, -3,  0,  4));
	Каркас.Добавить(ДобавитьПрямую(Рисунки, x0 + dz/2 + dx,	y0 + dz/2, 		0,		-dy, 	Цвет, -3, -3,  0,  4));
	
	Каркас.Добавить(ДобавитьПрямую(Рисунки, x0,				y0, 			dz/2,	dz/2,	Цвет,  3, -1, -2, -2));
	Каркас.Добавить(ДобавитьПрямую(Рисунки, x0,				y0 - dy, 		dz/2,	dz/2, 	Цвет,  3,  3, -2, -2));
	//Каркас.Добавить(ДобавитьПрямую(Рисунки, x0 + dx, 		y0, 			dz/2, 	dz/2, 	Цвет, -1, -1, -2, -2));
	Каркас.Добавить(ДобавитьПрямую(Рисунки, x0 + dx, 		y0 - dy, 		dz/2, 	dz/2, 	Цвет, -1,  3, -2, -2));
	
	ЗаполнитьЗначенияСвойств(Рисунки.Добавить(ТипРисункаТабличногоДокумента.Текст)
	, Новый Структура("Лево, Верх, Авторазмер, Текст, ЦветТекста, ЦветЛинии"
		, Лево + (x0 + dz/2) * Масштаб + 1, Верх + (y0 + dz/2 - dy) * Масштаб + 1, Истина, Текст, Цвет, Цвет));	
	
КонецПроцедуры
Показать
Еще можете посмотреть как похожая задача решается при рисовании графа в статье Как нарисовать граф на 1С. Там можно скачать обработку и посмотреть, как происходит рисование, выбирается масштаб и прочее
Ёпрст; +1 Ответить
78. Salavat 13 30.09.14 19:58 Сейчас в теме
и попутно - опять ведь перемешано - (27)
Функция ДобавитьПрямую(Рисунки, x, y, dx, dy, Цвет, a = 0, b = 0, c = 0, d = 0)
    
    Результат = Рисунки.Добавить(ТипРисункаТабличногоДокумента.Прямая); 
    ЗаполнитьЗначенияСвойств(Результат, Новый Структура("Линия, Лево, Верх, Ширина, Высота, ЦветЛинии"
        , Новый Линия(ТипЛинииРисункаТабличногоДокумента.Точечная), Лево + x * Масштаб + a, Верх + y * Масштаб + b, dx * Масштаб + c, dy * Масштаб + d, Цвет));
    Возврат Результат
    
КонецФункции

Процедура НарисоватьБлок(Рисунки, x, y, z, dx, dy, dz, Текст, Цвет)
    
    Каркас = Новый Массив;
    
    x0 = x + z/2; y0 = y + z/2;
    
    //Каркас.Добавить(ДобавитьПрямую(Рисунки, x0,             y0,                dx,     0,        Цвет,  3, -1, -4,  0));
    Каркас.Добавить(ДобавитьПрямую(Рисунки, x0,             y0 - dy,         dx,     0,        Цвет,  3,  3, -4,  0));
    Каркас.Добавить(ДобавитьПрямую(Рисунки, x0 + dz/2,         y0 + dz/2,        dx,     0,        Цвет,  1, -3, -4,  0));
    Каркас.Добавить(ДобавитьПрямую(Рисунки, x0 + dz/2,         y0 + dz/2 - dy,    dx,     0,        Цвет,  1,  1, -4,  0));
    
    Каркас.Добавить(ДобавитьПрямую(Рисунки, x0,             y0,             0,         -dy,    Цвет,  3, -1,  0,  4));
    //Каркас.Добавить(ДобавитьПрямую(Рисунки, x0 + dx,         y0,                0,         -dy,     Цвет, -1, -1,  0,  4));
    Каркас.Добавить(ДобавитьПрямую(Рисунки, x0 + dz/2,         y0 + dz/2,         0,         -dy,    Цвет,  1, -3,  0,  4));
    Каркас.Добавить(ДобавитьПрямую(Рисунки, x0 + dz/2 + dx,    y0 + dz/2,         0,        -dy,     Цвет, -3, -3,  0,  4));
    
    Каркас.Добавить(ДобавитьПрямую(Рисунки, x0,                y0,             dz/2,    dz/2,    Цвет,  3, -1, -2, -2));
    Каркас.Добавить(ДобавитьПрямую(Рисунки, x0,                y0 - dy,         dz/2,    dz/2,     Цвет,  3,  3, -2, -2));
    //Каркас.Добавить(ДобавитьПрямую(Рисунки, x0 + dx,         y0,             dz/2,     dz/2,     Цвет, -1, -1, -2, -2));
    Каркас.Добавить(ДобавитьПрямую(Рисунки, x0 + dx,         y0 - dy,         dz/2,     dz/2,     Цвет, -1,  3, -2, -2));
    
    ЗаполнитьЗначенияСвойств(Рисунки.Добавить(ТипРисункаТабличногоДокумента.Текст)
    , Новый Структура("Лево, Верх, Авторазмер, Текст, ЦветТекста, ЦветЛинии"
        , Лево + (x0 + dz/2) * Масштаб + 1, Верх + (y0 + dz/2 - dy) * Масштаб + 1, Истина, Текст, Цвет, Цвет));    
    
КонецПроцедуры
Показать

и по-русски и по английски...
dz - это Высота или что? dy - ширина или право? dx - Тыл или (Фронт минус Тыл) или наоборот или как?
Масштаб ладно - подбором ещё можно угадать, что там подставлять.
ДобавитьПрямую() - что за a, b, c,.........?

и т.д.............
79. Salavat 13 01.10.14 12:52 Сейчас в теме
(78) Salavat, Вобщем с рисованием разобрался (рисование написал по-своему) - вопрос отменяется.
Попутно выяснилось, что в Укладке нет Номера Ящика - добавил и его.

С перебором Номенклатуры (и с её количеством) - вопрос открытый.
26. Ёпрст 1063 03.04.14 13:08 Сейчас в теме
+ не ясно, почему на рисунке между коробами "пустоты" .. они же лежат друг на друге, а не "висят" в воздухе ? Или это для облегчения "чтения" упаковочного листа ?
28. ildarovich 7846 03.04.14 13:19 Сейчас в теме
(26) Я уже говорил в комментарии (10), что
при выводе картинки размеры упаковок специально чуть сокращены внутрь их объема, так как иначе грани упаковок накладывались друг на друга и было вообще трудно что-либо разобрать. Поэтому расстояние, которое отделяет упаковки друг от друга на картинке не всегда есть в реальности
30. Ёпрст 1063 03.04.14 13:22 Сейчас в теме
29. Ёпрст 1063 03.04.14 13:21 Сейчас в теме
Ага спасибо, еще пара уточняющих вопросов и мы из автора вытащим весь код целиком :)

ЗЫ: на счет "пустот", это так и задумано ? Для простоты визуального восприятия ?
32. ildarovich 7846 03.04.14 13:34 Сейчас в теме
(29) Да пожалуйста. На самом деле я собирался привести и обработку целиком, но для Хабра она не интересна, да и к статье ее сейчас приложить нельзя, поэтому чуть сэкономил время. Поскольку для публикации обработки еще нужно привести способ хранения габаритов упаковок, так как в штатной УТ10 его нет, а в УТ11 есть габариты, но тара не так определяется. В общем, пока решил с этим не спешить.
36. Evil Beaver 8100 04.04.14 10:11 Сейчас в теме
(32) кстати, когда ждать статью на хабре?
37. ildarovich 7846 04.04.14 13:13 Сейчас в теме
(36) Вообще-то статья уже вышла. Это было 28.03.14. Вот ссылка.
38. Evil Beaver 8100 07.04.14 10:15 Сейчас в теме
(37) извиняюсь, не заметил ее там.
42. Alex_IT 140 13.04.14 13:33 Сейчас в теме
(32) Интересно увидеть обработку, в любом виде, даже без возможности использования в типовых. Само рисование в 1С ну очень куцее и любое удачное визуальное решение всегда вызывает интерес.
43. ildarovich 7846 13.04.14 15:00 Сейчас в теме
(42) Alex_IT, обработку я со временем выложу, приспособив ее и к 10.3 и к 11 (уже почти все готово). Но если Вас интересует только рисование, обратите внимание на мой комментарий (23). Там приведен ВЕСЬ код из обработки, необходимый для рисования блоков в 2,5 D.
31. Ёпрст 1063 03.04.14 13:23 Сейчас в теме
Жалко только, что алгоритм не всем подходит, нужно еще учитывать вес коробки и его "хрупкость", это если уж совсем "правильно" укладывать
33. ildarovich 7846 03.04.14 13:38 Сейчас в теме
(31) И вес коробки и хрупкость можно учесть - все регулируется порядком сортировки в соответствующем запросе, куда можно добавить указанные поля.
40. FractonKireyev 11.04.14 17:53 Сейчас в теме
По поводу хрупкости (для (31) и (33)).
Всё совсем не так просто. Если товар лежит так (считаем, что твёрдые коробки не ниже хрупкой):

твёрдый - хрупкий - твёрдый

то длинную и тяжёлую коробку можно положить поперёк (так, чтобы концы опирались на твёрдые коробки) и нельзя вдоль хрупкой (раздавит).
Так что просто сортировкой в запросе просто так не отделаться - нужны какие-то другие алгоритмы.
34. Ёпрст 1063 03.04.14 15:32 Сейчас в теме
Круто, если демку оформите, хотя бы с одним справочником и одним документом.
39. FractonKireyev 11.04.14 17:46 Сейчас в теме
Чем была нарисована картинка со схемой укладки в коробку?
41. ildarovich 7846 11.04.14 19:18 Сейчас в теме
(39) FractonKireyev, в комментарии (27) я уже отвечал на этот вопрос. Это чистый 1С, используется поле табличного документа и объект "рисунок" типа линия. В том же комментарии приведен ВЕСЬ необходимый код рисования блока.
(40) Вариантов алгоритмов великое множество. Тот вариант, о котором говорите Вы (твердые должны опираться на твердые), можно считать подмножеством приведенного, если в нем ввести сортировку по критерию минимизации опоры на хрупкие коробки.
44. пользователь 14.04.14 20:32
Сообщение было скрыто модератором.
...
45. пользователь 14.04.14 20:33
Сообщение было скрыто модератором.
...
48. CheBurator 3119 14.04.14 22:30 Сейчас в теме
Вообще, конечно автор молодец!
еще в запросы впихнуть ограничения по каждой коробке (типа нельзя ставит на торец или типа как хрупкое с опорой выше)... и демо конфу минимальную... передавать в "пакете" исходные коробки на выходе получать раскладки...
49. CheBurator 3119 14.04.14 22:32 Сейчас в теме
вообще не сильно понятно наскольо эффективно работает такая упаковка ФИЗИЧЕСКи - ладноя понимаю палеты/конейтнеры комплектовать, но коробки размером 60см на 80... на 40... если упаковке подлежит большое колво разноообразного товара то имхо упаковщики которые стоят на упаковке сделают близко к оптимальному и без раскладки...
.
окупается ди сам процесс УПАКОВКИ КОРОБОК ПО СХЕМЕ?
50. ildarovich 7846 21.04.14 13:51 Сейчас в теме
(49) CheBurator,
упаковщики которые стоят на упаковке сделают близко к оптимальному и без раскладки...
Сам так думал, но недавно, после того, как вспомнили про задачу в связи со статьей, мы провели эксперимент: двух стажеров попросили заполнить короб разными найденными в офисе коробочками. Удивительно, но стажеры во всех попытках справились с работой хуже программки. Правда, мои коллеги отнесли все на способности стажеров, но все же факт остается фактом.
А про окупаемость можно рассудить так: если нужны упаковочные листы, то можно
1) получить их заранее и разложить товар по коробкам в соответствии с ними, подглядывая в упаковочный лист;
2) получить упаковочный лист после укладки, просканировав товар.
Кажется, первый вариант, не требующий сканера и лишнего хождения к принтеру, выглядит экономичнее.
Если упаковочные листы не нужны, то смысла тратить явно большее время на укладку по просчитанной схеме нет. Лучше натренировать упаковщика.
124. CheBurator 3119 17.02.21 16:06 Сейчас в теме
(50) упаковка паллет разными коробами хорошо работает когда много коробов и они мелкие. и когда всего пару коробов и они крупыне. а вот когда промежуточный вариант - короба среднего размера с малым количеством коробом мелкого размера - тут все сложнее становится если паковать "ручками". но даже в таком виде думаю опытные упаковщики быстро достаточно спраятся. по карйней мере у меня на складе - где коробки совершенно разномастные - упаковщики пакуют очень плотно и достаточно быстро. я думаю врядл ипргой получилось бы "выгоднее".
125. ildarovich 7846 17.02.21 16:51 Сейчас в теме
(124) Если пришлете накладную с размерами, смогу сказать, сколько паллет потребовалось программе, сможете сравнить.
126. Zaimist 04.11.21 14:40 Сейчас в теме
(125)Здравствуйте. Подскажите, как можно с вами связаться? Интересует возможность упаковки паллеты.
51. Kopman 23 10.06.14 08:18 Сейчас в теме
Хорошая статья. Присоединяюсь к желающим увидеть обработку.
52. alexandr851c 27 21.07.14 14:28 Сейчас в теме
Хотелось бы увидеть обработку. Будет ли она выложена?
53. ildarovich 7846 21.07.14 16:39 Сейчас в теме
(52) alexandr851c, обработка будет выложена. Когда - пока сказать не могу.
54. alexandr851c 27 24.07.14 09:51 Сейчас в теме
(53) а можете кинуть саму процедуру упаковки ))) Заранее огромное спасибо.
55. scientes 288 31.07.14 14:23 Сейчас в теме
Что интересно, похоже в приведенном коде есть опечатка. Взялся проверять самый первый запрос.
SELECT 0 AS x
    INTO R1                                 
UNION
SELECT 1;

SELECT L.x + 2 * H.x AS x
    INTO R2
    FROM R1 AS L, R1 AS H;

SELECT L.x + 2 * H.x AS x
    INTO R4
    FROM R2 AS L, R2 AS H;

SELECT L.x + 2 * H.x AS x
    INTO R8
    FROM R4 AS L, R4 AS H;
Показать


Чтобы получилась последовательность от 0 до 255, надо в таблице R4 использовать коэффициент 4, а в таблице R8 коэффициент 16.
ildarovich; +1 Ответить
56. ildarovich 7846 31.07.14 14:51 Сейчас в теме
(55) scientes, вы очень внимательны. Ошибку исправлю. Она появилась в ходе перевода запроса на английский. Сам принцип такого способа генерации множества чисел изложен в статье "Порождающий запрос".
57. Salavat 13 23.09.14 09:56 Сейчас в теме
эх,.. что то с наименованиями полей напутано. начиная с
INTO Vista
похоже.

но конкретно - в
SELECT TOP 1 id, d0l, d1l, d2l, d0h, d1h, d2 
	FR OM Vista 
	WHERE d2l + d2 < = &Height 
	ORDER BY s * d2l - v, s * d2 DESC, d2l + d2, d0l, d1l, d0h;
у Vista нет (из предыдущего запроса) - d2.

я правильно понял - там d2h нужно?

а в следующем запросе - там (или ранее где) перепутано (кроме указанного) с it - он такой же как и в
SELECT id, CASE x WHEN 0 THEN d0 WHEN 1 THEN d1 WHEN 2 THEN d2 END AS dx, x
	INTO Scan
	FR OM Items, R2
	WH ERE x < 3;
?
если да, то в последнем уже снова для него появились -
It.d2l, It.d1l,
, и аналогичные...

Автор, прокомментируйте пожалуйста.
61. ildarovich 7846 24.09.14 13:42 Сейчас в теме
(57) Salavat, да, это ошибка, она появилась, когда я переименовывал (желая сделать их покороче) наименования измерений. Неправильно "as d2h" - - это вообще не нужно писать - так как там фактически поле не переименовывается. Нужно d2 as d2. Измерение d2 обозначает просто высоту упаковки. Не положение верхнего края - оно не нужно. А собственно высоту. Положение верхнего края далее вычисляется как d2l + d2, то есть как положение нижнего края плюс высота. Вот текст запроса выбора коробки с "нормальными" наименованиями полей
ВЫБРАТЬ ПЕРВЫЕ 1
Зона.ИндексКоробки,
Зона.Лево КАК Лево,
Зона.Тыл КАК Тыл,
Зона.Низ,
Зона.Право КАК Право,
Зона.Фронт,
Зона.Высота КАК Высота
ИЗ
Зона КАК Зона
ГДЕ
Зона.Низ + Зона.Высота <= &Высота

УПОРЯДОЧИТЬ ПО
Зона.Площадь * Зона.Низ - Зона.Опора,
Зона.Площадь * Зона.Высота УБЫВ,
Зона.Низ + Зона.Высота,
Лево,
Тыл,
Право
Показать
Зона - это Vista (пространство возможностей) до переименования.
Вот текст запроса инициализации с соответствующими названиями переменных
ВЫБРАТЬ
Слева.Х КАК Лево,
Сзади.Х КАК Тыл,
Слева.Х + Коробки.Глубина КАК Право,
Сзади.Х + Коробки.Ширина КАК Фронт,
0 КАК Низ,
Коробки.Высота КАК Высота,
0 КАК Опора,
Коробки.Глубина * Коробки.Ширина КАК Площадь,
Коробки.НомерСтроки КАК ИндексКоробки
ИЗ
Регистр8 КАК Слева,
Регистр8 КАК Сзади,
КрученыеКоробки КАК Коробки
ГДЕ
Слева.Х <= &Глубина
И Сзади.Х <= &Ширина
И Коробки.Высота <= &Высота
Показать

Про It (это алиас таблицы, которая хранит параметры выбранной коробки) вопрос не понял. В запросе, в котором упоминается эта таблица, все записи возможных размещений "пересекаются" с параметрами одной выбранной упаковки. И если они пространственно пересекаются, возможное размещение корректируется по вертикали (только дно поднимается - высота упаковки не меняется).
Вот текст запроса пересечения по-русски
ВЫБРАТЬ
Зона.Лево,
Зона.Тыл,
ЕСТЬNULL(ВЫБОР
КОГДА Коробка.Низ + Коробка.Высота > Зона.Низ
ТОГДА Коробка.Низ + Коробка.Высота
КОНЕЦ, Зона.Низ) КАК Низ,
Зона.Право,
Зона.Фронт,
Зона.Высота,
Зона.Опора + ЕСТЬNULL((ВЫБОР
КОГДА Коробка.Право < Зона.Право
ТОГДА Коробка.Право
ИНАЧЕ Зона.Право
КОНЕЦ - ВЫБОР
КОГДА Коробка.Лево > Зона.Лево
ТОГДА Коробка.Лево
ИНАЧЕ Зона.Лево
КОНЕЦ) * (ВЫБОР
КОГДА Коробка.Фронт < Зона.Фронт
ТОГДА Коробка.Фронт
ИНАЧЕ Зона.Фронт
КОНЕЦ - ВЫБОР
КОГДА Коробка.Тыл > Зона.Тыл
ТОГДА Коробка.Тыл
ИНАЧЕ Зона.Тыл
КОНЕЦ) * Коробка.Высота, 0) КАК Опора,
Зона.Площадь,
Зона.ИндексКоробки
ИЗ
Зона КАК Зона
ЛЕВОЕ СОЕДИНЕНИЕ Коробка КАК Коробка
ПО (Зона.Тыл <= Коробка.Тыл
И Коробка.Тыл < Зона.Фронт
ИЛИ Коробка.Тыл <= Зона.Тыл
И Зона.Тыл < Коробка.Фронт)
И (Зона.Лево <= Коробка.Лево
И Коробка.Лево < Зона.Право
ИЛИ Коробка.Лево <= Зона.Лево
И Зона.Лево < Коробка.Право)
ГДЕ
Зона.ИндексКоробки <> &ИндексКоробки
Показать
62. Salavat 13 25.09.14 15:27 Сейчас в теме
(61) а что за переменные &Высота, Ширина, Глубина - это размеры Номенклатуры или Ящика?
63. ildarovich 7846 26.09.14 10:26 Сейчас в теме
(62) Salavat, это размеры ящика (короба)
64. Salavat 13 26.09.14 15:55 Сейчас в теме
(61)
...
Зона.ИндексКоробки, 
Зона.Лево КАК Лево, 
Зона.Тыл КАК Тыл, 
Зона.Низ, 
Зона.Право КАК Право, 
Зона.Фронт, 
Зона.Высота КАК Высота,
...
Зона.Опора,
Зона.Площадь,
...
Показать

Коробки как я понял - это всё-таки Номенклатура?
А зачем так много полей и/или - что они значат? Лево, Право,.. Тыл, Фронт,.. Опора, Площадь,..
Из перечисленного только понял про Низ и Высота - разве не достаточно было всё так и обозначать через координаты начального угла и размеры граней номенклатуры?
65. ildarovich 7846 26.09.14 16:33 Сейчас в теме
(64) Salavat, в принципе, положение коробки, которую можно вращать, задается шестью параметрами. Ими действительно могут быть координаты угла (три числа) и размеры сторон (три числа). А могут быть и координаты граней (Лево, Право, Тыл, Фронт, Низ, Верх). Или комбинированный вариант, как у меня: Лево, Право, Тыл, Фронт, Низ, Высота. Я выбрал такой вариант, чтобы минимизировать вычисления при определении пересечений. Для определения пересечения нужно знать, например правый край. И его не нужно вычислять как Лево + Ширина. Он хранится как "Право". В отношении Низа и Верха получилось, что Высота в расчетах используется чаще чем Верх и я взял высоту.
В общем, это все для минимизации вычислений в процессе работы.
Также про "опору" и площадь. Площадь считается сразу - она у варианта не меняется. Это произведение ширины на глубину (мы стоим перед коробкой). "Опора" - это более сложная вещь. Это сколько занятого объема находится под дном номенклатуры. В идеале под номенклатурой не должно быть пустоты - "опора" должна быть равна произведению площади на координату "низ" коробки. Разница говорит о пустоте. Чем она больше, тем больше пустоты под коробкой. Поэтому разница объема под коробкой и "опоры" используется для сортировки вариантов по критерию минимума незанятого пространства.
66. Salavat 13 26.09.14 17:46 Сейчас в теме
(65) ок - ладно с координатами вроде (!) понятно.
но чем дальше я пытаюсь разобраться, тем больше мне всё это напоминает миф какойто красиво нарисованный (+/-).

далее - таблицы?
Зона - это как уложено на данной итерации?
Укладка - это что такое?

Вобще - мне малоинтересна теория, т.б. тянущая не менее чем на курсовик.
Достаточно (и полезнее) былобы на уровне - "
...
1. Запрос ........ - .
2. &А, &Б, &В - размеры, которые подставить в виде...
3. Таблица БлаБлаБла - ....... которая ....... и ...
..."
мне бы (да и другим - не сомневаюсь) - гораздо полезнее была бы публикация, которую можно было использовать Практически, а не для убийства времени, разгадывания - что/куда/откуда/как/когда/... ...

Спасибо если поняли о чём я прошу.

58. CheBurator 3119 23.09.14 23:39 Сейчас в теме
мне бы данная обработка пригодилась бы для расчета "сколько однотипных коробок влезитя в ячейку заданного размера".
59. ildarovich 7846 24.09.14 09:04 Сейчас в теме
(58) CheBurator, конечно, данный подход решит эту задачу, но для нее есть гораздо более простые способы. Что мешает поделить длину ячейки на длину одной упаковки, ширину ячейки на ширину упаковки, высоту ячейки на высоту упаковки, затем взять целые части результатов деления и перемножить их? Или упаковки можно по-разному вращать при складывании?
60. CheBurator 3119 24.09.14 10:15 Сейчас в теме
(59) да, можно по разному, например укладка на палете (ну и соответственно в ячейке резервного хранения) может быть вот такой
http://screencast.com/t/6HLjQIxZl0p (вид на палету сверху) - 7 коробок в слое, следующий слой кладется наоборот : 2 коробки получатся слева...
как например посчитать такую раскладку слоя сходу - навскидку не соображу. Здесь что "хорошо" - все коробки одного размера.
.
при такой раскладке высота всех коробок одинаковая.
а вот например при запихивании в ячейку активного хранения можно извращаться и посильнее - какие-то коробки на торец ставить и т.д. - будет ли при этом выигрыш - хз...
67. Salavat 13 28.09.14 10:46 Сейчас в теме
продолжаю свою попытку:

и так - исходные данные (мои):
Ящик и список Номенклатуры (автор её Коробкой называет) с указанием количества. Оба имеют - Высоту, Ширину и Глубину (Номенклатура в списке - различная, с различными габаритами).
Номенклатура имеет верх (вращать вокруг вертикальной оси - можно).

Задача - определить необходимое (минимальное и оптимальное) количество Ящиков для заданного Списка Номенклатуры.

Последовательность алгоритма:

1. Формируем и выполняем запрос (результат - первичное решение -
ВЫБРАТЬ
	Коробки.НомерСтроки,
	Коробки.Глубина,
	Коробки.Ширина,
	Коробки.Высота
ПОМЕСТИТЬ Коробки
ИЗ
	&Коробки КАК Коробки
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Коробки.НомерСтроки КАК id,
	Коробки.Глубина КАК d0,
	Коробки.Ширина КАК d1,
	Коробки.Ширина КАК d2
ПОМЕСТИТЬ Items
ИЗ
	Коробки КАК Коробки
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	0 КАК x
ПОМЕСТИТЬ R1

ОБЪЕДИНИТЬ

ВЫБРАТЬ
	1
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	L.x + 2 * H.x КАК x
ПОМЕСТИТЬ R2
ИЗ
	R1 КАК L,
	R1 КАК H
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	L.x + 2 * H.x КАК x
ПОМЕСТИТЬ R4
ИЗ
	R2 КАК L,
	R2 КАК H
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	L.x + 2 * H.x КАК x
ПОМЕСТИТЬ R8
ИЗ
	R4 КАК L,
	R4 КАК H
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Items.id,
	ВЫБОР R2.x
		КОГДА 0
			ТОГДА Items.d0
		КОГДА 1
			ТОГДА Items.d1
		КОГДА 2
			ТОГДА Items.d2
	КОНЕЦ КАК dx,
	R2.x
ПОМЕСТИТЬ Scan
ИЗ
	Items КАК Items,
	R2 КАК R2
ГДЕ
	R2.x < 3
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	B0.id,
	B0.dx КАК d0,
	B1.dx КАК d1,
	B2.dx КАК d2
ПОМЕСТИТЬ Spin
ИЗ
	Scan КАК B0
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ Scan КАК B1
		ПО B0.id = B1.id
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ Scan КАК B2
		ПО B0.id = B2.id
ГДЕ
	НЕ(B0.x = B1.x
				ИЛИ B0.x = B2.x
				ИЛИ B1.x = B2.x)
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	FromLeft.x КАК d0l,
	FromBack.x КАК d1l,
	FromLeft.x + Spin.d0 КАК d0h,
	FromBack.x + Spin.d1 КАК d1h,
	0 КАК d2l,
	Spin.d2 КАК d2h,
	0 КАК Опора,
	Spin.d0 * Spin.d1 КАК S,
	Spin.id
ПОМЕСТИТЬ Vista
ИЗ
	R8 КАК FromLeft,
	R8 КАК FromBack,
	Spin КАК Spin
ГДЕ
	FromLeft.x + Spin.d0 <= &Width
	И FromBack.x + Spin.d1 <= &Depth
	И Spin.d2 <= &Hight
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	0 КАК Х
ПОМЕСТИТЬ Регистр1

ОБЪЕДИНИТЬ

ВЫБРАТЬ
	1
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Младшие.Х + 2 * Старшие.Х КАК Х
ПОМЕСТИТЬ Регистр2
ИЗ
	Регистр1 КАК Младшие,
	Регистр1 КАК Старшие
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Младшие.Х + 4 * Старшие.Х КАК Х
ПОМЕСТИТЬ Регистр4
ИЗ
	Регистр2 КАК Младшие,
	Регистр2 КАК Старшие
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Младшие.Х + 16 * Старшие.Х КАК Х
ПОМЕСТИТЬ Регистр8
ИЗ
	Регистр4 КАК Младшие,
	Регистр4 КАК Старшие
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ РАЗЛИЧНЫЕ
	Коробки.НомерСтроки,
	ВЫБОР Вариант.Х
		КОГДА 0
			ТОГДА Коробки.Глубина
		КОГДА 1
			ТОГДА Коробки.Ширина
		КОГДА 2
			ТОГДА Коробки.Высота
	КОНЕЦ КАК Значение,
	Вариант.Х КАК Измерение
ПОМЕСТИТЬ Коробки1
ИЗ
	Коробки КАК Коробки,
	Регистр2 КАК Вариант
ГДЕ
	Вариант.Х < 3
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ РАЗЛИЧНЫЕ
	Коробки1.НомерСтроки,
	Коробки1.Значение КАК Глубина,
	Коробки2.Значение КАК Ширина,
	Коробки3.Значение КАК Высота
ПОМЕСТИТЬ КрученыеКоробки
ИЗ
	Коробки1 КАК Коробки1
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ Коробки1 КАК Коробки2
		ПО Коробки1.НомерСтроки = Коробки2.НомерСтроки
		ВНУТРЕННЕЕ СОЕДИНЕНИЕ Коробки1 КАК Коробки3
		ПО (Коробки1.НомерСтроки = Коробки2.НомерСтроки)
ГДЕ
	НЕ(Коробки1.Измерение = Коробки2.Измерение
				ИЛИ Коробки1.Измерение = Коробки3.Измерение
				ИЛИ Коробки2.Измерение = Коробки3.Измерение)
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ РАЗЛИЧНЫЕ
	Коробки.НомерСтроки,
	ВЫБОР ПОДСТРОКА("ДШВ ШДВ ШВД ДВШ ВДШ ВШД", 4 * Вариант.Х + 1, 1)
		КОГДА "Д"
			ТОГДА Коробки.Глубина
		КОГДА "Ш"
			ТОГДА Коробки.Ширина
		КОГДА "В"
			ТОГДА Коробки.Высота
	КОНЕЦ КАК Глубина,
	ВЫБОР ПОДСТРОКА("ДШВ ШДВ ШВД ДВШ ВДШ ВШД", 4 * Вариант.Х + 2, 1)
		КОГДА "Д"
			ТОГДА Коробки.Глубина
		КОГДА "Ш"
			ТОГДА Коробки.Ширина
		КОГДА "В"
			ТОГДА Коробки.Высота
	КОНЕЦ КАК Ширина,
	ВЫБОР ПОДСТРОКА("ДШВ ШДВ ШВД ДВШ ВДШ ВШД", 4 * Вариант.Х + 3, 1)
		КОГДА "Д"
			ТОГДА Коробки.Глубина
		КОГДА "Ш"
			ТОГДА Коробки.Ширина
		КОГДА "В"
			ТОГДА Коробки.Высота
	КОНЕЦ КАК Высота
ПОМЕСТИТЬ КрученыеКоробки1
ИЗ
	Коробки КАК Коробки,
	Регистр4 КАК Вариант
ГДЕ
	Вариант.Х < 6
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Слева.Х КАК Лево,
	Сзади.Х КАК Тыл,
	Слева.Х + Коробки.Глубина КАК Право,
	Сзади.Х + Коробки.Ширина КАК Фронт,
	0 КАК Низ,
	Коробки.Высота КАК Высота,
	0 КАК Опора,
	Коробки.Глубина * Коробки.Ширина КАК Площадь,
	Коробки.НомерСтроки КАК ИндексКоробки
ИЗ
	Регистр8 КАК Слева,
	Регистр8 КАК Сзади,
	КрученыеКоробки КАК Коробки
ГДЕ
	Слева.Х <= &Глубина
	И Сзади.Х <= &Ширина
	И Коробки.Высота <= &Высота
	И Слева.Х + Коробки.Глубина <= &Глубина
	И Сзади.Х + Коробки.Ширина <= &Ширина
Показать

Параметры запроса:
1) &Коробки - Номенклатура. ТаблицаЗначений с колонками - № позиции, Глубина, Ширина, Высота.
2) &Width, &Depth, &Hight (они же - &Ширина, &Глубина, &Высота) - габариты Ящика.

2... дальше я просто потерял путь мысли. Понимаю, что должен быть цикл подбора-оценки, но какой? веди и в п.1 уже участвуют Коробки (вроде бы), по-крайней мере в тексте.

Автор, помогите, пожалуйста.
68. ildarovich 7846 29.09.14 10:38 Сейчас в теме
(67) Salavat, текст запроса, который вы привели, я использовал для подготовки статьи. В нем всех таблиц по две. На самом деле достаточно вот такого варианта
ВЫБРАТЬ
	Коробки.НомерСтроки,
	Коробки.Глубина,
	Коробки.Ширина,
	Коробки.Высота
ПОМЕСТИТЬ Коробки
ИЗ
	&Коробки КАК Коробки
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	0 КАК Х
ПОМЕСТИТЬ Регистр1

ОБЪЕДИНИТЬ

ВЫБРАТЬ
	1
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Младшие.Х + 2 * Старшие.Х КАК Х
ПОМЕСТИТЬ Регистр2
ИЗ
	Регистр1 КАК Младшие,
	Регистр1 КАК Старшие
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Младшие.Х + 4 * Старшие.Х КАК Х
ПОМЕСТИТЬ Регистр4
ИЗ
	Регистр2 КАК Младшие,
	Регистр2 КАК Старшие
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Младшие.Х + 16 * Старшие.Х КАК Х
ПОМЕСТИТЬ Регистр8
ИЗ
	Регистр4 КАК Младшие,
	Регистр4 КАК Старшие
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ РАЗЛИЧНЫЕ
	Коробки.НомерСтроки,
	ВЫБОР ПОДСТРОКА("ДШВ ШДВ ШВД ДВШ ВДШ ВШД", 4 * Вариант.Х + 1, 1)
		КОГДА "Д"
			ТОГДА Коробки.Глубина
		КОГДА "Ш"
			ТОГДА Коробки.Ширина
		КОГДА "В"
			ТОГДА Коробки.Высота
	КОНЕЦ КАК Глубина,
	ВЫБОР ПОДСТРОКА("ДШВ ШДВ ШВД ДВШ ВДШ ВШД", 4 * Вариант.Х + 2, 1)
		КОГДА "Д"
			ТОГДА Коробки.Глубина
		КОГДА "Ш"
			ТОГДА Коробки.Ширина
		КОГДА "В"
			ТОГДА Коробки.Высота
	КОНЕЦ КАК Ширина,
	ВЫБОР ПОДСТРОКА("ДШВ ШДВ ШВД ДВШ ВДШ ВШД", 4 * Вариант.Х + 3, 1)
		КОГДА "Д"
			ТОГДА Коробки.Глубина
		КОГДА "Ш"
			ТОГДА Коробки.Ширина
		КОГДА "В"
			ТОГДА Коробки.Высота
	КОНЕЦ КАК Высота
ПОМЕСТИТЬ КрученыеКоробки
ИЗ
	Коробки КАК Коробки,
	Регистр4 КАК Вариант
ГДЕ
	Вариант.Х < 6
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Слева.Х КАК Лево,
	Сзади.Х КАК Тыл,
	Слева.Х + Коробки.Глубина КАК Право,
	Сзади.Х + Коробки.Ширина КАК Фронт,
	0 КАК Низ,
	Коробки.Высота КАК Высота,
	0 КАК Опора,
	Коробки.Глубина * Коробки.Ширина КАК Площадь,
	Коробки.НомерСтроки КАК ИндексКоробки
ИЗ
	Регистр8 КАК Слева,
	Регистр8 КАК Сзади,
	КрученыеКоробки КАК Коробки
ГДЕ
	Слева.Х <= &Глубина
	И Сзади.Х <= &Ширина
	И Коробки.Высота <= &Высота
	И Слева.Х + Коробки.Глубина <= &Глубина
	И Сзади.Х + Коробки.Ширина <= &Ширина
Показать


В Вашем случае коробка не будет крутиться вокруг всех осей, поэтому запрос для получения "Крученых коробок" будет проще
////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ РАЗЛИЧНЫЕ
	Коробки.НомерСтроки,
	ВЫБОР ПОДСТРОКА("ДШВ ШДВ ", 4 * Вариант.Х + 1, 1)
		КОГДА "Д"
			ТОГДА Коробки.Глубина
		КОГДА "Ш"
			ТОГДА Коробки.Ширина
		КОГДА "В"
			ТОГДА Коробки.Высота
	КОНЕЦ КАК Глубина,
	ВЫБОР ПОДСТРОКА("ДШВ ШДВ ", 4 * Вариант.Х + 2, 1)
		КОГДА "Д"
			ТОГДА Коробки.Глубина
		КОГДА "Ш"
			ТОГДА Коробки.Ширина
		КОГДА "В"
			ТОГДА Коробки.Высота
	КОНЕЦ КАК Ширина,
	ВЫБОР ПОДСТРОКА("ДШВ ШДВ ", 4 * Вариант.Х + 3, 1)
		КОГДА "Д"
			ТОГДА Коробки.Глубина
		КОГДА "Ш"
			ТОГДА Коробки.Ширина
		КОГДА "В"
			ТОГДА Коробки.Высота
	КОНЕЦ КАК Высота
ПОМЕСТИТЬ КрученыеКоробки
ИЗ
	Коробки КАК Коробки,
	Регистр4 КАК Вариант
ГДЕ
	Вариант.Х < 2
;
Показать
А можно еще проще, но без отладки трудно точно сказать

Важно, в чем задаются размеры. Лучше, чтобы они были все в сантиметрах. Теоретически ширина и глубина (размеры дна) в этом запросе не могут быть больше 255. Но практически максимум: 50-100 сантиметров. Почему это важно? - Потому что в результате этого запроса формируется таблица ВСЕХ вариантов укладки КАЖДОЙ коробки в ящик. Укладка производится в узлы сантиметровой (например) сетки. Если сетка будет слишком мелкой (например, миллиметровой), то вариантов окажется слишком много.

То есть в этой таблице каждая запись соответствует одной коробке, находящейся в конкретном узле сетки и находящейся на дне (Дно = 0) ящика. Это первоначально. Это таблица вариантов "Зона" или Vista в английском варианте запроса.

Теперь "путь мысли" далее.

Из таблицы вариантов выбирается ОДНА конкретная запись (как - чуть позже). Это запрос "Выбор места". Лучший вариант помещения коробки в ящик. Тогда мы знаем номер помещаемой коробки и ее координаты. Можем запомнить, напечатать и тому подобное. Это уже часть результата.

Далее все варианты из таблицы Зона (Vista) соединяются JOIN с одной выбранной записью. При этом соединение смотрится: пересекается ли в пространстве коробка варианта и укладываемая коробка. Не мешает ли ВОЗМОЖНОМУ варианту укладываемая (зафиксированная) коробка. Если пересечения нет, то вариант остается без изменений - как есть - та же запись. А если пересечение есть, то коробка варианта ПОДНИМАЕТСЯ на высоту укладываемой коробки. То есть теперь мы сможем положить эту коробку только ВЫШЕ этой - в следующий по высоте слой. У варианта укладки в таблице Зона меняется поле записи "Дно". То есть идет пересчет всех вариантов - всей таблицы вариантов. Это делается запросом в функции "Укладка". И так далее.

Выбор места делается так: варианты сортируются по "пустоте ниже", объему в обратном порядке, высоте верха. И выбирается первый вариант, который имеет минимальную пустоту ниже, либо максимальный объем при равной пустоте, либо минимальную высоту верха при равенстве первых двух параметров. Этот критерий легко поменять, так как запрос очень простой.


69. Salavat 13 29.09.14 13:02 Сейчас в теме
(68) ок. Спасибо.

да - размеры в сантиметрах, но с 2 знаками после запятой. это (миллиметры - фактически) влияет?
можно и округлить (для гарантии - отсечь миллиметры) - нестрашно это. ну по полсантиметра (в среднем) будут дополнительные пробелы и только.

я правильно понял это?

и так:
1. Получаем таблицу вариантов Зона (Vista) из запроса
ВЫБРАТЬ
	Коробки.НомерСтроки,
	Коробки.Глубина,
	Коробки.Ширина,
	Коробки.Высота
ПОМЕСТИТЬ Коробки
ИЗ
	&Коробки КАК Коробки
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	0 КАК Х
ПОМЕСТИТЬ Регистр1

ОБЪЕДИНИТЬ

ВЫБРАТЬ
	1
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Младшие.Х + 2 * Старшие.Х КАК Х
ПОМЕСТИТЬ Регистр2
ИЗ
	Регистр1 КАК Младшие,
	Регистр1 КАК Старшие
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Младшие.Х + 4 * Старшие.Х КАК Х
ПОМЕСТИТЬ Регистр4
ИЗ
	Регистр2 КАК Младшие,
	Регистр2 КАК Старшие
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Младшие.Х + 16 * Старшие.Х КАК Х
ПОМЕСТИТЬ Регистр8
ИЗ
	Регистр4 КАК Младшие,
	Регистр4 КАК Старшие
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ РАЗЛИЧНЫЕ
	Коробки.НомерСтроки,
	ВЫБОР ПОДСТРОКА("ДШВ ШДВ ", 4 * Вариант.Х + 1, 1)
		КОГДА "Д"
			ТОГДА Коробки.Глубина
		КОГДА "Ш"
			ТОГДА Коробки.Ширина
		КОГДА "В"
			ТОГДА Коробки.Высота
	КОНЕЦ КАК Глубина,
	ВЫБОР ПОДСТРОКА("ДШВ ШДВ ", 4 * Вариант.Х + 2, 1)
		КОГДА "Д"
			ТОГДА Коробки.Глубина
		КОГДА "Ш"
			ТОГДА Коробки.Ширина
		КОГДА "В"
			ТОГДА Коробки.Высота
	КОНЕЦ КАК Ширина,
	ВЫБОР ПОДСТРОКА("ДШВ ШДВ ", 4 * Вариант.Х + 3, 1)
		КОГДА "Д"
			ТОГДА Коробки.Глубина
		КОГДА "Ш"
			ТОГДА Коробки.Ширина
		КОГДА "В"
			ТОГДА Коробки.Высота
	КОНЕЦ КАК Высота
ПОМЕСТИТЬ КрученыеКоробки
ИЗ
	Коробки КАК Коробки,
	Регистр4 КАК Вариант
ГДЕ
	Вариант.Х < 2
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Слева.Х КАК Лево,
	Сзади.Х КАК Тыл,
	Слева.Х + Коробки.Глубина КАК Право,
	Сзади.Х + Коробки.Ширина КАК Фронт,
	0 КАК Низ,
	Коробки.Высота КАК Высота,
	0 КАК Опора,
	Коробки.Глубина * Коробки.Ширина КАК Площадь,
	Коробки.НомерСтроки КАК ИндексКоробки
ИЗ
	Регистр8 КАК Слева,
	Регистр8 КАК Сзади,
	КрученыеКоробки КАК Коробки
ГДЕ
	Слева.Х <= &Глубина
	И Сзади.Х <= &Ширина
	И Коробки.Высота <= &Высота
	И Слева.Х + Коробки.Глубина <= &Глубина
	И Сзади.Х + Коробки.Ширина <= &Ширина
Показать


2. Расшифровку Пути мысли - не понял (пытался перечитать много раз). Что значит
смотрится: пересекается ли
- мне абсолютно по-барабану.
Пожалуйста просто по пунктно перечислите в каком порядке что/когда/как нужно делать дальше с этой Зоной для получения оптимального размещения.
И - в каком виде оно (решение) вообще должно получиться?.
70. ildarovich 7846 29.09.14 13:35 Сейчас в теме
(69) Salavat, миллиметры нужно отсечь. Обязательно.

Зона - это таблица.
1) в ней нужно выбрать одну строку. Запрос для выбора приведен в функции ВыборМеста. Смысл его в том, чтобы выбрать лучший вариант размещения коробки. В этой строке уже решение для одной коробки - можете его вывести как либо. Там есть номер коробки, ее положение и все ее размеры. Теперь уменьшаем на один число таких коробок к размещению.
2) Если число коробок такого типоразмера (с таким Id) стало равно нулю, все такие коробки нужно удалить из таблицы Зона - переписать ее с условием ГДЕ Id <> IdВыбраннойКоробки.
У меня Id коробки соответствовал строке табличной части ЗаказаПокупателя. То есть, если оказывалось, что в строке уже не оставалось не размещенных позиций, то Id удалялось из таблицы Зона.
3) Если выбранная коробка мешает возможным вариантам, то их нужно скорректировать. Как это делается - делается запрос к таблице Зона. В запросе указываются параметры. Запрос возвращает новую таблицу Зона. Уже пересчитанную. В ней все варианты скорректированы. Некоторые оставлены без изменения (на которые не повлияло сделанное размещение), а у некоторых изменен "Низ", также пересчитана "опора".
Такая же таблица по структуре получается, но с некоторыми другими числами, относительно уровня, где теперь могут помещаться коробки.
У меня 2) и 3) делаются в одном запросе "УкладкаКоробки".
Пункт 1) повторяется, пока возможен выбор, пока запрос ВыборМеста возвращает строку. Там ограничена высота и если не найдется вариантов, высота верха коробки в котором будет меньше, чем высота ящика, то запрос ничего не вернет.
Тогда увеличивается число использованных ящиков и повторяется инициализация (приземление). Варианты опять рассматриваются, начиная с дна ящика.

То есть решение получается в виде последовательности строк, выбираемых из таблицы "Зона". Каждая выбранная за один раз строка - это укладка одной коробки. После каждой укладки вся таблица "Зона" пересчитывается. Или инициализируется заново при взятии нового ящика.
71. Salavat 13 29.09.14 14:48 Сейчас в теме
(70) ок.

и так - Цикл (пока ЗапросВыборМеста даёт результат - для следующей коробки, иначе - берём следующий Ящик):

1) Запрос ВыборМеста -
ВЫБРАТЬ
	Зона.Лево,
	Зона.Тыл,
	Зона.Низ,
	Зона.Право,
	Зона.Фронт,
	Зона.Высота,
	Зона.Опора,
	Зона.Площадь,
	Зона.ИндексКоробки
ПОМЕСТИТЬ Зона
ИЗ
	&Зона КАК Зона
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ ПЕРВЫЕ 1
	&НомерКороба КАК НомерКороба,
	Зона.ИндексКоробки,
	Зона.Лево КАК Лево,
	Зона.Тыл КАК Тыл,
	Зона.Низ,
	Зона.Право КАК Право,
	Зона.Фронт,
	Зона.Высота КАК Высота
ИЗ
	Зона КАК Зона
ГДЕ
	Зона.Низ + Зона.Высота <= &Высота

УПОРЯДОЧИТЬ ПО
	Зона.Площадь * Зона.Низ - Зона.Опора,
	Зона.Площадь * Зона.Высота УБЫВ,
	Зона.Низ + Зона.Высота,
	Лево,
	Тыл,
	Право
Показать
результат - строка с номером коробки, которая оптимально (на этой итерации) заполняет свободное место ящика.

2. Про Количество - ок. (это тоже для меня загадка была)

3. (и 2 - УкладкаКоробки), запрос
ВЫБРАТЬ
	Зона.Лево,
	Зона.Тыл,
	Зона.Низ,
	Зона.Право,
	Зона.Фронт,
	Зона.Высота,
	Зона.Опора,
	Зона.Площадь,
	Зона.ИндексКоробки
ПОМЕСТИТЬ Зона
ИЗ
	&Зона КАК Зона
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Укладка.НомерСтроки,
	Укладка.ИндексКоробки,
	Укладка.Лево,
	Укладка.Тыл,
	Укладка.Низ,
	Укладка.Право,
	Укладка.Фронт,
	Укладка.Высота
ПОМЕСТИТЬ Укладка
ИЗ
	&Укладка КАК Укладка
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ ПЕРВЫЕ 1
	Укладка.ИндексКоробки,
	Укладка.Лево,
	Укладка.Тыл,
	Укладка.Низ,
	Укладка.Право,
	Укладка.Фронт,
	Укладка.Высота
ПОМЕСТИТЬ Коробка
ИЗ
	Укладка КАК Укладка

УПОРЯДОЧИТЬ ПО
	Укладка.НомерСтроки УБЫВ
;

////////////////////////////////////////////////////////////­////////////////////
ВЫБРАТЬ
	Зона.Лево,
	Зона.Тыл,
	ЕСТЬNULL(ВЫБОР
			КОГДА Коробка.Низ + Коробка.Высота > Зона.Низ
				ТОГДА Коробка.Низ + Коробка.Высота
		КОНЕЦ, Зона.Низ) КАК Низ,
	Зона.Право,
	Зона.Фронт,
	Зона.Высота,
	Зона.Опора + ЕСТЬNULL((ВЫБОР
			КОГДА Коробка.Право < Зона.Право
				ТОГДА Коробка.Право
			ИНАЧЕ Зона.Право
		КОНЕЦ - ВЫБОР
			КОГДА Коробка.Лево > Зона.Лево
				ТОГДА Коробка.Лево
			ИНАЧЕ Зона.Лево
		КОНЕЦ) * (ВЫБОР
			КОГДА Коробка.Фронт < Зона.Фронт
				ТОГДА Коробка.Фронт
			ИНАЧЕ Зона.Фронт
		КОНЕЦ - ВЫБОР
			КОГДА Коробка.Тыл > Зона.Тыл
				ТОГДА Коробка.Тыл
			ИНАЧЕ Зона.Тыл
		КОНЕЦ) * Коробка.Высота, 0) КАК Опора,
	Зона.Площадь,
	Зона.ИндексКоробки
ИЗ
	Зона КАК Зона
		ЛЕВОЕ СОЕДИНЕНИЕ Коробка КАК Коробка
		ПО (Зона.Тыл <= Коробка.Тыл
					И Коробка.Тыл < Зона.Фронт
				ИЛИ Коробка.Тыл <= Зона.Тыл
					И Зона.Тыл < Коробка.Фронт)
			И (Зона.Лево <= Коробка.Лево
					И Коробка.Лево < Зона.Право
				ИЛИ Коробка.Лево <= Зона.Лево
					И Зона.Лево < Коробка.Право)
ГДЕ
	Зона.ИндексКоробки <> &ИндексКоробки
Показать
&Укладка - это что/как/откуда (очень похоже на Зону)?
Результат - обновлённая Зона (я правильно понял)?

КонецЦикла

Результат - таблица Зона с упаковками и координатами их.
Но (вопрос) - у нас ведь может быть 3 штуки Упаковок и для них ведь всё разное должно быть в результате (кроме ИндексКоробки). Я снова не пойму - где у нас результат для (с координатами) каждой упаковки?
72. ildarovich 7846 29.09.14 16:37 Сейчас в теме
(71) Salavat, нет, весь результат - это таблица "Укладка".
К ней по одной на каждом шаге добавляются строки, выбираемые из таблицы "Зона".
Кстати, и номер короба (ящика) туда пишется.
"Зона" - это рабочая таблица ВСЕХ вариантов, а "Укладка" - это полученное размещение.
Именно поэтому в процедуре "Укладка" из таблицы Укладка выбирается одна последняя строка. Она была только что добавлена при выборе места. И эта строка используется для корректировки рабочей таблицы "Зана". В итоге в таблице "Укладка" столько строк, сколько было всего в сумме коробок (упаковок) в заказе. А в таблице "Зона" число строк - это число вариантов положить одну из оставшихся коробок на очередном шаге.
Вообще куда складывать результат и прочее - это не столь существенные технические подробности. Они с алгоритмом не так уж сильно связаны. Это я к тому, что в других версиях обработки можно сделать (и сделано) по-другому.

Кстати, думал, что в отправленном мною тексте это было, а оказывается - нет. Вот основной цикл:
НомерКороба = 0;
Укладка.Очистить();
Инициализация();
Пока Приземление() Цикл
     НомерКороба = НомерКороба + 1;	
     Пока ВыборМеста() Цикл
	     УкладкаКоробки()
     КонецЦикла
КонецЦикла
Показать
73. Salavat 13 29.09.14 17:04 Сейчас в теме
(72) "Вообще куда складывать результат и прочее - это не столь существенные технические подробности." - разве?
А если у нас расчитанное положение позиции на дне (допустим) только, а мы (не зная это) заложили его место другими?
При этом - позиции у нас не очень лёгкие.

Или я снова не понял.
74. ildarovich 7846 29.09.14 18:05 Сейчас в теме
(73) Salavat, про технические подробности я имел ввиду не подробности алгоритма укладки, а подробности реализации в виде обработки. Дело в том, что функции и структуры данных выдернуты из обработки, используемой для отладки. Где данные загружаются и выгружаются в запрос лишние разы, чтобы видеть, что происходит. Отвечая на вопрос: какая таблица для чего, я уже говорю не про алгоритм, а про подробности реализации, которая может быть и другой при сохранении основной идеи, но я отвлекся...

Давайте еще раз другими словами о том, в чем суть алгоритма:

Коробки укладываются по одной, начиная с дна ящика. Так, как их укладывает человек. Мы не можем выбрать место для очередной коробки, чтобы она висела в воздухе - она должна опираться на дно или другие коробки. Для каждого шага имеется таблица вариантов "Vista" (как в статье). Каждая запись-вариант в таблице хранит номер коробки, положение ее левого и правого, ближнего и дальнего края, низа и высоты. В самый первый момент коробки "приземлены" - во всех вариантах низ = 0 и коробки находятся на дне ящика. Также нулю равна пустота (незанятое место под коробками).
Далее выбираем один вариант. Значит, одна коробка зафиксирована на дне ящика. Теперь все варианты из таблицы, которые должны были занять то же место (или часть того же места) должны быть скорректированы, поскольку непосредственно на дно в этом месте положить другую коробку уже нельзя. Но другую коробку можно положить на верх уже положенной коробки. Поэтому у того варианта, который пересекается с уже положенной (положенная - это последняя строка в таблице укладка), должен быть увеличен "низ". Он должен стать равен верху уже положенной коробки.
То есть выбираем один конкретный вариант положить коробку, дописываем его к таблице "Укладка". И просматриваем все записи в таблице вариантов Зона. Те записи, которые стали неактуальны (невозможны физически), меняем, поднимая выше значение поля "низ". То есть постепенно низ всех коробок в таблице вариантов будет выше и выше, пока не превысит высоту ящика. Тогда мы возьмем новый ящик, "приземлим" оставшиеся варианты и так далее.
76. Salavat 13 30.09.14 09:54 Сейчас в теме
(74) эта строка (теперь)
ИндексКоробки = ?(Коробки[Строка.ИндексКоробки - 1].Количество = 0, Строка.ИндексКоробки, 0);
- меня озадачивает. что за
ИндексКоробки =
? оно ведь нигде не используется.
Почему оно - или Строка.ИндексКоробки, или 0 ?

подозреваю должно быть уменьшение Строка.ИндексКоробки для
... Коробки[Строка.ИндексКоробки - 1]...
но, это я только подозреваю, как/что/куда/откуда/... - я снова не вижу.
75. Salavat 13 30.09.14 07:57 Сейчас в теме
(72) за
НомерКороба = 0;
Укладка.Очистить();
Инициализация();
Пока Приземление() Цикл
НомерКороба = НомерКороба + 1;
Пока ВыборМеста() Цикл
УкладкаКоробки()
КонецЦикла
КонецЦикла
- Спасибо! удалось наконецто увидеть всю (надеюсь) тему.
удалось запустить, но (как я примерно и говорил изначально) - проблема с количествами!
нет проверки на количество в списке Номенклатуры. Точнее - оно есть, но такое, что я не понял как заставить его работать.

В итоге получил - бесконечный цикл - количество Номенклатуры уменьшается до бесконечности. Причём количество - только у последней строки номенклатуры - нет перехода по строкам Номенклатуры.

Файл прикладываю - УТ 10.3. В справочник Номенклатура добавлены реквизиты - Высота, Ширина, Глубина.

Помогите, пожалуйста.
Прикрепленные файлы:
ТрехмерноеРазмещениеТовара2.epf
80. Salavat 13 01.10.14 13:28 Сейчас в теме
Вобщем нашёл и проблема (в количествах) где кроится..........
А в таблице "Зона" число строк - это число вариантов положить одну из оставшихся коробок на очередном шаге.
(72) ildarovich - здесь не оставшиеся, а те, что были получены в самом начале.
но и это - только часть проблемы (подозреваю).

Автор, сделайте пожалуйста рабочий вариант или скажите (предметно) - как решить проблему.
ведь - нерабочий вариант же.
Прикрепленные файлы:
ТрехмерноеРазмещениеТовара5.epf
82. ildarovich 7846 01.10.14 14:09 Сейчас в теме
(80) Salavat, нужно было всего лишь реквизит "ИндексКоробки" (числового типа) добавить к реквизитам обработки. Тогда ИндексКоробки будет передаваться в запрос "Укладка" и при достижении нулевого количества такой номенклатуры она будет удаляться из таблицы Зона по условию. Об этом был пункт 2) в комментарии (70).
84. Salavat 13 01.10.14 15:32 Сейчас в теме
(82) пробовал - не вышло, в итоге добавил - в другое место. и - ......... короче через зад.

(83) никак они (эти колонки) в таблице Зона не меняются. в Укладке - да, они (эти колонки) разные.

Вобщем - вроде работает, но, как/что/правильноли/.............. - я точно не скажу сейчас. потому что - я уже описал что (неединственное).

Хотел поблагодарить (изначально), но честно - нет никакого желания (сейчас).
Вопрос задаю - получаю кучу слов, которые я не могу (за редким исключением, которое надо ещё найти/выудить из этой кучи) использовать, реально.
я же не за чтением романа сюда пришёл - зачем краснословии упражняться.

Почему? Потому что если я выкладываю, то стараюсь выложить понятное и/или рабочее. Если оцениваю это денежно, то - за деньги.
Иначе же - ничего не выкладываю, а просто пишу - я сделал офигенную вещь похвалите меня!

сами выберите - к какой стороне отнести себя.
85. ildarovich 7846 01.10.14 16:05 Сейчас в теме
(84) Salavat, я совершенно точно не хотел ничего пока выкладывать (в этой конкретной статье), то есть реализовал вариант:
ничего не выкладываю, а просто пишу - я сделал офигенную вещь - похвалите меня!
Это Вам что-то понадобилось и Вы стали меня просить. В итоге я Вам "за пожалуйста" постепенно с объяснениями переслал всю начинку своей обработки, которую использовал для отладки. При этом мне показалось, что Вам не очень хотелось разбираться, а хотелось получить готовый результат и таким образом Вы своей цели добились.- Удачи!
86. Salavat 13 01.10.14 16:22 Сейчас в теме
(85) не совсем так.
я увидел публикацию, расценил её как нечто полезное, но ......... и в ней, и в присланном изложено так, что ... - вобщем это нерабочее, а именно - согласились вобщем Вы.

мне только непонятно - Вы читаете литературу (я не имею ввиду - левые видеоуроки, например) и там тоже разбираетесь?
Я нет - я привык взять и прочитать. Прочитать столько, сколько понадобится, но чтоб читаемое было понятным, а не водой/соломой/.... разбавлено.

Цель моя (и здесь, и обычно) - решить. Решить, это значит - должно работать и я знаю как.
Сейчас же - я не уверен, что работает и не знаю как.

Зато в краснословии Вы себе не отказываете - Удачи!!
87. ildarovich 7846 01.10.14 16:54 Сейчас в теме
(86) Salavat, спасибо, приму к сведению
77. Salavat 13 30.09.14 15:03 Сейчас в теме
ildarovich, ну так что - что с количеством делать? как/когда/где/... его правильно учесть?
81. Salavat 13 01.10.14 14:01 Сейчас в теме
непонятно зачем нужны в Зоне колонки Опора и Низ - они же нулевые.
83. ildarovich 7846 01.10.14 14:12 Сейчас в теме
(81) Salavat, про это я уже писал, перечитайте внимательнее. Теперь, когда Ваша обработка уже должна работать, сможете посмотреть как меняются данные в этих колонках по мере укладки коробок в ящик.
90. Salavat 13 03.10.14 04:52 Сейчас в теме
(83) вобщем как я и подозревал - работает неверно.
рисует красиво, но цифры левые.
смог разобрать только, что он габариты берёт (или перемешивает их в расчёте - ширина вроде верна, а высота и глубина - нет) не от тех позиций.
при чём - логику проследить, у меня абслютно не вышло.

однозначно - результатт неверный.

Автор, разъясните пожалуйста.
88. CheBurator 3119 01.10.14 20:39 Сейчас в теме
...дайте уже обработку для 8-ки, потестить.... чтобы на вход задать можно было габариты "ящика-получателя" (дл, шир, выс) и размер коробки (дл, шир, выс), а на выходе - сколько коробок влезет в ящик - есть такое?
спсб!
89. ildarovich 7846 01.10.14 22:23 Сейчас в теме
(88) CheBurator, сделаю это в ближайшие дни.
104. CheBurator 3119 03.10.14 19:01 Сейчас в теме
(89) спасибо, буду очень ждать.
просьба по возможности учесть чятоя нв 8-ке полный олух. могу только в пользовательском режиме кнопки нажимать.
если взлетит - могу официальный отзыв дать от конторы о полезности.
105. CheBurator 3119 03.10.14 19:03 Сейчас в теме
(89) и на этапе "отладочной" эксплуатации было бы хорошо визализацию раскладки видеть - как это у вас в обработке нарисовано.
еще раз спасибо. буду ждать!!!!
можно писать в личку или на мыло e.meil@mail.ru
91. Salavat 13 03.10.14 05:03 Сейчас в теме
Единственное, что я заметил беспроблемное, это количество номенклатуры - оно верно (сейчас).
но, это очень трудно назвать решением данной задачи.
92. Salavat 13 03.10.14 07:15 Сейчас в теме
попытался разобраться в получаемой якобы-укладке - для 3 пробных позиций (по 10 штук):
1. высота:
у первой - получаеттся разная - от первой и второй позиции,
у второй - от первой,
у третьей - от второй и от той, которой нет вообще...

2. ширина:
у первой - от первой и третьей,
у второй - от первой,
у третьей - от третьей и несуществующей.

3. глубина:
у первой - от первой и несуществующей,
у второй - от несуществующей,
у третьей - от второй и третьей.

это всё, что я насмотрел.

подозреваю косяк(и) в запросах/переборе/...

но это - только моё подозрение.

Автор, прокомментируйте, пожалуйста.
93. ildarovich 7846 03.10.14 09:14 Сейчас в теме
(92) Salavat, пришлите, пожалуйста, мне на почту текущий вариант отлаживаемой обработки - я его посмотрю.
Оставьте свое сообщение