LINUX.ORG.RU

Разместить предметы в ограниченном пространстве на JavaScript

 


0

2

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

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

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

Интересует два вопроса:
- Как лучше рисовать произвольные изображения для такого случая? Предполагаю, что canvas, хотя никогда его не пробовал.
- И собственно, алгоритм. Наверняка есть такие, пусть не готовые для JS, но хотя бы описание, порядок действий?

И, да, если есть какие-нибудь правильные библиотеки для этих целей (рисование и расчет), буду рад узнать...

это NP-полная задача, боюсь только полным перебором вариантов ты ее сможешь решить.

чем рисовать - Cancas, SVG, можно и DIV'ами с CSS3 3d-transform (к примеру, гугл кубик рубика недавно так рисовал в дудлах), можно на PHP картинку сгенерровать и выводить уже готовую.

BaBL ★★★★★ ()
Ответ на: комментарий от Moonysh

Что может быть крутого в "методе научного тыка"?

И, кстати, нафига решать это жабоскриптом, если можно просто написать нормальный сишный CGI, а клиенту уже данные отдавать и webgl'ем рисовать!

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

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

ddos3 ()
Ответ на: комментарий от Moonysh

Я правильно понимаю, что это невозможно решить за конечное время?

Нет, неправильно. Из википедии: «Всякую задачу о принадлежности слова x языку L, лежащую в классе NP, можно решить за экспоненциальное время перебором всех возможных сертификатов длины меньше |x|^c.» То есть время решения полным перебором хоть и экспоненциальное, но все же конечное. Решать такие задачи полным перебором можно в некоторых случаях, но делать это нужно очень осторожно.

ddos3 ()

Чуть менее чем во всех CAD-ах про одежду, раскрой материала со схожими задачами как правило можно даже реализацию сабжа увидеть… насчет 3D сомневаюсь.

init_6 ★★★★★ ()
Ответ на: комментарий от ddos3

Зря. Решение на мощном компьютере будет (возможно) секунд 10 длиться. Жабоскриптом ты несколько дней считать будешь!

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

Давай не будем забывать о том, что мы говорим о решении задачи в контексте системы управления складом или магазином, а не академического исследования. А это значит, что времени на решение мало, буквально секунда-две, но при этом можно (и нужно) пожертвовать точностью ради скорости.
Решение, на десять секунд под завязку забивающее CPU сервера по каждому клику пользователя, категорически не подходит.

ddos3 ()
Ответ на: комментарий от ddos3

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

ddos3 ()

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

Norgat ★★★★★ ()

Тебе повезло, чувак: https://github.com/zarkone/Containers

Это NP-полная задача о контейнерах, по ссылке — мой наскоро слепленый за день быдлокод на канвасе годичной давности.

Я сейчас туда заглянул, написано очень хреново, но возможно чем-то поможет.

zarkone ★★ ()
Ответ на: комментарий от zarkone

хотя отмена, там выше ссылку по-лучше дали, тред не прочитал

zarkone ★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.