C# algorithm conundrum - bin packing

Question

I am trying to make a FNF algorithm for 2d bin packing, and when I call the method I get the wrong results. Please help, I can't find the problem.

private void FFF()
{
    int xmax = 0;
    int movex = 0;
    int movey = 0;
    int maxH = RectBin.Height;
    int maxW = RectBin.Width;
    List<Rectangle> rectsToDraw = new List<Rectangle>();
    for (int i = 0; i < Shapes.Count; i++)
    {
        int height = Shapes[i].Height;
        int width = Shapes[i].Width;
        if ((movey + height) <= maxH)
        {
            rectsToDraw.Add(new Rectangle(movex, movey, width, height));
            movey = movey + height;
            if (xmax < movex + width)
            {
                xmax = movex + width;
            }
        }
        else if ((xmax + width) <= maxW)
        {
            movex = xmax;
            rectsToDraw.Add(new Rectangle(movex, 0, width, height));
            movey = height;
            xmax = movex + width;
        }
        else
        {
            Debug.Write("Message1");
            break;
        }
    }

    for (int j = 0; j < rectsToDraw.Count; j++)
    {
        Debug.Write(rectsToDraw[0]);
    }
    r2d = rectsToDraw;
}

rectBin is a public rectangle (0,0, 300, 190), and Shapes[] is a public rectangle list. I sort Shapes before using it here by:

private void button9_Click(object sender, EventArgs e)
{
    Shapes.Sort((x,y) => ((y.Width.CompareTo(x.Width))));
}

When I start FNF in the debug console I get repeating list items and message1 (first one in shapes, which shouldn't repeat), when i should get 14 items.

Just to be clear, I am not looking for an algorithm, just someone to tell me where I made a mistake so that the first item in oblici gets coppyed 4 times into rectsToDraw and the loop ends...

Input: {X=0,Y=0,Width=231,Height=66}{X=0,Y=0,Width=167,Height=61}{X=0,Y=0,Width=151,Height=47}{X=0,Y=0,Width=130,Height=40}{X=0,Y=0,Width=119,Height=39}{X=0,Y=0,Width=115,Height=52}{X=0,Y=0,Width=72,Height=53}{X=0,Y=0,Width=58,Height=46}{X=0,Y=0,Width=47,Height=32}{X=0,Y=0,Width=41,Height=47}{X=0,Y=0,Width=38,Height=47}{X=0,Y=0,Width=33,Height=45}{X=0,Y=0,Width=22,Height=39}{X=0,Y=0,Width=0,Height=0}

Output: {X=0,Y=0,Width=231,Height=66}{X=0,Y=0,Width=231,Height=66}{X=0,Y=0,Width=167,Height=61}{X=0,Y=0,Width=231,Height=66}{X=0,Y=0,Width=167,Height=61}{X=0,Y=0,Width=151,Height=47}{X=0,Y=0,Width=231,Height=66}{X=0,Y=0,Width=167,Height=61}{X=0,Y=0,Width=151,Height=47}{X=0,Y=0,Width=130,Height=40}{X=0,Y=0,Width=231,Height=66}{X=0,Y=0,Width=167,Height=61}{X=0,Y=0,Width=151,Height=47}{X=0,Y=0,Width=130,Height=40}{X=0,Y=0,Width=119,Height=39}{X=0,Y=0,Width=231,Height=66}{X=0,Y=0,Width=167,Height=61}{X=0,Y=0,Width=151,Height=47}{X=0,Y=0,Width=130,Height=40}{X=0,Y=0,Width=119,Height=39}{X=0,Y=0,Width=115,Height=52}{X=0,Y=0,Width=231,Height=66}{X=0,Y=0,Width=167,Height=61}{X=0,Y=0,Width=151,Height=47}{X=0,Y=0,Width=130,Height=40}{X=0,Y=0,Width=119,Height=39}{X=0,Y=0,Width=115,Height=52}{X=0,Y=0,Width=72,Height=53}{X=0,Y=0,Width=231,Height=66}{X=0,Y=0,Width=167,Height=61}{X=0,Y=0,Width=151,Height=47}{X=0,Y=0,Width=130,Height=40}{X=0,Y=0,Width=119,Height=39}{X=0,Y=0,Width=115,Height=52}{X=0,Y=0,Width=72,Height=53}{X=0,Y=0,Width=58,Height=46}{X=0,Y=0,Width=231,Height=66}{X=0,Y=0,Width=167,Height=61}{X=0,Y=0,Width=151,Height=47}{X=0,Y=0,Width=130,Height=40}{X=0,Y=0,Width=119,Height=39}{X=0,Y=0,Width=115,Height=52}{X=0,Y=0,Width=72,Height=53}{X=0,Y=0,Width=58,Height=46}{X=0,Y=0,Width=47,Height=32}{X=0,Y=0,Width=231,Height=66}{X=0,Y=0,Width=167,Height=61}{X=0,Y=0,Width=151,Height=47}{X=0,Y=0,Width=130,Height=40}{X=0,Y=0,Width=119,Height=39}{X=0,Y=0,Width=115,Height=52}{X=0,Y=0,Width=72,Height=53}{X=0,Y=0,Width=58,Height=46}{X=0,Y=0,Width=47,Height=32}{X=0,Y=0,Width=41,Height=47}{X=0,Y=0,Width=231,Height=66}{X=0,Y=0,Width=167,Height=61}{X=0,Y=0,Width=151,Height=47}{X=0,Y=0,Width=130,Height=40}{X=0,Y=0,Width=119,Height=39}{X=0,Y=0,Width=115,Height=52}{X=0,Y=0,Width=72,Height=53}{X=0,Y=0,Width=58,Height=46}{X=0,Y=0,Width=47,Height=32}{X=0,Y=0,Width=41,Height=47}{X=0,Y=0,Width=38,Height=47}{X=0,Y=0,Width=231,Height=66}{X=0,Y=0,Width=167,Height=61}{X=0,Y=0,Width=151,Height=47}{X=0,Y=0,Width=130,Height=40}{X=0,Y=0,Width=119,Height=39}{X=0,Y=0,Width=115,Height=52}{X=0,Y=0,Width=72,Height=53}{X=0,Y=0,Width=58,Height=46}{X=0,Y=0,Width=47,Height=32}{X=0,Y=0,Width=41,Height=47}{X=0,Y=0,Width=38,Height=47}{X=0,Y=0,Width=33,Height=45}{X=0,Y=0,Width=231,Height=66}{X=0,Y=0,Width=167,Height=61}{X=0,Y=0,Width=151,Height=47}{X=0,Y=0,Width=130,Height=40}{X=0,Y=0,Width=119,Height=39}{X=0,Y=0,Width=115,Height=52}{X=0,Y=0,Width=72,Height=53}{X=0,Y=0,Width=58,Height=46}{X=0,Y=0,Width=47,Height=32}{X=0,Y=0,Width=41,Height=47}{X=0,Y=0,Width=38,Height=47}{X=0,Y=0,Width=33,Height=45}{X=0,Y=0,Width=22,Height=39}{X=0,Y=0,Width=231,Height=66}{X=0,Y=0,Width=167,Height=61}{X=0,Y=0,Width=151,Height=47}{X=0,Y=0,Width=130,Height=40}{X=0,Y=0,Width=119,Height=39}{X=0,Y=0,Width=115,Height=52}{X=0,Y=0,Width=72,Height=53}{X=0,Y=0,Width=58,Height=46}{X=0,Y=0,Width=47,Height=32}{X=0,Y=0,Width=41,Height=47}{X=0,Y=0,Width=38,Height=47}{X=0,Y=0,Width=33,Height=45}{X=0,Y=0,Width=22,Height=39}{X=0,Y=0,Width=0,Height=0}

visina is the height of the current rectangle, maxV=190, maxŠ=350 — user1649498, Sep 12 '12 at 03:55
Maybe it would be a little bit easier to answer your question if you don't mix English with Croatian/Serbian in your code :) — pero, Sep 12 '12 at 07:27
Weird, it doesn't seem possible that the length of the list `rectsToDraw` would be greater than the length of `Shapes`. Are you positive that `Shapes` only contains 14 elements? Can you add some debug output right before (or inside) the first `for` loop to be certain nothing weird is going on there? — rsbarro, Sep 12 '12 at 14:16

score 2 · Answer 1 · answered Sep 12 '12 at 03:22

2

There may be other problems, but I think this code:

for (int j = 0; j < rectsToDraw.Count; j++)
{
    Debug.Write(rectsToDraw[0]);
}

should be:

for (int j = 0; j < rectsToDraw.Count; j++)
{
    Debug.Write(rectsToDraw[j]);
}

(change Debug.Write(rectsToDraw[0]); to Debug.Write(rectsToDraw[j]);).

answered Sep 12 '12 at 03:22

rsbarro

27,021
9
71
75

thx, I did get that one wrong, but I changed it now and still get wrong data. – user1649498 Sep 12 '12 at 03:28
how is the data wrong? can you supply the inputs and outputs...? – rsbarro Sep 12 '12 at 03:33
added input, output list to my question. Also, I am thinking this might be similar to http://stackoverflow.com/questions/271440/c-sharp-captured-variable-in-loop – user1649498 Sep 12 '12 at 03:45

score 0 · Answer 2 · answered Sep 12 '12 at 17:34

Never mind, I managed to fix it... Code follows:

private void FNF()
    {
        int XMX = 0;
        int moveX= 0;
        int moveY = 0;
        int MH = RectBin.Height;
        int MW = RectBin.Width;
        int c1 = Items.Count;
        rectsToDraw = new List<Rectangle>();

        for(int i = 0; i < c1; i++)
        {
            int height = Oblici[i].Height;
            int width = Oblici[i].Width;
            if(((moveY + height) <= MV)&&((moveX+width)<=MW))
            {
                rectsToDraw.Add(new Rectangle(moveX, moveY, width, height));
                moveY = moveY + height;
                if (XMX < moveX + width)
                {
                    XMX = moveX + width;
                }
            }
            else if((XMX + width) <= MW)
            {
                moveX = XMX;
                rectsToDraw.Add(new Rectangle(moveX, 0, width, height));
                moveY = height;
                XMX = moveX + width;
            }
            else
            {
                Debug.Write("Doesn't fit.");
                break;
            }
        }
        for (int j = 0; j < rectsToDraw.Count; j++)
        {
            Debug.Write(rectsToDraw[j]);
        }
    }

Wrote it again and changed some names (for no reason).... Thanx anyway....

C# algorithm conundrum - bin packing

2 Answers2