Скачать: CL | DM;

"Алгоритм прямоугольников"?   Найти похожие ветки 

← →
DevilDevil ©   (2008-06-02 13:45) [0]

Извините за название, суть в следующем.

Есть сколько-то прямоугольников, разных размеров (размеры известны). Задача максимально компактно разместить их в прямоугольной "комнате" (размер "комнаты" тоже известен).

Есть ли какой вменяемый алгоритм для решения задачи ?

---

← →
Kerk ©   (2008-06-02 13:46) [1]

Эта задачка была на Google Code Jam Europe пару лет назад :)

---

← →
Правильный_Вася   (2008-06-02 13:52) [2]

типичная задача плотной упаковки
или "задача о рюкзаке"
гуглить

---

← →
ketmar ©   (2008-06-02 14:00) [3]

не надо. а надо читать про marching squares.

---
Understanding is not required. Only obedience.

---

← →
Тыщ ©   (2008-06-02 14:31) [4]

http://www.lomont.org/Software/
Тут есть, на C#. Rectangle Packing.

---

← →
DevilDevil ©   (2008-06-02 15:04) [5]

> Тыщ ©   (02.06.08 14:31) [4]
не скачивается.

не кинешь по почте, если есть.

---

← →
Рамиль ©   (2008-06-02 16:32) [6]

> Правильный_Вася   (02.06.08 13:52) [2]

А может раскроя?

---

← →
Alarm ©   (2008-06-02 16:45) [7]

Рамиль ©   (02.06.08 16:32) [6]
Именно раскроя листа (комнаты).
Канторович (линейное программирование)

---

← →
Правильный_Вася   (2008-06-02 17:09) [8]

> А может раскроя?

это одного класса задачи

---

← →
Ega23 ©   (2008-06-02 17:12) [9]

Одна из известных задач линейного программирования.
Алгоритм есть в любом учебнике (да и в сети навалом).

---

← →
DevilDevil ©   (2008-06-02 17:36) [10]

Не нахожу описание алгоритма.
В Rectangle Packing вроде то, но нет описания.

На всякий случай повторю условия. Есть комната определённого размера. Есть прямоугольники (которые нельзя поворачивать). Задача - максимально компактно расположить "прямоугольники" в "комнате".

---

← →
DevilDevil ©   (2008-06-02 18:04) [11]

похоже, то, что мне нужно:
http://www.gamedev.ru/users/coriolis/articles/Packing_Lightmaps

---

← →
Правильный_Вася   (2008-06-02 18:09) [12]

> максимально компактно расположить "прямоугольники" в "комнате".

тетрис?

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.47 MB
Время: 0.01 c