2D-Packing codeV3

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

from graphics import *
from random import randrange
import copy

#temp measurements
MAX_WIDTH = 600
MAX_HEIGHT = 400
DEBUG1 = False
DEBUG2 = False
DEBUG_LOOPS = True

# Rect: extends the rectangle class from the graphics lbrary
# provided in CSC111
#
# using this class because may need other additional
# methods in the future
class Rect(Rectangle):

    # constructor, initializes a rectangle with a default
    # location at x,y = 0,0
    # @param w width of rectangle
    # @param h height of tectangle
    def __init__(self, w, h):
        super().__init__(0, 0, w, h, [randrange(255), randrange(255), randrange(255)])

    # draw() method
    # for debugging purposes, also prints out the rectangle's
    # width and height in the upper left corner
    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)) 
        
    # setCoords() changes the x and y without
    # calling setX() and setY()
    def setCoords(self, x, y):
        self._x = x
        self._y = y

    # setX() mutator, setter
    # @param x x location
    def setX(self, x):
        self._x = x
        
    # setY() mutator, setter
    # @param 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

    def __str__(self):
        return "(h: %d, w: %d)" % (self._height, self._width)

# Segment: Line used to figure out where is there space
# to place a rectangle
#
# adding in the x coord from Line because realized hard
# to extract x since not know which specific Line
class Segment:

    # Constructor
    # @param y y coordinate
    # @param x x coordinate
    # @param 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
    # for debugging purposes, prints out the x,y location of the
    # top beginning
    def draw(self, canvas):
        #drawLine is a method part of the Canvas class
        #canvas.setFill(255, 132, 0)
        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

    # Might not have uses, returns the y of the bottom
    # of the segment
    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
        
    # needs to be changed!!
    def getX(self):
        return self._x
    
    # setHeight() mutator, setter
    def setHeight(self, h):
        self._height = h

    # toString()
    # not completed
    def __str__(self):
        return str(self._y)
        
# Line: A list of Segments
# Every Line starts with a segment stretching to the top
# of the canvas.
#
# also going to take in the maxHeight of the canvas to
# have an initial height for the first segment
class Line:

    # Constructor, automatically creates a list with one Segment
    # @param x x location
    # @param 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
        #self._segList = []
        #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))]

    # Iterator lets me iterate through the Line object,
    # going through each segment
    def __iter__(self):
        for x, seg in self._segList:
            yield seg

    # draw() method
    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 loc
    def sort(self):
        self._segList.sort()

    # addSegment() adds another segment onto the list
    # @param seg the Segment that's eing appended
    #
    # trying to find its uses, will be important
    def addSegment(self, seg):
        self._segList.append((seg._y, seg))

    # at() gets the Segment at a particulat index
    # @param index particular index want to get from
    #
    # mostly used for testing
    def at(self, index):
        #print("sl", len(self._segList))
        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:
            #print(xseg[1].getHeight())
            if xseg[1].getHeight() == 0:
                #print("removing seg")
                self._segList.remove(xseg)

    # toString()
    # gives 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
#
# since passing in the maxHeight multiple times,
# maybe make it global? --or maybe not need to anymore
class LinesList:
    
    # Constructor creates a list of Lines
    # @param maxW the maxWidth of the canvas, used to set boundaries
    # @param 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()

    # Iterator lets me iterate through the LinesList object,
    # going through each Line
    def __iter__(self):
        for x, line in self._lineList:
            yield line

    #draw() method   
    def draw(self, canvas):
        for x, line in self._lineList:
            #print(line.getX())
            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 that is being added
    #
    #Curious if there are other ways to write this
    #I was first thinking to add, and sort, if it generates
    #an exception, don't add
    #or the other way is to just go through the list.
    #waht is lambda?
    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 index particular index want to get from
    #
    # mostly used for testing
    def at(self, index):
        #print("ll", self._lineList[0])
        return self._lineList[index][1]

    # getmax() returns the farthest x coord that a
    # rectangle has crossed
    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:
            #print("before")
            #print(line)
            line.clearZeros()
            #print("after")
            #print(line)

    # toString
    # currently only prints out the x associated
    def __str__(self):
        string = ""
        for x, line in self._lineList:
            string += "[" + str(x) + "]\n"#+ line + "]\n"
        return string

def removeImpossibleRect(rectList, maxW, maxH):
    for rect in rectList:
        if rect.getHeight() > maxH or rect.getWidth() > maxW:
            rectList.remove(rect)
            

# 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

# findTallestRect() finds the rectangle with the largest height
# but a shorter than the segment
# if two rectangles have the same height, returns the rectangle
# with the larger area. Otherwise based on how Python sorted it
# if there are no rectangles that fir the search criteria,
# none is returned instead
def findTallestRect(rectList, seg, lineList, maxW):
    highRects = []
    lineList.sort()
    # 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).
    # the height.area is used to sort the array
    for rect in rectList:
        rectH = rect.getHeight()
        rectW = rect.getWidth()
        if rectH <= seg.getHeight() and rectW + seg.getX() <= maxW:
            rectXi = seg.getX()
            rectXf = rectW + seg.getX()
            rectYi = seg.getY()
            rectYf = rectH + seg.getY()
            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:
                if line.getX() > rectXf:
                    break
                elif rectXi <= line.getX(): # line between rect
                    for testSeg in line:
                        segFits = 0 # store # of segs that can fit the rect
                        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
            #inside first if
            if goodRect: # means that has never broken out of the loop
                         # and crosses all segs
                         
#        #Has problems if the rectangles are of the same size and area
                #Appends a tuple
                highRects.append((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][2]
    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
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)

#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

    # there is a problem where it doesn't deal with the rect that can't
    # in so that unpacked will always have rects in it, so it is an
    # endless loop
    unpacked = [Rect(100, 220), Rect(200, 100), Rect(75, 75), Rect(700, 700)]
    for i in range(50, 200, 50):
        for j in range(50, 200, 50):
            unpacked.append(Rect(i, j))
        
    packed = []
    lineList = LinesList(MAX_WIDTH, MAX_HEIGHT)

    #Remove rects that are impossible
    removeImpossibleRect(unpacked, MAX_WIDTH, MAX_HEIGHT)

    # fix the condition
    while(len(unpacked) > 0):
        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
                tallestRect = findTallestRect(unpacked, segment, lineList, MAX_WIDTH)
                
                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 it anymore
                while tallestRect != None:
                    tallestRect.setCoords(line.getX(), segment.getY())
                    packed.append(tallestRect)
                        
                    cutSegs(lineList, tallestRect)
                    
                    # -- Testing graphical output --
                    canvas.clear()
                    lineList.draw(canvas)
                    for rect in packed:
                        rect.draw(canvas)
                    lineList.draw(canvas)
                    #input()
                    line.sort()
                    lineList.sort()
                    
                    unpacked.remove(tallestRect)
                    
                    if DEBUG1:
                        print("unpacked: ", unpacked)
                        print("packed: ", packed)
                        print()
                        
                    tallestRect = findTallestRect(unpacked, segment, lineList, MAX_WIDTH)
            line.sort()
            lineList.sort()       
            lineList.clearZeros()
            #canvas.clear()
            lineList.draw(canvas)
                    
def main2():
    win = GraphicsWindow(int(MAX_WIDTH), int(MAX_HEIGHT))
    canvas = win.canvas()

    test(canvas)
    
main()

#main2()

'''
 def __ne__(self, other):
        return (self._height, self.getArea()) != \
               (other._height, other.getArea())
    
    def __lt__(self, other):
        return (self._height, self.getArea()) < \
               (other._height, other.getArea())
    def __gt__(self, other):
        return (self._height, self.getArea()) > \
               (other._height, other.getArea())

    def __ge__(self, other):
        return (self._height, self.getArea()) >= \
               (other._height, other.getArea())
'''