Autor Zpráva
JaySee
Profil
Dobrý den,

chci vytvořit obrázkovou koláž, kde budou zobrazeny obrázky s pevnou šířkou a různou výškou. Zároveň obrázky budou doléhat těsně na sebe a dohromady by měly tvořit přibližně obdélník +- pár pixelů.

Takže by to byly řekněme tři (ale taky třeba 4 nebo 2 nebo 10) sloupce naplněné obrázky různých výšek, kde všechny tři sloupce budou mít přibližně stejnou výšku.

A já potřebuji algoritmus, který načte rozměry (výšku) (je jedno jestli z XML, SQL, nebo jinak) cca 50 obrázků (+-5) a setřídí je tak, aby seděly ty celkové výšky ve sloupcích. Pořadí obrázků v sloupci není podstatné.

Stačí mi obecné algoritmy, nepotřebuji rovnou PHP script, to už si klidně napíši sám. Nebo alespoň nápady, jak na to.
Keeehi
Profil
To máte tak trochu problém. Pokud se nepletu, tak se jedná o NP-úplný problém, který se dá řešit pouze hrubou silou. Jde o Problém dvou loupežníků. Avšak vaše úloha má malé odlišnosti, což však nemění nic na složitosti úlohy. Počet loupežníků je roven počtu sloupců a nejde Vám o přesné rozdělení ale o nejlepší poměr.

Mám i nějaké materiály k tomuto ze školy, avšak vůbec nevím, zda je můžeme zveřejňovat.
JaySee
Profil
Keeehi:
I tak děkuji alespoň za inspiraci. A upřímně, myslel jsem si že je můj dotaz cosi lehkého :-D Na druhou stranu mě ale napadá pár postupů, které by se k tomu mohli alespoň přiblížit... Řekněme, že máme pole. To celé seřadíme a pak začneme rozdělovat do sloupců. Daly by se odfiltrovat velmi specifické rozměry, hlavně ty vysoké a s těmi začít. No a pak se snažit ta pole vždycky dorovnat. No a až to bude nějak u konce, tak ty položky ve sloupci zamíchat, aby to nebylo jak ty bílé pruhy před retardérem | | | | ||| ... bohužel, nejsem zrovna teoretik:-)

Ale jak jste napsal, nejde mi o přesné rozdělení (ale bylo by to fajn) ale o výslednou vizuální podobu (menší odchylky by se daly nahnat decentně odlišným marginem u jednotlivých sloupců)...

Co Vy na to? Připadne Vám to rozumné, nebo by se to dalo řešit efektivněji?
Keeehi
Profil
JaySee:
Napište mi. Email mám v profilu.
Alphard
Profil
Keeehi:
Co máš kde tajného? Zrovna tohle je zajímavé téma :-)
Alphard
Profil
JaySee:
Řekněme, že máme pole. To celé seřadíme a pak začneme rozdělovat do sloupců. Daly by se odfiltrovat velmi specifické rozměry, hlavně ty vysoké a s těmi začít.
Ano, přiblížit se půjde. V rychlosti jsem o tom přemýšlel a tohle je jedna z věcí, která mě napadla.
Tady je takový nástřel za 10 minut, teď mám na večer jiné plány, ale zajímá mě, co vymyslíte :-)

$size = array();
for ($i = 0; $i <= 50; $i++)
{
    $size[] = rand(50, 150);
}
//file_put_contents('data/size.txt', json_encode($size));


$colsCount = 4;
$cols = array();
//$size = json_decode(file_get_contents('data/size.txt'), true);

rsort($size);

$avg = array_sum($size)/$colsCount;
for ($i = 0; $i < $colsCount; $i++)
{
    $cols[] = array();
}

$img = 0;
$col = 0;
for ($j = 0; $j < 1e3; $j++) # $j je jen pojistka, mel by tam byt rizeny vystup
{
    if (array_sum($cols[$col%$colsCount])+$size[$img] < $avg )
    {
        $cols[$col%$colsCount][] = $size[$img];    
        unset($size[$img]);
        $img++;
        $col++;
    }
}

print_r($cols);
print_r($size);

echo "Prumer: $avg\n";
for ($i = 0; $i < $colsCount; $i++)
{
    echo "Sloupec $i: ".(array_sum($cols[$i]))."\n";
}

Výstup:
Array
(
[0] => Array
(
[0] => 150
[1] => 142
[2] => 135
[3] => 126
[4] => 121
[5] => 111
[6] => 99
[7] => 91
[8] => 80
[9] => 75
[10] => 71
[11] => 61
)

[1] => Array
(
[0] => 147
[1] => 139
[2] => 134
[3] => 124
[4] => 120
[5] => 110
[6] => 96
[7] => 89
[8] => 75
[9] => 73
[10] => 69
[11] => 60
)

[2] => Array
(
[0] => 146
[1] => 138
[2] => 128
[3] => 123
[4] => 118
[5] => 109
[6] => 95
[7] => 85
[8] => 75
[9] => 72
[10] => 66
[11] => 56
)

[3] => Array
(
[0] => 146
[1] => 136
[2] => 128
[3] => 123
[4] => 118
[5] => 101
[6] => 93
[7] => 85
[8] => 75
[9] => 71
[10] => 63
[11] => 56
)

)
Array
(
[48] => 55
[49] => 51
[50] => 50
)
Prumer: 1265
Sloupec 0: 1262
Sloupec 1: 1236
Sloupec 2: 1211
Sloupec 3: 1195


Ještě tam dost věcí chybí, ale mohla by to být cesta. Konečné rozdíly lze vyrovat třeba ořezáním obrázku, když v každém seberte nahoře a dole 5 pixelů, nebude to snad vadit.
Keeehi
Profil
Alphard:
Co máš kde tajného?
Jak jsem psal, nevím, zda to mohu veřejně šířit. Materiály jsou přístupné jen po přihlášení, takže kdyby měli být veřejně šiřitelné, asi by byly. Avšak zase nic tak světoborného to není. První příklad je základní řešení hrubou silou, druhý je rozšířen o nějaké optimalizace.

Algoritmus využívá rekurze. Vždy vezme první předmět z pole, a pro tři sloupce se 3x zavolá s polem kde je daný prvek odebraný a v součtu je přiřazen jednou každému sloupci. Až to dojede na konec pole. Složitost je v nejlepším případě O(N), v nejhorším O((počet sloupců)^N)

Toto jsou optimalizace
- Protože nezáleží na očíslování sloupců první předmět je přiřazen do sloupce 1 => výpočet se zkrátí na 1/(počet sloupců).
- Program se snaží předané předměty přiřazovat nejprve rovnoměrně, (první prvému, druhý druhému, třetí třetímu, čtvrtý opět prvému, ...) a teprve pokud to nevyjde, zkusí jiné přiřazení. Aby tento postup měl větší šanci na úspěch, předměty si funkce seřadí sestupně.

Pokud se budeme držet původního problému, tj. přesné rozdělení, pak se dají přidat ještě tyto podmínky:
- Pokud součet není dělitelný počtem sloupců nebo pokud cena nejdražšího předmětu je větší než (součet)/(počet sloupců), pak zadání nemá řešení
JaySee
Profil
Keeehi:
Už jsem Vás mailem kontaktoval a ještě mě napadla malá optimalizace.... nazval bych to Robin Hood :-D
1) setřídění od největšího po nejmenší
2) každému sloupci se přiřadí jeden z nejvyšších obrázků
3) pak cyklus, který dává další zbývající největší obrázek sloupci, který je nejchudší (má nejmenší součet výšek)

4) když by byly rozdíly pořád veliké, tak se podívá do databáze na další obrázek adekvátní velikosti na doplnění :-D
5) ale pořád je to blbé řešení
JaySee
Profil
Tak jsem z toho jelen... upřímně jsem pohořel na své neschopnosti si v poli předávat identifikátor :-(

protože já nejen že potřebuji optimálně roztřídit výšky, já i potřebuji přenést nějaké id s těmi výškami. Totálně se ztrácím ve vlastním, byť konmentovaném kódu. A ještě jeden problém, když použiju rsort() tak se mi změní klíče a opět jsem u svého problému číslo 1, neumím předávat idečka v poli.
Keeehi
Profil
JaySee:
K výšce nepotřebujete mít přiřazené id, to jde dohledat zpětně. Ale pokud byste na tom trval, tak použijte dvourozměrné pole
Alphard
Profil
Trochu jsem si s tím hrál a zdá se, že obrázky není problém o nějaké to procento roztáhnout nebo zmáčkou, takže není ani potřeba moc složitý algoritmus. Pokud není extrémní situace, aby vycházely dva obrázky pod sebe, vyjde to pěkně. Vylepšil jsem (prakticky přepsal, jen jsem zachoval myšlenku nejdříve zařadit vysoké obrázky) [#6] a dostal se k výsledku.
Jestli zveřejním kódy, případně v jakém rozsahu, se rozhodnu zítra.
JaySee
Profil
Alphard:
Tak to je AWESOME!!!!!! přesně tohle jsem chtěl a vypadá to, pane, opravdu dobře! Klobouk dolů. Je možno sdílet strojopis prosím?
Keehel:
No ono to pole v Alphardově ukázce pro náhodné hodnoty bylo jednorozměrné (ale i to má klíče) a přidal jsem mu další rozměr a do něj přidal klíče. Už tady v té fázi pochybuji o "elegratnosti" řešení. Pak jsem se je snažil různě předávat a nakonec se mi to vždycky nějak pokazilo, když jsem používal funkce jako rsort(kdy mi to sice seřadil, ale už uplně pomateně).

Takže jsem myslím objevil zadání svého domácího úkolu na příští měsíc :-D
Alphard
Profil
JaySee:
Já nevím, jestli to sem jen tak dávat, je to váš úkol :-) možná mě ukecáte za pár dní, ale teď to ještě zkuste trochu sám.
Funkce rsort() byla v první nástřelu, když jsem dal jako klíče jména souborů, musel jsem to změnit na arsort() (v manuálu se podívejte na See also, tj. další řadící funkce). Tím jsem ale ztratil číselné a setřízené indexy, takže jsem část cyklů musel přepsat přes foreach a trochu upravit některé struktury.
Soubor, který to roztřídí do sloupců, má asi 50 řádků a to roztažení/stlačení není ani na 30 řádků. Je to na chvilku.
JaySee
Profil
Alphard:
Já nevím, jestli to sem jen tak dávat, je to váš úkol :-)
Váš přístup se mi líbí!

Tak dobře, zkusím se podvat na ten arsort() a vzít to přes foreach... večer se ozvu, jestli se zadařilo :-D Nikdy jsem tohle nepotřeboval dělat, takže to neumím a nebude to na chvilku:-D
Alphard
Profil
JaySee se už neozval, ale jiné vlákno mi tohle připomnělo. Udělal jsem to přibližně takhle:
index.php
$colsCount = 6; #počet sloupců
$imgWidth = 300; # šířka sloupce (obrázky se zmenší nebo roztáhnout)

include "calcImageSize.php"; # funkce od Jakuba Vrány http://php.vrana.cz/zmensovani-obrazku.php
include "loadImages.php"; # načte obrázky z adresáře a vytvoří asociativní pole file => height
include "sortInCols.php"; # roztřídí obrázky do sloupců
include "extend.php"; # roztáhne nebo stlačí obrázky na průměrnou délku sloupce
include "generateCollage.php"; # vygeneruje výsledný obrázek

sortInCols.php
<?php

$imgCount = count($images);
$cols = array();

arsort($images);

$avg = array_sum($images)/$colsCount;
for ($i = 0; $i < $colsCount; $i++)
{
    $cols[] = array();
}

$img = 0;
$col = 0;

foreach ($images as $file => $s) 
{
    if (array_sum($cols[$col%$colsCount])+$s < $avg )
    {
        $cols[$col%$colsCount][$file] = $s;    
        unset($images[$file]);
        $col++;
    }
    else
    {
        for ($c = 0; $c < $colsCount; $c++)
        {
            $col++;
            if (array_sum($cols[$col%$colsCount])+$s < $avg )
            {
                $cols[$col%$colsCount][$file] = $s;    
                unset($images[$file]);
                continue 2;
            }
        }
    }
}

foreach ($images as $file => $s)
{
    $n = 0;
    for ($i = 0; $i < $colsCount; $i++)
    {
        if (array_sum($cols[$i]) < array_sum($cols[$n]))
        {
            $n = $i;
        }        
    }
    $cols[$n][$file] = $s;
    unset($images[$file]);
}

Možná to šlo líp, současný stav je spíš důsledek živelného vývoje, který se po dosažení cíle dále neupravoval. Kdybyste někdo stál o kompletní scripty, tak napište.
JaySee
Profil
Alphard:
Jsem na příjmu:-D Ale ještě jsem si s tím neporadil (věnoval jsem se jiným věcem). Zapracuju na tom, tentokrát nebudu slibovat do kdy:-D

Vaše odpověď

Mohlo by se hodit

Odkud se sem odkazuje


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm: