2D-Packing codeV2

From CSclasswiki
Jump to: navigation, search
# Youyou Tian
# Sample 2-D packing, implemented in python
# algorithm by D. Thiebaut
# version 2, rectangles can cut the middle of
# segments, too

from graphics import *
from random import randrange
import copy

#temp measurements
MAX_WIDTH = 600
MAX_HEIGHT = 400

# 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, [198, 162, 242])

    # 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)

    # 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

# 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.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.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
        
    # 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((self._x, 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

# 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):
    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).
    # the height.area is used to sort the array
    for rect in rectList:
        if rect.getHeight() <= seg.getHeight():
            highRects.append((float("%d.%d" % (rect.getHeight(), rect.getArea())), rect))

    highRects.sort()   # may not need this, maybe a .max() will work as well
    try:               # returns the largest
        return highRects[-1][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
def cutSegs(lineList, rect):
    rectH = rect.getHeight()
    rectW = rect.getWidth()
    rectY = rect.getY()
    rectX = rect.getX()
    print()
    print("LineList")
    print(lineList)
    for line in lineList:
        print()
        print("segs in line", line)
        print("line", line.getX(), "rect", rectX + rectW)
        if line.getX() < rectX + rectW:
            for seg in line:
                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
    unpacked = [Rect(100, 220), Rect(200, 100), Rect(75, 75)]
    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)

    # woah look at all those indents
    while(len(unpacked) > 0):
        for line in lineList:
            for segment in line: # goes through each segment in the line and lineList
                tallestRect = findTallestRect(unpacked, segment)
                
                # continue using this segment until can't fill it anymore
                while tallestRect != None:
                    tallestRect.setCoords(line.getX(), segment.getY())
                    packed.append(tallestRect)

                    # chects to see if can add a completely new (full) line
                    #if tallestRect.getX() + tallestRect.getWidth() > lineList.getMax():
                    #    lineList.addLine(Line(tallestRect.getX() + tallestRect.getWidth(),
                    #                          MAX_HEIGHT))
                        
                    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)
                    tallestRect = findTallestRect(unpacked, segment)
                    
            lineList.clearZeros()
            #canvas.clear()
            lineList.draw(canvas)
                    
def main2():
    win = GraphicsWindow(int(MAX_WIDTH), int(MAX_HEIGHT))
    canvas = win.canvas()

    test(canvas)
    
main()

#main2()