Learn python programming through algorithms - Binpacking part 2

Bin packing algorithm for regular and irregular shapes

Part 2: Constructing the Binary tree (linked list)

s is the size, it is a tuple containing the length and the width.
c is the coordinate, it is a tuple that will contain its origin point and the origin point won't be the center.

Origin point for an inserted shape in red

The pointers right and left are used to construct the tree that we will discuss later.

occupants is used to hold some complex shapes such that the sorting function takes care of splitting the Node while sorting, thats one method to defeat stuttering as we defer some of the splitting overhead in the inserting stage to the sorting stage.

class Node:    
       def __init__(self, a=[0,0], b=[0,0]):
                   self.s = a
                   self.c = b 
                   self.left = False
                   self.right = False 
                   self.Rotate = False
                   self.occupants = []

A function that checks whether a shape fits within a container by comparing its length and width to the length and width of the container.

ptr is the pointer to the container, box is the shape.

def fits(box, ptr):  
     if ptr == False:
               return False
     if( (box.s[0] <= ptr.s[0]) and (box.s[1] <= ptr.s[1]) ):
                  return True  
     else:              
                 return False

Check whether the item will fit if rotated

def rotatefit(box, ptr):  
       if( (box.s[1] <= ptr.s[0]) and (box.s[0] <= ptr.s[1]) ):
                 return True
       else:  
                return False

We have two directions to go now,

When a shape is inserted, a container contains the shape as a leaf and each time we insert a new shape, we check whether it collides with the previous leafs.

When a shape is inserted, a container is split into leafs where the part taken by the shape is omitted and we have new containers constructed out of the remaining parts as leafs.

I took the second way as it was easier to implement, I had to make a collision detection algorithm later for something else though!

if we insert a shape inside a container then we have two ways to split a container.

Two ways to split a container.  

In the figure above,
you can see the inserted shape in blue and the remaining free area in gray,
there are two ways we can split the remaining area,

what if something can fit in one of the configs and can't fit in the other,
we can implement a separate function that checks for nearby empty spaces to combine them so a shape can fit, but to save on computations as traversing a tree to check for nearby areas can be expensive,
we can save those configs and if one of them works later, we can easily release the other,

and this is how we construct our tree.

we sort our tree such that for each config, the largest area is the node and the smallest area is the leaf.

then we sort nodes by size such that the smallest node is first.

So if we are traversing a tree then we check the first node, if it fits then we go right to check if we can fit it in the smaller leaf, and set the left pointer to False as we won't follow that config anymore, 

otherwise we go left to check if we fit in the other node, if we fit then we make that out first node.

if you are confused, lets follow the code.

container = Node([80, 40])                  #we construct a container with length =80 and width = 40 
box1        = Node([10, 15])                  #first box to be inserted
box2        = Node([20, 10])                  #second box to be inserted

we assign a pointer to the start node of the container, ptr = container then we check if its leaf fits as the leaf is always smaller than the parent node  fit(box, ptr,right), if True then that node fits well and the while loop will keep on going deeper to get to the smallest fitting part and we will eliminate any other configs / possible nodes along the way ptr.left = False

def insert(box, container):    
        ptr = container
        while fits(box, ptr.right):
                 ptr.left = False
                 ptr       = ptr.right

Now we are left with the last container that fits but maybe this is a node and we have other configs on the left, so we try that and we traverse its right as well, notice here that we bias the tree such that we jump over the first node and we connect the previous and the next node together ptr.right = ptr.left, then we go as normal trying to find the smallest leaf that fits.

if ptr.right.left == True:
      if fits(box, ptr.right.left):
           ptr.right = ptr.right.left
           ptr         = ptr.right
           while fits(box, ptr.right):
                   ptr.left = False
                   ptr       = ptr.right

One weird thing to note here, originally i wrote the __init__ function for the Node class like this,
def __init__(self, a=[], b=[]) ,then initialized multiple boxes consecutively, so as to assign the coordinates and sizes later,
box1 = Node()
box2 = Node()
but then i had all sorts of errors and i thought it was my algorithm but when i did hex(id(box1)) and hex(id(box2)), i discovered that both had the same memory location and if i initialized more boxes, then the same thing happened, this is with python 3.6.9 , so if i later assign box1.c = (5,15), i find that box2.c is (5,15) as well!.

So i had to initialize the class with this def __init__(self,  a=[0]*3,  b=[0]*3)
[0]*3 is a shorthand for [0, 0, 0] , then the whole memory sharing between boxes problem is solved but i went through some problems again and found out later that if i set a[0] = 1 then a[1] & a[2] automatically are equal to , and checking again, i found that the three positions in the list, a[0],a[1] & a[2] shared the same memory as well!

I love python but the problem with it in my opinion iss documentation and mixed directions that cause some sorts of undocumented/ undefined behaviour, some say its too much freedom.

Tune in for the rest of tutorials 😊