Algorithm to divide surface

[Fury]

Hallo, i am a student programmer.

I'm looking for a solution to divide surface with less loss in vb.net.
It would be a program where the user would input length en width of the original surface. Then the user would input the new lengths en witdhs of the new surfaces wich the original would be divided in.

So i'm looking for a algorithm that can calculate how to divide the original surface into the new surfaces with less loss of the original surface.
Finally it should be shown on screen or being printed how to divide the original surface.

Can someone please help me, because i can"t seem to find a solution.

 

[JohnH]

Calculating how many small boxes that fits in the large box when vertically aligned is easy. One example is:

dim maxwidth as integer = availablewidth \ neededwidth
dim maxheight as integer = availableheight \ neededheigth
dim maxcount = maxwidth * maxheight

You can do the same calculation when the small box is aligned horizontally. Choosing the better of these two results is the basic optimized fit.

Sometimes if you put some of the small boxes vertically and some horizontally you can fit more boxes into the same original large box. I did this fun excercise and came up with this algorithm that checks best fit Vert/Horiz for each row and add the rectangles to a collection that is returned as an array at the end. The alignment of each row is determined by calculating max number of boxes that can be fitted in remainder of the big box.

Private Function BestFitRectangles(ByVal largeBox As Size, ByVal smallBox As Size) As Rectangle()
    Dim rectangles As New List(Of Rectangle)
    Dim smallBoxFlipped As New Size(smallBox.Height, smallBox.Width)
    Dim y As Integer
    Dim maxV As Integer = -1
    Dim maxH As Integer = -1
    Dim maxwidthV, maxheightV, maxwidthH, maxheightH As Integer
    'calculate rectangles
    Do Until (maxV = 0) And (maxH = 0)
        maxwidthV = largeBox.Width \ smallBox.Width
        maxheightV = (largeBox.Height - y) \ smallBox.Height
        maxV = maxwidthV * maxheightV
        maxwidthH = largeBox.Width \ smallBoxFlipped.Width
        maxheightH = (largeBox.Height - y) \ smallBoxFlipped.Height
        maxH = maxwidthH * maxheightH
        If maxH > maxV Then
            addrectanglesrow(rectangles, y, maxwidthH, smallBoxFlipped)
            y += smallBoxFlipped.Height
        ElseIf maxV > 0 Then
            addrectanglesrow(rectangles, y, maxwidthV, smallBox)
            y += smallBox.Height
        End If
    Loop
    Return rectangles.ToArray
End Function

Private Sub addrectanglesrow(ByVal rcts As List(Of Rectangle), _
                            ByVal y As Integer, _
                            ByVal maxwidth As Integer, _
                            ByVal sz As Size)
    For x As Integer = 0 To maxwidth - 1
        rcts.Add(New Rectangle(New Point(x * sz.Width, y), sz))
    Next
End Sub

You also needed to display the layout of all boxes, with all the rectangles ready there is not much work to draw it to a Bitmap:

Private Function drawFittedRectangles(ByVal largebox As Size, ByVal rectangles() As Rectangle) As Bitmap
    Dim bmp As New Bitmap(largebox.Width, largebox.Height)
    Using g As Graphics = Graphics.FromImage(bmp)
        g.Clear(Color.White)
        g.FillRectangles(Brushes.Yellow, rectangles)
        g.DrawRectangles(Pens.Blue, rectangles)
        'draw border
        largebox.Width -= 1
        largebox.Height -= 1
        g.DrawRectangle(Pens.Green, New Rectangle(Point.Empty, largebox))
        Return bmp
    End Using
End Function

Here the method I used to do the test calls, I placed a Picturebox on form to display the generated image and tell with messagebox how many rectangles were fitted:

Private Sub RectangleOptimization()
    Dim largeBox As New Size(100, 200)
    Dim smallBox As New Size(6, 26)
    Dim rcts() As Rectangle = BestFitRectangles(largeBox, smallBox)
    Me.PictureBox1.Image = drawFittedRectangles(largeBox, rcts)
    MessageBox.Show(String.Format("fitted {0} rectangles", rcts.Length))
End Sub

The sample output image:

I also ran some code to check the key values during processing of the rows optimization, just to check that the algoritm didn't take the wrong turn somewhere along the way (I would then expect to see a larger max somewhere in the path that wasn't achieved in the end), so for reference here is that data in relation to this sample:

[FONT="Courier New"]maxH 99 maxV 112 current 0   currentmax 112
maxH 87 maxV 96  current 16  currentmax 112
maxH 72 maxV 80  current 32  currentmax 112
maxH 60 maxV 64  current 48  currentmax 112
maxH 48 maxV 48  current 64  currentmax 112
maxH 33 maxV 32  current 80  currentmax 113
maxH 30 maxV 32  current 83  currentmax 115
maxH 18 maxV 16  current 99  currentmax 117
maxH 15 maxV 16  current 102 currentmax 118
maxH 3  maxV 0   current 118 currentmax 121
maxH 0  maxV 0   current 121 currentmax 121[/FONT]

You see the original best fit was 112 small boxes vertically aligned (or 99 horizontally), when the algorithm was done it had fitted 121!

For fun you can use this and calculate the utilization percentage for different cuts?

Perhaps someone can find a better calculation too?

 

[Fury]

Thanks a lot for the work you have done!
I just don't fully understand how to use all this code.

If i have 4 textboxes where the user can input the length en width of the big and the little box and i have a button "Calculate" how do i call all this code?

 

[JohnH]

I would use 4 NumericUpDown controls and use their values for width/height of the small/large box, and a button that calls RectangleOptimization method.

 

[JohnH]

Here is another sample output, the big box is 100*100 and small box is 17*27, 18 boxes were fitted:
As you can see, and it is really apparent for the eye, the 4 marked boxes can be removed and in place fits a column of 5 horizontal boxes, adding up to 19 boxes:
Can this be calculated automatically? anyone?

 

[Fury]

I called the RectangleOptimization method in a button click event and it seems to do the calculation but i don't see the image or the messagebox.

 

[JohnH]

Based on the proven failure described in previous post I have this new theory: first divide the large box in two according to the best distribution of vertical/horizontal boxes in a row, then do the rows fill same as before for both sections. Here is an image of how the large box is divided in A and B section:

​

I did 2400 simulated tests with different box sizes and got up to 10% better results than the previous algorithm in 10% of the cases (and none results worse), so I consider the new theory proven. Btw, here's the output with the previous mentioned key figures, result 19 boxes:

​

First sample for comparison with this method, now 125 boxes:

​

This time I attached a sample project so you won't get into trouble adding controls to form haha

 

[Fury]

Thanks a lot! I will work with this and try to find a solution for multiple small boxes with different sizes.

 

[Fury]

I'm afraid to ask it but i don't understand how i can use this to see how multiple small boxes wit each different sizes could fit in one big box.

 

[JohnH]

Don't be afraid, hehe, it would interesting to know, have you tried asking the math forums if there exist a formula or approach to solve such problems?

 

[Fury]

I just did.

 

[Fury]

I'm not getting any good answer at the moment.
Is it such a complex problem?

 

[JohnH]

I have no idea, did you get any answers at the math forums you asked?

 

[Fury]

Nope, i'm not getting any response on the math fora.

 

[Fury]

Do you think there is a way to use your code but instead of using the same small box that every different small box is used untill there are no small boxes left? It should try every possible combination of the small boxes...
I don't know how to calculate the best combination. There allways will be left the same amount of the big box.