Cześć!
Szukam algorytmu na optymalne wypełnienie prostokątnego pola o danych
wymiarach (np. kartki A4) , poprzez inne prostokąty (mają one swoje
wymiary początkowe, które można skalować zachowując proporcje).
Szukałem, szukałem i marnie mi to idzie...
Może ktoś z was podpowie mi pod jaką nazwą tego szukać - próbowałem
problem pakowania plecaka, jednak to nie jest to o co mi chodzi...

Pozdrawiam,
Krzysiek

do góry

On 21.08.2009, krzys wrote:
> Cześć!
> Szukam algorytmu na optymalne wypełnienie prostokątnego pola o danych
> wymiarach (np. kartki A4) , poprzez inne prostokąty (mają one swoje
> wymiary początkowe, które można skalować zachowując proporcje).
> Szukałem, szukałem i marnie mi to idzie...
> Może ktoś z was podpowie mi pod jaką nazwą tego szukać - próbowałem
> problem pakowania plecaka, jednak to nie jest to o co mi chodzi...

Problem plecakowy bylby szczegolnym przypadkiem twojego problemu, jesli
pozbyc sie mozliwosci skalowania innych prostokatow, mianowicie gdy
prostokat do wypelnienia ma wymiary N x M, N < M, a wszystkie prostokaty
wypelniajace maja wymiary N x K, gdzie znowu N < K dla kazdego K.
(N jest tu mniejsze po to, zeby prostokaty mozna bylo polozyc tylko
w jednym kierunku).

--
Stanislaw Klekot

do góry

On Fri, 21 Aug 2009 04:25:04 -0700 (PDT), krzys <d...@g...com>
wrote:

>Cześć!
>Szukam algorytmu na optymalne wypełnienie prostokątnego pola o danych
>wymiarach (np. kartki A4) , poprzez inne prostokąty (mają one swoje
>wymiary początkowe, które można skalować zachowując proporcje).
>Szukałem, szukałem i marnie mi to idzie...
>Może ktoś z was podpowie mi pod jaką nazwą tego szukać - próbowałem
>problem pakowania plecaka, jednak to nie jest to o co mi chodzi...
>
>Pozdrawiam,
>Krzysiek

2D bin packing, rectangle packing, box packing

A.L.

do góry

On Fri, 21 Aug 2009 11:50:32 +0000 (UTC), "Stachu 'Dozzie' K."
<d...@d...im.pwr.wroc.pl.nospam> wrote:

>On 21.08.2009, krzys wrote:
>> Cześć!
>> Szukam algorytmu na optymalne wypełnienie prostokątnego pola o danych
>> wymiarach (np. kartki A4) , poprzez inne prostokąty (mają one swoje
>> wymiary początkowe, które można skalować zachowując proporcje).
>> Szukałem, szukałem i marnie mi to idzie...
>> Może ktoś z was podpowie mi pod jaką nazwą tego szukać - próbowałem
>> problem pakowania plecaka, jednak to nie jest to o co mi chodzi...
>
>Problem plecakowy bylby szczegolnym przypadkiem twojego problemu, jesli
>pozbyc sie mozliwosci skalowania innych prostokatow, mianowicie gdy
>prostokat do wypelnienia ma wymiary N x M, N < M, a wszystkie prostokaty
>wypelniajace maja wymiary N x K, gdzie znowu N < K dla kazdego K.
>(N jest tu mniejsze po to, zeby prostokaty mozna bylo polozyc tylko
>w jednym kierunku).

Naprawde?...

A.L.

do góry

On 21.08.2009, A.L wrote:
> On Fri, 21 Aug 2009 11:50:32 +0000 (UTC), "Stachu 'Dozzie' K."
><d...@d...im.pwr.wroc.pl.nospam> wrote:
>
>>On 21.08.2009, krzys wrote:
>>> Cześć!
>>> Szukam algorytmu na optymalne wypełnienie prostokątnego pola o danych
>>> wymiarach (np. kartki A4) , poprzez inne prostokąty (mają one swoje
>>> wymiary początkowe, które można skalować zachowując proporcje).
>>> Szukałem, szukałem i marnie mi to idzie...
>>> Może ktoś z was podpowie mi pod jaką nazwą tego szukać - próbowałem
>>> problem pakowania plecaka, jednak to nie jest to o co mi chodzi...
>>
>>Problem plecakowy bylby szczegolnym przypadkiem twojego problemu, jesli
>>pozbyc sie mozliwosci skalowania innych prostokatow, mianowicie gdy
>>prostokat do wypelnienia ma wymiary N x M, N < M, a wszystkie prostokaty
>>wypelniajace maja wymiary N x K, gdzie znowu N < K dla kazdego K.
>>(N jest tu mniejsze po to, zeby prostokaty mozna bylo polozyc tylko
>>w jednym kierunku).
>
> Naprawde?...

Nie, tak tylko zarty sobie z grupy stroje.

--
Stanislaw Klekot

do góry

Dzięki za odpowiedź.
Z tym skalowaniem sprawa wygląda tak, że jedne z prostokątów można
powiększyć, a inne pomniejszyć, tak aby jak najszczelniej wypełniły
powierzchnię (jednak nie mogę zmieniać ich ilości - tzn. jak mam 3
prostokąty, to muszą być 3, ich wymiary mogą się zmienić tak, aby
optymalnie pokryły całą powierzchnię, ale z zachowaniem ich proporcji)

do góry

"krzys" <d...@g...com> wrote in message
news:43c4dcf4-2640-4a20-a907-436720af94af@b15g2000yq
d.googlegroups.com...
> Cześć!
> Szukam algorytmu na optymalne wypełnienie prostokątnego pola o danych
> wymiarach (np. kartki A4) , poprzez inne prostokąty (mają one swoje
> wymiary początkowe, które można skalować zachowując proporcje).
> Szukałem, szukałem i marnie mi to idzie...


Powinno się udać
http://www-rcf.usc.edu/~skoenig/icaps/icaps04/icapsp
apers/ICAPS04KorfR.pdf

Pozdrawiam
--
Mateusz Loskot, http://mateusz.loskot.net
pl.comp.lang.c FAQ: http://pl.cpp.wikia.com/wiki/FAQ
C++ FAQ: http://parashift.com/c++-faq-lite

do góry

"Mateusz Loskot" beee:
> "krzys" <d...@g...com> wrote in message
> news:43c4dcf4-2640-4a20-a907-436720af94af@b15g2000yq
d.googlegroups.com...
>> Cześć!
>> Szukam algorytmu na optymalne wypełnienie prostokątnego pola o danych
>> wymiarach (np. kartki A4) , poprzez inne prostokąty (mają one swoje
>> wymiary początkowe, które można skalować zachowując proporcje).
>> Szukałem, szukałem i marnie mi to idzie...
> Powinno się udać
> http://www-rcf.usc.edu/~skoenig/icaps/icaps04/icapsp
apers/ICAPS04KorfR.pdf
ale się człowiek opisał... ;-> metoda szatkowania kwadratami, ponieważ
upycha kwadraty/prostokąty, czyli figury szatkowalne na kwadraty.
wystarczyło napisać, że problem upchnięcia jest tak rozwiązywalny, jak
rozwiązywalne jest znalezienie figury będącej wspólnym dzielnikiem wszy-
stkich upychanych figur (tak samo jak znalezienie liczb dzielników
w przestrzeni jednowymiarowej).
...
każdy musi zdobyć dyplom... ;->
--
beeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee

do góry

On Fri, 21 Aug 2009 18:39:52 +0000 (UTC), "P. Owca"
<2...@i...sk> wrote:

>?Mateusz Loskot" beee:
>> "krzys" <d...@g...com> wrote in message
>> news:43c4dcf4-2640-4a20-a907-436720af94af@b15g2000yq
d.googlegroups.com...
>>> Cześć!
>>> Szukam algorytmu na optymalne wypełnienie prostokątnego pola o danych
>>> wymiarach (np. kartki A4) , poprzez inne prostokąty (mają one swoje
>>> wymiary początkowe, które można skalować zachowując proporcje).
>>> Szukałem, szukałem i marnie mi to idzie...
>> Powinno się udać
>> http://www-rcf.usc.edu/~skoenig/icaps/icaps04/icapsp
apers/ICAPS04KorfR.pdf
>ale się człowiek opisał...?;->?metoda szatkowania kwadratami, ponieważ
>upycha kwadraty/prostokąty, czyli figury szatkowalne?na kwadraty.
>wystarczyło napisać, że problem upchnięcia jest tak rozwiązywalny, jak
>rozwiązywalne

Problem pakowania jest NP-hard, wiec Kolega jest uprzejmy bredzic...

beeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee

A.L.

do góry

On 21 Sie, 14:53, krzys <d...@g...com> wrote:
> Dzięki za odpowiedź.
> Z tym skalowaniem sprawa wygląda tak, że jedne z prostokątów można
> powiększyć, a inne pomniejszyć, tak aby jak najszczelniej wypełniły
> powierzchnię (jednak nie mogę zmieniać ich ilości - tzn. jak mam 3
> prostokąty, to muszą być 3, ich wymiary mogą się zmienić tak, aby
> optymalnie pokryły całą powierzchnię, ale z zachowaniem ich proporcji)

Optymalne wypełnienie oznacza, że pozostaje jak najmniejsze pole
powierzchni niewykorzystane ?

Ta optymalność przypomina trochę problem komiwojażera i może być
znaleziona na przykład algorytmem genetycznym. Duża szansa, że utkwisz
w jakimś minimum lokalnym, które będzie satysfakcjonujące, ale nie
będzie to rozwiązanie analitycznie najlepsze.

Zakładając, że będzie niewiele figur jednak, da się przeszukać
wszystkie możliwości, jeśli nie byłoby skalowania. Skalowanie dość
mocno komplikuje problem, bo rozciąga z dyskretnej przestrzeni , na
ciągłą.

do góry