[PHP / MySQL] Een vlak opvullen met images uit database

[Verwijderd]

Ik ben met een website bezig waarin ik het volgende wil bereiken:
Een vlak (kollom) zoveel mogelijk "opvullen" met plaatjes van verschillende maten.

De plaatjes sla ik gewoon op in het FS, daarbij houd ik wel info bij over het plaatje (breedte, hoogte) met een uniek id'tje waaronder ik het plaatje ook zelf ook op sla.

Nou wil ik deze plaatjes uitlezen en daarbij kijken hoe ik een vlak zo mooi mogelijk kan opvullen. zodat er zo min mogelijk lege ruimtes in het vlak zitten.

Maar ik heb geen idee hoe ik dit zou moeten aanpakken, daarom hoop ik dat 1 van jullie hier misschien ervaring in heeft of dat mensen een suggestie kunnen doen.

[NMe]

Wat lukt je dan precies niet? Waar gaat het mis? Wat heb je zelf al geprobeerd? Lees ook P&W FAQ - De "quickstart" even door. Zoals je topic er nu staat kunnen we het alleen als scriptrequest opvatten, en die staan we hier in Programming & Webscripting niet toe. Probeer dus wat uitgebreider aan te geven waar het misgaat.

[Noork]

Er zijn tig scriptjes waarmee je images kan resizen met php en gdlib. Zoals deze: http://smiledsoft.com/dem...thescript/demo/index.html

[Janoz]

Het vullen van een rechthoek met een deel verzameling kleinere rechthoeken waarbij het grote rechthoek volledig wordt gevuld is een zogenaamd NP Compleet probleem. Hiervoor bestaat dus geen andere oplossing dan domweg maar wat proberen en hopen dat je uitkomt.

[ekoopman]

Je zou gaan kunnen Monte Carlo'en. (google even als dit je niks zegt). Start met een lege doos, pak at random een plaatje en gooi hem ergens erin.
Definieer dan een functie U die oneindig is als er iets uitsteekt of overlapt en anders de waarde heeft van het aantal nog lege vakjes. Je wilt dan dus U minimaliseren.
Doe dan in iteraties het volgende:
of je haalt een vlakje weg, of je voegt er at random een toe. Dan met een kans die gelijk is aan min(1,exp(U_oud/U_nieuw)) accepteer je deze nieuwe configuratie. Ondertussen houd je netjes bij welke configuratie het kleinste aantal lege vakjes had.

De precieze details kunnen niet helemaal kloppen, maar dit is een aanpak die redelijk zou moeten werken

[Verwijderd]

offtopic: hehe wel tof, soort ai schrijven om een vlak op te vullen met plaatjes, maar dat wordt wel een beetje heftige serverload denk ik, het komt er toch op neer dat je alle combinaties probeert dan? als je dan 100 plaatjes hebt, en er passen er 25 in ofzo, dan gaat dat erg hard lijkt me....

zou je niet beter zoals iemand anders al zei, gewoon het vlak eerst ruw volgooien met random plaatjes, tot nergens meer een plaatje past, en random plaatjes in de lege plekken gaan resizen, lijkt mij wel vet iig. Zou ff moeten bedeken hoe je dit aan moet pakken, maar is wel mogelijk denk ik

[Verwijderd]

Ik ben al van het idee af om ALLES op te vullen maar dan zou ik minstens de breedte "zoveel" mogelijk willen opvullen.

Ik ben niet op zoek naar scripts die resizen, en alle aanwezige logo's moeten in het vlak komen dus dan zou hij naar beneden moeten oprekken (wat natuurlijk geen probleem is, meer een voordeel)

ik weet dat het iets in de trend moet zijn van de volgende stappen:
- alle plaatjes in een array laden vanuit de database
- kijken hoeveel ruimte er in de breedte over is, en op zoek gaan naar een plaatje die daar het beste in past
- die entry verwijderen uit array
- en dan weer opnieuw

Maar ik kom er niet uit hoe ik dat exact zou moeten aanpakken.

hopelijk zo duidelijker

[Verwijderd]

Verwijderd schreef op dinsdag 31 januari 2006 @ 18:39:
Ik ben al van het idee af om ALLES op te vullen maar dan zou ik minstens de breedte "zoveel" mogelijk willen opvullen.

Ik ben niet op zoek naar scripts die resizen, en alle aanwezige logo's moeten in het vlak komen dus dan zou hij naar beneden moeten oprekken (wat natuurlijk geen probleem is, meer een voordeel)

ik weet dat het iets in de trend moet zijn van de volgende stappen:
- alle plaatjes in een array laden vanuit de database
- kijken hoeveel ruimte er in de breedte over is, en op zoek gaan naar een plaatje die daar het beste in past
- die entry verwijderen uit array
- en dan weer opnieuw

Maar ik kom er niet uit hoe ik dat exact zou moeten aanpakken.

hopelijk zo duidelijker

Om hoeveel plaatjes gaat het?
10?
100?
1000+?

[Verwijderd]

het gaat om een aantal rubrieken (denk aan zo'n 30) en in zo'n rubriek komen tientallen plaatjes (variabel)

[Verwijderd]

Verwijderd schreef op dinsdag 31 januari 2006 @ 18:39:
Ik ben al van het idee af om ALLES op te vullen maar dan zou ik minstens de breedte "zoveel" mogelijk willen opvullen.

Als je alleen naar de breedte kijkt, kun je het in O(nB) deterministisch doen, waarbij n het aantal plaatjes is en B de totale breedte van je vlak (in pixels) met een dynamisch programmeeralgoritme, gebaseerd op de volgende recurrente betrekking:

Stel in array s[i] is voor iedere afbeelding i de breedte opgeslagen.

Definieer een kostenfunctie W:
W(i, x) = minimum aantal pixels dat wordt overgehouden wanneer een vlak van breedte x moet worden opgevuld, waarbij de eerste i afbeeldingen mogen worden gebruikt.

Dan krijg je:
W(0, x) = x
(als je 0 plaatjes mag gebruiken kun je niets opvullen, en houdt je dus x pixels ongebruikt over)

W(i, x) = min( W(i-1, x) , W(i-1, x-s[i]) )
onder voorwaarde dat x >= s[i] (de minimum kosten voor het opvullen van een vlak van x pixels met gebruikmaking van de eerste i afbeeldingen is het minimum van [W(i-1, x) oftewel de minimum kosten als je het plaatje niet gebruikt] en [W(i-1, x-s[i]) oftewel de minimum kosten als je plaatje i wel gebruikt en dus nog een vlak van x-s[i] pixels overhoudt om op te vullen met de eerste i-1 plaatjes).

Als je deze recurrente betrekking in een DP-algoritme uitklopt heb je dit beslisprobleem vrij snel opgelost; je weet dan de waarde van W(n, B ) wat je dus vertelt wat het aantal pixels is dat je zelfs in het optimale geval niet kan vullen met je plaatjes; met een beetje geluk is dit in de buurt van 0. Om nu de oplossing zelf te vinden moet je in een extra array bijhouden welke keuzes gemaakt worden in de min-check; de keuze om plaatje i wel of niet te gebruiken.

[Verwijderd]

PHP:

<?php
function doIt($blockWidth, $Images) {
    $ietsGedaan = TRUE;
    while($ietsGedaan == TRUE) {
        //echo '<pre>';
        //print_r($Images);
        //echo '</pre>';
        $ruimteOver = $blockWidth;
        $ietsGedaan = FALSE;
        $oudeHoogte = 0;
        foreach ( $Images AS $key => $value ) {
            if($ruimteOver >= $Images[$key]['width'] AND $Images[$key]['state'] == TRUE) {
                if($Images[$key]['height'] < $oudeHoogte AND $oudeHoogte != 0) {
                    $hoogteOver = $oudeHoogte - $Images[$key]['height'];
                    $breedteOver = $Images[$key]['width'];
                    echo '<div style="height: '.$oudeHoogte.'px; width: '.$breedteOver.'px; float: left; border: 0px solid purple;">';
                        $ruimteOver = $ruimteOver - $Images[$key]['width'];
                        $Images[$key]['state'] = FALSE;
                        $ietsGedaan = TRUE;
                        echo '[img]"'.$putUrl.''.$key.'.jpg"[/img]';
                        doIt2($breedteOver,$hoogteOver,$Images);
                    echo '</div>';
                } else {
                    echo '[img]"'.$putUrl.''.$key.'.jpg"[/img]';
                    $ruimteOver = $ruimteOver - $Images[$key]['width'];
                    $Images[$key]['state'] = FALSE;
                    $ietsGedaan = TRUE;                 
                }
                
                $oudeHoogte = $Images[$key]['height'];
            }
        }
        if($ietsGedaan == TRUE)
            echo '<div style="clear: both;"></div>';
    }   
}
function doIt2($blockWidth, $blockHeight, $Images) {
    echo '<div style="width: '.$blockWidth.'px; height: '.$blockHeight.'px; float: left;">';
    $ruimteOver = $blockWidth;
    
    foreach ( $Images AS $key => $value ) {
        
        if($ruimteOver >= $Images[$key]['width'] AND $Images[$key]['height'] <= $blockHeight AND$Images[$key]['state'] == TRUE) {
            echo '[img]"'.$putUrl.''.$key.'.jpg"[/img]';
            $ruimteOver = $ruimteOver - $Images[$key]['width'];
            $Images[$key]['state'] = FALSE;
        }
    }
    echo '</div>';
}

$itemRes = mysql_query("SELECT * FROM titem ORDER BY itheight * itwidth DESC");
while($itemObj = mysql_fetch_object($itemRes)) {
    $Images[$itemObj->itid]['width'] = $itemObj->itwidth;
    $Images[$itemObj->itid]['height'] = $itemObj->itheight;
    $Images[$itemObj->itid]['state'] = TRUE;
}

echo '
<html>
    <head>
        <style>
        div {
            border: 0px solid blue; 
        }
        img {
            border: 0;
            float: left;
        }
        </style>
    </head>
<body>
<div style="width: 200px; border: 1px solid blue;">
';
doIt(200, $Images);
echo '
</div>
</body>
</html>
';
?>

Dat werkt op zich vrij aardig en krijg ik "wat ik wil". In firefox laat hij het sowieso goed zien, in IE nog wat problemen, maar daar is wel uit te komen.

Ik ben niet zo'n held in inschatten of iets een "zware" bewerking is, hebben jullie misschien nog suggesties en / of verbeteringen op het te optimaliseren?