2D-Packing codeV4

From CSclasswiki
Jump to: navigation, search
# Youyou Tian
# Sample 2-D packing, implemented in python
# Algorithm by D. Thiebaut
# Version 4

from graphics import *
from random import randrange
import copy

# Temp measurements
MAX_WIDTH = 600
MAX_HEIGHT = 400
DEBUG1 = True
DEBUG2 = False
DEBUG_LOOPS = False
DEBUG_RECT = False
RECT_ID = 0

# Rect: extends the rectangle class from the graphics lbrary
# provided in CSC111
class Rect(Rectangle):

    # Constructor, initializes a rectangle with a default
    # location at x,y = 0,0 and a random color
    # @param int w width of rectangle
    # @param int h height of tectangle
    def __init__(self, w, h, rectID):

        super().__init__(0, 0, w, h, [randrange(255), randrange(255), randrange(255)])
        self._rectID = rectID
  
    # draw() draws the rectangle and for debugging purposes,
    # also prints out the rectangle's width and height in
    # the upper left corner of the rectangle
    def draw(self, canvas):
        canvas.setOutline(0,0,0)
        super().draw(canvas)
        wh = "(h: %d, w: %d)" % (self._height, self._width)
        canvas.drawText(self._x, self._y, wh)
        if DEBUG1:
           print("Drawing rect: ((%d, %d): (h: %d, w: %d))" % \
                 (self._x, self._y, self._height, self._width)) 

    # eq() checks if two rectangles are equal
    # to each other
    # @param Rectangle other second rectangle comparing to
    def __eq__(self, other):
        try:
            return (self._height, self.getArea()) == \
                   (other._height, other.getArea())
        except AttributeError:
            return False
            
    # lt(Rectangle other) checks if the first rectangle is
    # less than the second rectangle
    # @param Rectangle other second rectangle comparing to
    def __lt__(self, other):
        return (self._height, self.getArea()) < \
               (other._height, other.getArea())
        
    # setCoords() changes both x and y
    def setCoords(self, x, y):
        self._x = x
        self._y = y

    # setX() mutator, setter
    # @param int x x location
    def setX(self, x):
        self._x = x
        
    # setY() mutator, setter
    # @param int y y location
    def setY(self, y):
        self._y = y

    # getY() accessor, getter
    def getY(self):
        return self._y

    # getX() accessor, getter
    def getX(self):
        return self._x

    # getHeight() accessor, getter
    def getHeight(self):
        return self._height

    # getWidth() accessor, getter
    def getWidth(self):
        return self._width

    # getArea() returns the area of the Rectangle
    def getArea(self):
        return self._width * self._height

    # str() returns a string of the rectangle's width and height
    def __str__(self):
        return "(h: %d, w: %d)" % (self._height, self._width)

# Segment: a line used to figure out where is there space
# to place a rectangle
class Segment:

    # Constructor
    # @param int y y coordinate
    # @param int x x coordinate
    # @param int h height of the segment
    def __init__(self, y, x, h):
        self._y = y
        self._x = x
        self._height = h

    # draw() method
    # draws the segment using the drawLine function part of the
    # canvas class and colors it red. For debugging purposes, prints
    # out the x,y location at the top of the segment
    def draw(self, canvas):
        #drawLine is a method part of the Canvas class
        canvas.setOutline(255, 0, 0)
        canvas.drawLine(self._x, self._y, self._x, self._y + self._height)
        
        #xy = "(x: %d, y: %d)" % (self._x, self._y)
        #canvas.setOutline(0,0,0)
        #canvas.drawText(self._x, self._y, xy)

    # getHeight() accessor, getter
    def getHeight(self):
        return self._height

    # getY() accessor, getter
    def getY(self):
        return self._y
    
    # getX() accesson, getter
    def getX(self):
        return self._x

    # getTail() returns the bottom y coordinate where the
    # segment ends
    def getTail(self):
        return self._height + self._y

    # setY() mutator, setter
    def setY(self, y):
        self._y = y

    # setX() mutator, setter
    def setX(self, x):
        self._x = x
    
    # setHeight() mutator, setter
    def setHeight(self, h):
        self._height = h

    # str() returns a string of the segment's y coord
    def __str__(self):
        return str(self._y)
        
# Line: A list of Segments
# Every Line starts with a segment stretching the length of the
# entire canvas
class Line:

    # Constructor, automatically creates a list with one Segment
    # @param int x x location
    # @param int maxH maxHeight the Line/Segment can be, mostly used
    #        to initialize the first Segment
    # Each element is a tuple (x, Segment), to allow for easy sorting
    def __init__(self, x, maxH):
        self._x = x;
        self._maxHeight = maxH
        
        # Auto creates 1 segment running the entire height of the canvas
        # first 0 represents the top of the canvas
        self._segList = [(0, Segment(0, self._x, self._maxHeight))]

    # iter() Allows iteration through the Line object
    # goes through each segment
    def __iter__(self):
        for x, seg in self._segList:
            yield seg

    # draw() draws all the segments in the line
    def draw(self, canvas):
        for x, seg in self._segList:
            seg.draw(canvas)

    # getX() accessor, getter
    def getX(self):
        return self._x

    # setX() sets the x cood for the line and all its segments
    def setX(self, x):
        self._x = x
        for xLine, seg in self._segList:
            seg.setX(x)

    # sort() sorts through the array by increasing x coord
    def sort(self):
        self._segList.sort()

    # addSegment() adds another segment onto the list
    # @param Segment seg the Segment that's being appended
    def addSegment(self, seg):
        self._segList.append((seg._y, seg))

    # at() gets the Segment at a particulat index
    # @param int index particular index want to get from
    def at(self, index):
        return self._segList[index][1]

    # might need one day
    #
    # def delSegment(self, seg):

    # delLine() deletes all the segments in the line
    # mostly used to create L_inf
    def delLine(self):
        self._segList = []

    # clearZeros() clears all the segments that have 0 heights
    def clearZeros(self):
        for xseg in self._segList:
            if xseg[1].getHeight() == 0:
                self._segList.remove(xseg)

    # str() returns a string of the x coord, y coords of the segments
    def __str__(self):
        string = ""
        for x, seg in self._segList:
            string += str(seg.getY()) + ", "
        return "%d: %s" % (self._x, string)

# LinesList: a list that contains all the lines
class LinesList:
    
    # Constructor creates a list of Lines
    # @param int maxW the maxWidth of the canvas, used to set boundaries
    # @param int maxH the maxHeight of the canvas, used to set boundaries
    #
    # Since it is created only once, the constructor sets
    # up the initial Line L_0 and L_inf
    def __init__(self, maxW, maxH):
        self._maxHeight = maxH
        self._maxWidth = maxW

        #sets the L_0 and L_inf
        self._lineList = [(0, Line(0, self._maxHeight)),
                         (self._maxWidth, Line(self._maxWidth, self._maxHeight))]
        self._lineList[-1][1].delLine()

    # iter() Allows iteration through the LineList object
    # goes through each line
    def __iter__(self):
        for x, line in self._lineList:
            yield line

    #draw() Draws all the lines  
    def draw(self, canvas):
        for x, line in self._lineList:
            line.draw(canvas)

    # sort() sorts based on increasing x coord
    # assumes there are no overlapping lines with the same x
    def sort(self):
        #self._lineList = sorted(self._lineList, key = lambda linesList:linesList._lineList)
        self._lineList.sort()

    # addLine() adds another Line to the list
    # @param Line line Line that is being added
    #
    # Tests to make sure no duplicate lines of the
    # same x coord can be added
    def addLine(self, line):
        self._lineList.append((line.getX(), line))
        try:
            self._lineList.sort()
        except TypeError:
            del self._lineList[-1]

    # at() gets the Line at a particulat index
    # @param int index particular index want to get from
    def at(self, index):
        return self._lineList[index][1]

    # getmax() returns the farthest x coord that a
    # rectangle has crossed, not including the maxWidth
    def getMax(self):
        return self._lineList[-2][0]

    # clearZeros() clears all the segments that have heights of 0
    def clearZeros(self):
        for x, line in self._lineList:
            line.clearZeros()


    # str() returns a string of all the x coords of the lines
    def __str__(self):
        string = ""
        for x, line in self._lineList:
            string += "[" + str(x) + "]\n"#+ line + "]\n"
        return string

# currently generating rect that are atmost 1/4 of the screen
# used for testing
def generateRandRect(num):
    rectList = []
    for i in range(num):
        width = randrange(MAX_WIDTH)//2
        height = randrange(MAX_HEIGHT)//2
        rect = Rect(width, height)
        #rect.setX(width)
        #rect.setY(height)
        rectList.append(rect)

    return rectList

# currently generating rect that are atmost 1/4 of the screen
# while generating Rect, also keeping track of the total area.
#
# will be the final function
def generateRandRectArea(num):
    rectList = []
    area = 0
    for i in range(num):
        width = randrange(MAX_WIDTH)//2
        height = randrange(MAX_HEIGHT)//2
        area += width * height
        rect = Rect(width, height)
        rectList.append(rect)
    return rectList, area

# rmLargeRect() removes unfit rectangles
# @param List rectList list of rectangles
# @param int maxW width of the canvas
# 
# currently just removes the rects that are too big for the canvas
def rmLargeRect(rectList, maxW, maxH, lineList):
    furthestPlaced = lineList.getMax()
    
    for rect in rectList:
        if rect.getWidth() > maxW or rect.getHeight() > maxH:
            rectList.remove(rect)  
    
# findTallestRect() finds the rectangle with the largest height
# but a shorter than the segment
# @param list rectList list of rectangles
# @param Segment seg the segment trying to pack a rectangle into
# @param LineList lineList
# @param int maxW width of the canvas
#
# If two rectangles have the same height, returns the rectangle
# with the larger area. Otherwise, if there are no rectangles that
# fits the search criteria, none is returned instead
def findTallestRect(rectList, seg, lineList, maxW):
    highRects = []
    
    # Goes through the list, trying to find rectangles that
    # can fit the segment and appends it into a list highRects
    # that holds a tuple (float(height.area), Rect).
    if DEBUG_RECT:
        print("--------------------------------")
        print("THESE ARE THE RECT IM WORKING WITH")
        for r in rectList:
            print(r)
        print("THIS IS MY SEG HEIGHT", seg.getHeight())
        print()
        
    for rect in rectList:
        if DEBUG_RECT:
            print("~~~~~~~~~~~~~")
            print("WORKING WITH", rect.getHeight(), rect.getWidth())
        rectH = rect.getHeight()
        rectW = rect.getWidth()
        rectXi = seg.getX()
        rectXf = rectW + seg.getX()
        rectYi = seg.getY()
        rectYf = rectH + seg.getY()
        if rectH <= seg.getHeight() and rectXf <= maxW:
            if DEBUG_RECT:
                print("FITS IN SEG")
            goodRect = True
            ##listIntersect = []
            # this is like line intersect, need to write a method to give
            # a list of all lines that intersect rect
            for line in lineList:
                lineList.sort()
                line.sort()
                
                if DEBUG_RECT:
                    print()
                    print("IM LOOKING AT THIS LINE", end = " ")
                    print(line)
                    
                if line.getX() > rectXf:
                    if DEBUG_RECT:
                        print("THIS LINE IS PAST RECT WIDTH")
                    break
                
                elif rectXi <= line.getX(): # line between rect
                    segFits = 0             # store # of segs that can fit the rect
                    for testSeg in line:
                        if testSeg.getY() <= rectYi and \
                           testSeg.getTail() >= rectYf:
                            segFits += 1
                    if segFits == 0:     # this breaks out of the lineInterset testing
                        goodRect = False # rect not good
                        break            # but not out of trying to find a rect
                    if DEBUG_RECT:
                        print("THIS IS A GOOD RECT")
                        print("~~~~~~~~~~~~~")
            #inside first if
            if goodRect: # means that has never broken out of the loop
                         # and crosses all segs        
                highRects.append(rect)#((rect.getHeight(), rect.getArea(), rect))

    highR = sorted(highRects)  # may not need this, maybe a .max() will work as well
    try:                       # returns the largest
        return highR[-1]
    except IndexError: # Sometimes there are no rectangles that arae shorter  
        return None    # than the segment so None is returned instead

# cutSegs() given a rectange, goes through all the segments
# them based on where the rectangle intersects them
# also adds a new Line if an entire Line could not have been
# created previously
# @param LineList lineList
# @param Rectangle rect
def cutSegs(lineList, rect):
    rectH = rect.getHeight()
    rectW = rect.getWidth()
    rectY = rect.getY()
    rectX = rect.getX()
    if DEBUG2:
        print()
        print("LineList")
        print(lineList)
    for line in lineList:
        if DEBUG2:
            print()
            print("segs in line", line)
            print("line", line.getX(), "rect", rectX + rectW)
        if line.getX() < rectX + rectW:
            for seg in line:
                if DEBUG2:
                    print("segy", seg.getY())
                    print("seg", seg.getTail(), "rect", rectY + rectH)
                    print("test1", rectY, ">=", seg.getY())
                    print("test2", rectY + rectH, "<=", seg.getTail())
                if rectY >= seg.getY() and \
                   rectY + rectH <= seg.getTail(): #if rect cuts seg
                    newLine = copy.deepcopy(line) #returns a deep copy of the Line object
                    #print("in the if, going to add segs")
                    #splits segments by shortening the first one and adding a second one
                    #have to check if this works if put a rect at the top of a seg.
                    #prob need a check for if the seg length is 0, delete.??
                    line.addSegment(Segment(rectH + rectY, line.getX(),
                                            seg.getTail() - (rectH + rectY)))
                    seg.setHeight(rectY - seg.getY())
            #print("in seg rt now line", line)
    
    newLine.setX(rectW + rectX)
    #print("NEWLINE", newLine)
    lineList.addLine(newLine)
    #print(lineList)

# Remove rect by ID
#def removeRect(rect, id):
    

#test testing
def test(canvas):
    rectList = generateRandRect(5)
    #for rect in rectList:
    #    rect.draw(canvas)

    lineList = LinesList(MAX_WIDTH, MAX_HEIGHT)
    lineList.draw(canvas)
    lineList.addLine(Line(150, MAX_HEIGHT))
    lineList.addLine(Line(250, MAX_HEIGHT))
    lineList.sort()
    print(lineList)
    lineList.at(1).at(0).setHeight(100)
    lineList.at(1).addSegment(Segment(200, 150, 100))
    lineList.addLine(Line(300, MAX_HEIGHT))
    print(lineList)
    lineList.sort()
    lineList.draw(canvas)

# main
def main():
    # eventually will generate canvas size that is changing w/
    # the total area of the Rects
    
    win = GraphicsWindow(int(MAX_WIDTH), int(MAX_HEIGHT))
    canvas = win.canvas()

    # set testing rectangles
    unpacked = [Rect(100, 100, 200)]
    for i in range(50, 150, 50):
        for k, j in enumerate(range(50, 150, 50)): #enumerate goes 0,1,2...for every value
            unpacked.append(Rect(i, j, k))
        
    packed = []
    lineList = LinesList(MAX_WIDTH, MAX_HEIGHT)
    counter = 0
    #Only goes through the entire lineList twice
    while(len(unpacked) > 0 and counter < 2):
        #set boolean
        found1 = False
        for line in lineList:
            if DEBUG_LOOPS:
                print("+++++++++++++++++++++++++++++++++++++++++++++++++++++")
                print("ORDER OF MY LINES")
                print(lineList)
                print("WHICH LINE IM IN")
                print(line)
                print()
            for segment in line: # goes through each segment in the line and lineList
                rmLargeRect(unpacked, MAX_WIDTH, MAX_HEIGHT, lineList)
                tallestRect = findTallestRect(unpacked, segment, lineList, MAX_WIDTH)
                if tallestRect != None:
                    found1 = True
                if DEBUG_LOOPS:
                    print("~~~~~~~~~~~~~~~~")
                    print("IN THE LINE", line.getX())
                    print("IN THIS SEGMENT", segment.getY())
                    print("THIS IS THE LENGTH OF MY SEG", segment.getHeight())
                    print("THIS IS THE RECT IVE FOUND")
                    print(tallestRect)
                    print("~~~~~~~~~~~~~~~~")
                    print()
                
                # continue using this segment until can't fill rects anymore
                while tallestRect != None:
                    tallestRect.setCoords(line.getX(), segment.getY())
                    
                        
                    cutSegs(lineList, tallestRect)
                    
                    # -- Testing graphical output --
                    canvas.clear()
                    lineList.draw(canvas)
                    for rect in packed:
                        rect.draw(canvas)
                    lineList.draw(canvas)
                    
                    line.sort()
                    lineList.sort()
                    
                    unpacked.remove(tallestRect)
                    packed.append(tallestRect)
                    
                    if DEBUG1:
                        print("unpacked: ", unpacked)
                        print("packed: ", packed)
                        print()
                        
                    tallestRect = findTallestRect(unpacked, segment, lineList, MAX_WIDTH)
                    if tallestRect != None:
                        found1 = True
            line.sort()
            lineList.sort()       
            #lineList.clearZeros()
            #canvas.clear()
            lineList.draw(canvas)
        counter += 1
                    
def main2():
    win = GraphicsWindow(int(MAX_WIDTH), int(MAX_HEIGHT))
    canvas = win.canvas()

    test(canvas)
    
main()

#main2()