Lap képekkel való lefedése

Algoritmusok

Sziasztok!

Egy algoritmust kellene találnom a következő problémára:

Adva van egy lap (szélesség, magasság) és n db kép ( kép azonosító, max. szélesség, max. magasság).
Az algoritmusnak a képeket kellene a lapra helyeznie úgy, hogy a lapot optimálisan töltsék ki a képek.
A képeknél a maximum szélesség és magasság van megadva ( ez az a méret ami felett már pixelesedik megjelenítés ), aminél lehetnek kisebbek de a képek szélesség/magasság aránya nem változhat.
Meg van meg adva a képek minimum szélessége ami egy konstans( álló képnél a magasság ).
Az mar csak hab a tortán, hogy van egy konstans távolság megadva a képek között (margo1) és a képek és a lap széle között (margo2).

Az algoritmus kimenetének az n db kép x, y koordinátájának és szélesség, magasságnak kellene lenni.

Még annál a fázisnál tartok, hogy milyen fajta algoritmus jöhetne szóba a problémára.
Tudom, hogy vannak matematikai algoritmusok egy téglalap felosztására például.
Mivel a képek mérete nem előre meghatározott, azon gondolkodtam, hogy ez már nem-e a mesterséges intelligenciával jobban megoldható kategória inkább.
Nem szeretném újra feltalálni a kereket, ezért kérdezlek benneteket, hogy ismer-e valaki erre a problémára illő vagy hasonló létező algoritmust.

Előre is köszi a segítséget!

  • 4455 megtekintés

( mulder | 2010. 11. 10., sze – 10:51 )

Genetikus algritmus OpenCL alapon ... would be nice :)

( Nyosigomboc v | 2010. 11. 10., sze – 11:45 )

Ez nagyon nincs definialva.

Mi szamit optimalisnak? Ha tfh. van 25 negyzetes keped azonos parameterekkel, akkor az a jobb, ha 5x5 negyzetbol all, vagy az, amikor van egy bazinagy (teljesitve a max. meret feltetelt), es a tobbi meg a szeleinel helyezkedik el? Legyen minel kisebb a felesleg? Legyenek minel nagyobbak a kepek? Csak 1 lap van, vagy lehet tobb is?

A kepek orientacioja szamit? Mert egy allo kepet ha elfektetve jobban el tudsz helyezni, az is jo lehet, ha a vegen egyenkent kivagod mindet.

Egyebkent nagyon NP-belinek tunik a feladat, nagyszamu kepre max. heurisztikakkal tudsz kozel optimalis megoldast talalni.

Ha az aspect ratio fix, akkor mindegy, hogy a szelessegre vagy a magassagra adsz meg minimalis meretet, mindkettore megadtad ezzel.

Margo1-et (a fix. asp. rat.-bol szarmazo nagyitastol eltekintve) kezelheted ugy, mint ha margo1*0.5-vel none a kep merete, margo2-t meg hogy margo2-margo1*0.5-tel kisebb a lapod. De ez mar reszletkerdes.

Ja, a margo gondolom lehet nagyobb nehany helyen, csak kisebb nem, ugye?

--
The iPad: Because the iPhone was too small for other people to notice you.

( strangelove | 2010. 11. 10., sze – 12:47 )

2dimenziós bin packing egy 2d-s ládába, vagy 2d knapsack speciális súlyokkal. A két probléma valamilyen értelemben ekvivalens (de ugyanolyan nehezek), és a célfüggvénytől függ, ami nem világos a mondandódból.

Mint eldöntési probléma, NP-teljes, amúgy NP-nehéz. Approximációs algoritmus van rá, szerény emlékeim szerint.

szerk.: 1 fillérért van rá sansz, hogy segítek, ha nem iskolá(ba való )példa!

http://www.youtube.com/watch?v=QXz7-BNC6jw
http://nocirc.org/

( PajzsMan | 2010. 11. 10., sze – 14:17 )

Köszi szépen az ötleteket! Utánanézek ezeknek.

Optimálison azt értettem, hogy minnél jobban le kell fedni a rendelkezésre álló felületet, de egyben jól is kell kinéznie, tehát minden képnek minnél nagyobbnak kellene lennie.
Képek orientációját es aspect rációját meg kell tartani.
Szóval a kérdésedre válaszolva 25 db azonos paraméterű képnek 5x5 ,azonos méretben kellene elhelyezkedni.
Most egy lapról beszelünk, ha túl sok kép lenne, akkor arra egyéb marketinges szabályrendszer van, hogy hány lapot használjunk.
Egyébként ez nem iskolai feladat, de a projectet nem én kaptam.
Engem csak érdekel a téma és ha a kollégáim netán elakadnának vagy végül valami nem elfogadhatót találnának ki akkor ki kell húzni a csapatot a bajból.
A megoldásnak nyelvfüggetlennek kell lennie, mert mind a kliensen mind a szerveren implementálva lesz különfajta nyelveken( javascript, java, actionscript ).