gifts2017

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

Опубликовал Сергей (ildarovich) в раздел Программирование - Практика программирования

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

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

Беглый анализ показал, что задача “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, но это были отнюдь не достигнутые проценты утилизации объема короба. - Вот такой парадокс психологии!

См. также

Подписаться Добавить вознаграждение
Комментарии
1. Сергей (ildarovich) 24.03.14 20:28
Эта статья написана для публикации на сайте habrahabr.ru, поэтому запросы были переведены на английский.
support; Evil Beaver; +2 Ответить 2
2. Алексей 1 (AlX0id) 24.03.14 23:40
(1) ildarovich,
И именно поэтому вот таким вот незамысловатым образом вы описываете 1с? ))
Фреймворк, с которым мы работаем, основан на скриптовом языке. Хотя язык достаточно гибок и обвешен по принципу рождественской елки всякими хлопушками и погремушками, включая даже методы математической статистики, он не очень хорошо приспособлен для задач с объемными вычислениями. Обычный цикл у нас выполняется гораздо дольше, чем в компилируемом языке. Поэтому простые, но массовые вычисления бывает удобнее делать на стороне сервера непосредственно на уровне СУБД. Для работы с базой данных у нас используется язык, очень похожий на T-SQL.
dabu-dabu; naumenko_alex; tarassov; hotey; smit1c; +5 Ответить 1
3. Игорь Хитров (Новенький_2209) 24.03.14 23:57
Причем наиболее глубокое впечатление почему-то осталось у тех, кого я подвозил тогда на своей синей импрезе. Все запомнили число 200, но это были отнюдь не достигнутые проценты утилизации объема короба. - Вот такой парадокс психологии!


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

откуда взято
4. Александр Кунташов (kuntashov) 25.03.14 02:31
Хорошая статья! Должно взлететь )
5. Юрий Гончарук (yukon) 25.03.14 14:15
(2) AlX0id,
И именно поэтому вот таким вот незамысловатым образом вы описываете 1с?


Мне тоже понравилось. Описание просто шикарное.
6. Алексей Т. (CratosX) 26.03.14 09:26
7. Андрей Овсянкин (Evil Beaver) 26.03.14 10:23
Ildarovich опять творит невозможное запросами. А можно туповатым, вроде меня, объяснить что делают запросы, особенно тот, что с вращением?
8. Сергей (ildarovich) 26.03.14 11:00
(6) Так Вы считаете эту шутку лучше убрать? (на хабре)
9. Сергей (ildarovich) 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

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

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

Хотелось бы видеть в алгоритмах здравый смысл:
1. по сумме объемов мелких коробок определяется минимальная основная коробка.
2. располагать основную коробку на столе упаковки следует наибольшей по площади гранью.
3. начинать упаковывание следует с более крупных коробок, которые могут быть расположены или на дне основной коробки или вдоль торца основной коробки
4. в оставшиеся "прорези" по возможности упаковываем подходящие мелкие коробочки
5. и т.д. с оставшейся свободной частью основной коробки - хотя понимаю, что реализация здравого смысла приведет как раз-таки к подобному сложному решению - перебору вариантов.
16. г. Казань Рустем Гумеров (Rustig) 31.03.14 06:56
17. Андрей Овсянкин (Evil Beaver) 31.03.14 11:04
Кстати, поскольку в общем виде задача является NP-полной, то какие ограничения имеют её существующие прикладные решения?
18. Сергей (ildarovich) 31.03.14 12:40
(15) Сложным алгоритм является только на первый взгляд. Я просто не стал его "разжевывать", имея ввиду, что приложены запросы, по которым можно разобраться.
На самом деле по сути это семейство алгоритмов. Общим является способ генерации ВСЕХ возможных вариантов укладки коробки (с учетом дискретизации) на каждом шаге и коррекции этих возможностей после ВЫБОРА одного варианта. Выбор варианта можно производить по разным критериям (эвристикам). Например, как показано в тексте конкретного запроса выбора сначала можно класть ту коробку, под которой будет оставаться минимум пустого пространства. А можно, изменив порядок сортировки (все остальное также) сначала класть наиболее объемную коробку или коробку наибольшей площади.
С точки зрения программирования выбора алгоритм более чем прост - достаточно задать порядок сортировки в соответствующем запросе.
Если повернуть основную коробку на бок - получим другое решение! Но так делать нежелательно, так как загружать коробку сбоку неудобно. Если окажется, что последнюю коробку потребуется поместить к верху задней стенки - в некоторых случаях это будет физически не возможно.
Можете попробовать сформулировать свою эвристику 1-5 в виде порядка сортировки - должно получиться. Можно будет провести испытания. Если в среднем плотность упаковки с использованием вашей эвристики окажется больше, можно выбрать ее.
Испытания приведенной эвристики показали на стандартных тестах (они опубликованы) результат 69-72%. Но у нас не было задачи увеличивать этот процент. Заказчики посчитали его достаточным. Тем более натурные эксперименты показали, что человек-упаковщик обеспечивает примерно такой-же процент.
Судя по литературе, борьба за каждый процент свыше 77% многократно усложняет алгоритм.
19. Сергей (ildarovich) 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Д пакера. Кажется, это разработка команды из МГУ и теоретические основы их метода описаны в соответствующих работах. Там нет одной ясной идеи. Используется композиция приемов сведения задачи к двумерному случаю, если я правильно помню.
20. Сергей (ildarovich) 31.03.14 13:20
(17) Не могу сейчас ответить на этот вопрос. Поскольку для этого нужно произвести отдельное исследование. Тем более, кажется, в последнее время появилось еще ряд решений.
Но исходя из соображений "здравого смысла" все предлагаемые решения решают за приемлемое время (секунды) типичные практические задачи: загрузку кузова автомобиля, морского контейнера, вагона. Борьба идет не за проценты полезного использования объема контейнера (именно это касается математической сложности задачи и ее NP-полноты), а за другие вещи: удобство интерфейса, возможность ручных корректировок, наглядность представления получаемой упаковки, учет не прямоугольных упаковок, веса, совместимости грузов, устойчивости укладки и тому подобное.
Предложенный метод ограничен тем, что работает с дискретным положением упаковок (укладка с точностью до сантиметра или НОД длин сторон упаковок). Время его работы прямо пропорционально произведению W x D x K x N, где W, D - размеры дна короба, K - число разноразмерных упаковок, N - число упаковок.
21. Алексей Новоселов (a-novoselov) 03.04.14 09:47
(0) Молодцы, красивое решение! Особенно после того, как несколько раз приходилось исправлять гениальные отчеты, в которых просроченная задолженность в циклах считается, очень приятно видеть такие решения запросами.

(8) Насчет Хабра, думаю, вас все равно завалят вопросами "Что за скриптовый язык такой?", так что лучше сразу написать что в 1С это делалось. Но и уточнение, что встроенный язык это интерпретатор, не сильно предназначенный для объемных вычислений и тормозящий на больших циклах, тоже опускать не стоит.
22. Епрст (Ёпрст) 03.04.14 12:23
(0)
Это , а алгоритм рисования есть самого упаковочного листа ?
Он должен быть не менее интересным.
23. Alex_IT (Alex_IT) 03.04.14 12:25
(22) +1
И инструмент рисования...
24. Сергей (ildarovich) 03.04.14 12:56
(22) (23) Там все очень просто - это табличное поле 1С, используются его объекты-рисунки: линии и прямоугольники. Координаты, определяющие положение фигур считаются как проекции трехмерных координат на плоскость за коробкой. Это несложные формулы с элементами тригонометрии.
В общем-то, если бы было нужно, можно было бы этими средствами и мультфильм, показывающий порядок упаковки, изобразить (своеобразный тетрис 3D).
Но вот если вдруг понадобится удалять невидимые грани, будет непросто, так как нет объекта, который бы позволил залить цветом многоугольную область, чтобы воспользоваться методом z-буфера.
25. Епрст (Ёпрст) 03.04.14 13:04
(24) мот, мини демо-пример?
А то смутно представляю, как "палочки" рисовать в табличном поле, еще и разным цветом, еще и с циферкой в углу.
26. Епрст (Ёпрст) 03.04.14 13:08
+ не ясно, почему на рисунке между коробами "пустоты" .. они же лежат друг на друге, а не "висят" в воздухе ? Или это для облегчения "чтения" упаковочного листа ?
27. Сергей (ildarovich) 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 Ответить 2
28. Сергей (ildarovich) 03.04.14 13:19
(26) Я уже говорил в комментарии (10), что
при выводе картинки размеры упаковок специально чуть сокращены внутрь их объема, так как иначе грани упаковок накладывались друг на друга и было вообще трудно что-либо разобрать. Поэтому расстояние, которое отделяет упаковки друг от друга на картинке не всегда есть в реальности
29. Епрст (Ёпрст) 03.04.14 13:21
Ага спасибо, еще пара уточняющих вопросов и мы из автора вытащим весь код целиком :)

ЗЫ: на счет "пустот", это так и задумано ? Для простоты визуального восприятия ?
30. Епрст (Ёпрст) 03.04.14 13:22
31. Епрст (Ёпрст) 03.04.14 13:23
Жалко только, что алгоритм не всем подходит, нужно еще учитывать вес коробки и его "хрупкость", это если уж совсем "правильно" укладывать
32. Сергей (ildarovich) 03.04.14 13:34
(29) Да пожалуйста. На самом деле я собирался привести и обработку целиком, но для Хабра она не интересна, да и к статье ее сейчас приложить нельзя, поэтому чуть сэкономил время. Поскольку для публикации обработки еще нужно привести способ хранения габаритов упаковок, так как в штатной УТ10 его нет, а в УТ11 есть габариты, но тара не так определяется. В общем, пока решил с этим не спешить.
33. Сергей (ildarovich) 03.04.14 13:38
(31) И вес коробки и хрупкость можно учесть - все регулируется порядком сортировки в соответствующем запросе, куда можно добавить указанные поля.
34. Епрст (Ёпрст) 03.04.14 15:32
Круто, если демку оформите, хотя бы с одним справочником и одним документом.
35. Дмитрий Г (Дмитрий74Чел) 04.04.14 08:21
(1) Я уж хотел написать "и что эта статья с Хабра делает на Инфостарте"? :-)
36. Андрей Овсянкин (Evil Beaver) 04.04.14 10:11
(32) ildarovich, кстати, когда ждать статью на хабре?
37. Сергей (ildarovich) 04.04.14 13:13
(36) Вообще-то статья уже вышла. Это было 28.03.14. Вот ссылка.
38. Андрей Овсянкин (Evil Beaver) 07.04.14 10:15
(37) ildarovich, извиняюсь, не заметил ее там.
39. Андрей Киреев (FractonKireyev) 11.04.14 17:46
Чем была нарисована картинка со схемой укладки в коробку?
40. Андрей Киреев (FractonKireyev) 11.04.14 17:53
По поводу хрупкости (для (31) и (33)).
Всё совсем не так просто. Если товар лежит так (считаем, что твёрдые коробки не ниже хрупкой):

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

то длинную и тяжёлую коробку можно положить поперёк (так, чтобы концы опирались на твёрдые коробки) и нельзя вдоль хрупкой (раздавит).
Так что просто сортировкой в запросе просто так не отделаться - нужны какие-то другие алгоритмы.
41. Сергей (ildarovich) 11.04.14 19:18
(39) FractonKireyev, в комментарии (27) я уже отвечал на этот вопрос. Это чистый 1С, используется поле табличного документа и объект "рисунок" типа линия. В том же комментарии приведен ВЕСЬ необходимый код рисования блока.
(40) Вариантов алгоритмов великое множество. Тот вариант, о котором говорите Вы (твердые должны опираться на твердые), можно считать подмножеством приведенного, если в нем ввести сортировку по критерию минимизации опоры на хрупкие коробки.
42. Alex_IT (Alex_IT) 13.04.14 13:33
(32) ildarovich, Интересно увидеть обработку, в любом виде, даже без возможности использования в типовых. Само рисование в 1С ну очень куцее и любое удачное визуальное решение всегда вызывает интерес.
43. Сергей (ildarovich) 13.04.14 15:00
(42) Alex_IT, обработку я со временем выложу, приспособив ее и к 10.3 и к 11 (уже почти все готово). Но если Вас интересует только рисование, обратите внимание на мой комментарий (23). Там приведен ВЕСЬ код из обработки, необходимый для рисования блоков в 2,5 D.
48. Сергей (Che) Коцюра (CheBurator) 14.04.14 22:30
Вообще, конечно автор молодец!
еще в запросы впихнуть ограничения по каждой коробке (типа нельзя ставит на торец или типа как хрупкое с опорой выше)... и демо конфу минимальную... передавать в "пакете" исходные коробки на выходе получать раскладки...
49. Сергей (Che) Коцюра (CheBurator) 14.04.14 22:32
вообще не сильно понятно наскольо эффективно работает такая упаковка ФИЗИЧЕСКи - ладноя понимаю палеты/конейтнеры комплектовать, но коробки размером 60см на 80... на 40... если упаковке подлежит большое колво разноообразного товара то имхо упаковщики которые стоят на упаковке сделают близко к оптимальному и без раскладки...
.
окупается ди сам процесс УПАКОВКИ КОРОБОК ПО СХЕМЕ?
50. Сергей (ildarovich) 21.04.14 13:51
(49) CheBurator,
упаковщики которые стоят на упаковке сделают близко к оптимальному и без раскладки...
Сам так думал, но недавно, после того, как вспомнили про задачу в связи со статьей, мы провели эксперимент: двух стажеров попросили заполнить короб разными найденными в офисе коробочками. Удивительно, но стажеры во всех попытках справились с работой хуже программки. Правда, мои коллеги отнесли все на способности стажеров, но все же факт остается фактом.
А про окупаемость можно рассудить так: если нужны упаковочные листы, то можно
1) получить их заранее и разложить товар по коробкам в соответствии с ними, подглядывая в упаковочный лист;
2) получить упаковочный лист после укладки, просканировав товар.
Кажется, первый вариант, не требующий сканера и лишнего хождения к принтеру, выглядит экономичнее.
Если упаковочные листы не нужны, то смысла тратить явно большее время на укладку по просчитанной схеме нет. Лучше натренировать упаковщика.
51. Андрей Антипенко (Kopman) 10.06.14 08:18
Хорошая статья. Присоединяюсь к желающим увидеть обработку.
52. Александр Куклин (alexandr851c) 21.07.14 14:28
Хотелось бы увидеть обработку. Будет ли она выложена?
53. Сергей (ildarovich) 21.07.14 16:39
(52) alexandr851c, обработка будет выложена. Когда - пока сказать не могу.
54. Александр Куклин (alexandr851c) 24.07.14 09:51
(53) ildarovich, а можете кинуть саму процедуру упаковки ))) Заранее огромное спасибо.
55. Валерий (scientes) 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 Ответить 1
56. Сергей (ildarovich) 31.07.14 14:51
(55) scientes, вы очень внимательны. Ошибку исправлю. Она появилась в ходе перевода запроса на английский. Сам принцип такого способа генерации множества чисел изложен в статье "Порождающий запрос".
57. Salavat (Salavat) 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,
, и аналогичные...

Автор, прокомментируйте пожалуйста.
58. Сергей (Che) Коцюра (CheBurator) 23.09.14 23:39
мне бы данная обработка пригодилась бы для расчета "сколько однотипных коробок влезитя в ячейку заданного размера".
59. Сергей (ildarovich) 24.09.14 09:04
(58) CheBurator, конечно, данный подход решит эту задачу, но для нее есть гораздо более простые способы. Что мешает поделить длину ячейки на длину одной упаковки, ширину ячейки на ширину упаковки, высоту ячейки на высоту упаковки, затем взять целые части результатов деления и перемножить их? Или упаковки можно по-разному вращать при складывании?
60. Сергей (Che) Коцюра (CheBurator) 24.09.14 10:15
(59) да, можно по разному, например укладка на палете (ну и соответственно в ячейке резервного хранения) может быть вот такой
http://screencast.com/t/6HLjQIxZl0p (вид на палету сверху) - 7 коробок в слое, следующий слой кладется наоборот : 2 коробки получатся слева...
как например посчитать такую раскладку слоя сходу - навскидку не соображу. Здесь что "хорошо" - все коробки одного размера.
.
при такой раскладке высота всех коробок одинаковая.
а вот например при запихивании в ячейку активного хранения можно извращаться и посильнее - какие-то коробки на торец ставить и т.д. - будет ли при этом выигрыш - хз...
61. Сергей (ildarovich) 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 (Salavat) 25.09.14 15:27
(61) ildarovich, а что за переменные &Высота, Ширина, Глубина - это размеры Номенклатуры или Ящика?
63. Сергей (ildarovich) 26.09.14 10:26
(62) Salavat, это размеры ящика (короба)
64. Salavat (Salavat) 26.09.14 15:55
(61) ildarovich,
...
Зона.ИндексКоробки, 
Зона.Лево КАК Лево, 
Зона.Тыл КАК Тыл, 
Зона.Низ, 
Зона.Право КАК Право, 
Зона.Фронт, 
Зона.Высота КАК Высота,
...
Зона.Опора,
Зона.Площадь,
...
...Показать Скрыть

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

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

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

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

67. Salavat (Salavat) 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) 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 (Salavat) 29.09.14 13:02
(68) ildarovich, ок. Спасибо.

да - размеры в сантиметрах, но с 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) 29.09.14 13:35
(69) Salavat, миллиметры нужно отсечь. Обязательно.

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

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

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

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

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

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

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

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

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

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

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

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

КонецЦикла

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

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

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

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

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

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

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

Помогите, пожалуйста.
Прикрепленные файлы:
ТрехмерноеРазмещениеТовара2.epf
76. Salavat (Salavat) 30.09.14 09:54
(74) ildarovich, эта строка (теперь)
ИндексКоробки = ?(Коробки[Строка.ИндексКоробки - 1].Количество = 0, Строка.ИндексКоробки, 0);
- меня озадачивает. что за
ИндексКоробки =
? оно ведь нигде не используется.
Почему оно - или Строка.ИндексКоробки, или 0 ?

подозреваю должно быть уменьшение Строка.ИндексКоробки для
... Коробки[Строка.ИндексКоробки - 1]...
но, это я только подозреваю, как/что/куда/откуда/... - я снова не вижу.
77. Salavat (Salavat) 30.09.14 15:03
ildarovich, ну так что - что с количеством делать? как/когда/где/... его правильно учесть?
78. Salavat (Salavat) 30.09.14 19:58
и попутно - опять ведь перемешано - (27) ildarovich,
Функция ДобавитьПрямую(Рисунки, 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 (Salavat) 01.10.14 12:52
(78) Salavat, Вобщем с рисованием разобрался (рисование написал по-своему) - вопрос отменяется.
Попутно выяснилось, что в Укладке нет Номера Ящика - добавил и его.

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

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

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

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

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

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

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

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

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

Зато в краснословии Вы себе не отказываете - Удачи!!
87. Сергей (ildarovich) 01.10.14 16:54
(86) Salavat, спасибо, приму к сведению
88. Сергей (Che) Коцюра (CheBurator) 01.10.14 20:39
...дайте уже обработку для 8-ки, потестить.... чтобы на вход задать можно было габариты "ящика-получателя" (дл, шир, выс) и размер коробки (дл, шир, выс), а на выходе - сколько коробок влезет в ящик - есть такое?
спсб!
89. Сергей (ildarovich) 01.10.14 22:23
(88) CheBurator, сделаю это в ближайшие дни.
90. Salavat (Salavat) 03.10.14 04:52
(83) ildarovich, вобщем как я и подозревал - работает неверно.
рисует красиво, но цифры левые.
смог разобрать только, что он габариты берёт (или перемешивает их в расчёте - ширина вроде верна, а высота и глубина - нет) не от тех позиций.
при чём - логику проследить, у меня абслютно не вышло.

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

Автор, разъясните пожалуйста.
91. Salavat (Salavat) 03.10.14 05:03
Единственное, что я заметил беспроблемное, это количество номенклатуры - оно верно (сейчас).
но, это очень трудно назвать решением данной задачи.
92. Salavat (Salavat) 03.10.14 07:15
попытался разобраться в получаемой якобы-укладке - для 3 пробных позиций (по 10 штук):
1. высота:
у первой - получаеттся разная - от первой и второй позиции,
у второй - от первой,
у третьей - от второй и от той, которой нет вообще...

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

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

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

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

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

Автор, прокомментируйте, пожалуйста.
93. Сергей (ildarovich) 03.10.14 09:14
(92) Salavat, пришлите, пожалуйста, мне на почту текущий вариант отлаживаемой обработки - я его посмотрю.
94. Сергей (ildarovich) 03.10.14 14:07
(93) Я уже переписал и исправил обработку, составленную без особенного понимания исключительно из моих ответов, был готов ее отправить. В личной переписке корреспондент был предупрежден, что одним из условий было ее использование для апробации, для одного конкретного клиента и нераспространение. Она лежала в папке "Исходящие".
Но тут мне прислали интересную ссылку ....
Оказалось, что еще не работающая обработка, построенная из моих запросов и бесплатных советов с 1-го октября уже продается на сайте ... под авторством Салавата за целых 15 000 рублей!. (сейчас он уже обещал ее убрать)

-Так что держите ухо востро!
Прикрепленные файлы:
95. Анатолий Бритько (headMade) 03.10.14 15:01
(94) ildarovich,
хуже умных врагов - только хитрожопые друзья )))
96. Salavat (Salavat) 03.10.14 15:40
(94) ildarovich, сразу обозначу свою т.з. - еслиб меня не заинтересовала тема, я бы не задавал столько вопросов.

по ответу - автор похоже с головой своей не совсем дружит. по-крайней мере - в этот момент.
1. Любой человек, видя объём вопросов (непустых и от одного человека) прекрасно поймёт, что тема заинтересовала. И не по тому, что запор долгий в туалете.
2.
...личной переписке корреспондент был предупрежден, что одним из условий было ее использование для апробации, для одного конкретного клиента и нераспространение
- гляньте в переписку, освежите память свою сначала. Более того - в той же переписке предлагалась цена (да, не золотые горы и он вроде обещал подумать/торговаться, но ... видя его обещания здешние, с апреля - я засомневался уже).

И последнее (надеюсь) - Вы хоть ради общего обзора - гляньте ст. 138, 137,..(остальное, из той же главы - тоже не помешает) УК РФ. Конкретно - я про переписку имею ввиду.
и - не говорите, что я вдруг угрожаю (малоли...). Я опять же - прошу только.
Надеюсь хотя бы про последнее (малоли...) не скажете, что я снова присваиваю чужое авторство.
97. Сергей (ildarovich) 03.10.14 16:38
(96) Salavat, а не Вы ли пытались продать мою обработку за 15 000 рублей под видом своей на сайте ...? А не Вас ли поймали за руку на конкретном плагиате "на горячем"? А не лучше ли сейчас покраснеть и публично извиниться?
98. Salavat (Salavat) 03.10.14 16:56
(97) ildarovich,
1. я нашёл тему.
2. задавал вопросы автору и предлагал ему оплату.
3. сделал (как думал - правильно) разместил.
4. я ни где не писал про своё авторство, продавать и говорить об авторстве - это разные вещи, если Вы не в курсе.
и - я тоже могу Вас обвинить в плагиате - немоего, разумеется, но пардон - в теме также не вижу упоминаний про то, откуда/какие/методы взяты. Былиб я б элементарно прошёлся по ним сначала, т.к. здесь - не всё есть.

где я не прав/вру/... - за что я должен извиниться?

я могу также сказать - что это Вы мою обработку себе приписываете? (см. 4...)

может хватит бахвальства излишнего? я почемуто подумал, что по т/ф мы договорились уже.
99. Salavat (Salavat) 03.10.14 17:13
(97) ildarovich, чувствую Вы снова разницу не знаете, разъясняю:
"моё" - это можно сказать когда Вы мне дали (я украл - б.р.) и я её (1к1 ну или минимум изменений) продаю.
я (не отрицал этого никогда, но меня об этом и не спрашивал никто, спросили/попросилиб я бы сказал/написал) - получил от Вас тексты, пытался их собрать безуспешно (ну да - с помощью Вашей всё же получилось, почти).
но пардон - я тоже руку приложил к этому, немалую.

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

Вы уж разберитесь с собой - кто не прав.
я предложил ведь - чаю попить, успокоиться сначала.
100. Salavat (Salavat) 03.10.14 17:23
(97) ildarovich, и - я пишу "я прошу (меня просить)" (в этой теме), имею ввиду буквально - просьба и мой ответ. возможный,
про деньги здесь - я даже не заикался. если у Вас это также возмущение вызывает.
101. Сергей (ildarovich) 03.10.14 18:24
(98) Salavat,
1. я нашёл тему.
- на первой странице Инфостарт
2. задавал вопросы автору и предлагал ему оплату.
Очень-очень-очень много вопросов, предложив для начала за готовую обработку(а мне и не нужно) 1,5(!!!) тысячи российских рублей
3. сделал (как думал - правильно) разместил.
- сложил вместе все присланные ФУНКЦИИ, даже не запросы - я замучился объяснять куда их вставлять и прислал все ключевые функции, а рисование еще раньше в одном из комментариев показал. То есть где это сделанное? В той выложенной (Вашей ее назвать нельзя) обработке практически нет никакого, кроме моего, кода, да еще В МОДУЛЕ ФОРМЫ, а не там, где полагается.
4. продавать и говорить об авторстве - это разные вещи
то есть можно продавать чужое, не уведомляя автора и не спрашивая его разрешения? - И много такого Вы уже напродавали? - Может быть, всем теперь нужно свои карманы проверить? По поводу того, что этот метод мной у кого-то заимствован - бред сивой кобылы - метод я придумал с "0", прочитав несколько статей на английском языке в зарубежных журналах (список первоисточников я приводил в одном из комментариев). Впрочем, проводить себе во вред тут ликбез по авторскому праву я не буду.
102. Сергей (ildarovich) 03.10.14 18:33
(99) Salavat,
я тоже руку приложил к этому, немалую
- в чем это можно заметить?

Успокаиваться мне не нужно, так как я и так совершенно прав и оттого абсолютно спокоен. Просто некорректно и агрессивно себя ведете и мне нужно бы поставить Вас на место.
103. Salavat (Salavat) 03.10.14 18:57
на первой странице Инфостарт
- допустим - это как влияет?

Очень-очень-очень много вопросов, предложив для начала за готовую обработку(а мне и не нужно) 1,5(!!!) тысячи российских рублей
выше в теме я уже сказал много раз - почему и также сказал про цену. могу повторить ещё раз.

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

обработке практически нет никакого, кроме моего, кода, да еще В МОДУЛЕ ФОРМЫ, а не там, где полагается.
в своём глазу бревно не вижу - напоминать надеюсь ненужно. где располагать - я сам решил, т.к. - получил от Вас тексты голые.

то есть можно продавать чужое, не уведомляя автора и не спрашивая его разрешения? - И много такого Вы уже напродавали? - Может быть, всем теперь нужно свои карманы проверить? По поводу того, что этот метод мной у кого-то заимствован - бред сивой кобылы - метод я придумал с "0", прочитав несколько статей на английском языке в зарубежных журналах (список первоисточников я приводил в одном из комментариев). Впрочем, проводить себе во вред тут ликбез по авторскому праву я не буду.
я уже ответил про разницу чужого и нечужого и применении к вашему коду тогоже. повторить? я не говорил, что Ваш метод/код заимствован у когото. я сказал - нет упоминания про статьи.

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

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

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

О чём мы договорились - я исполнил? Так чтож Вы всё не отстанете наконец?

Повторю - я не считаю себя в чём-либо виноватым перед Вами.
Добавлю - если посчитаю себя виноватым (перед Вами) - здесь же публично принесу извинения. Я в этом - проблем не испытываю.