2D-Packing codeV1

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

from graphics import *
from random import randrange

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

    # 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

        # not used
        #self._seg = Line(Point(self._x, self._y),
        #                 Point(self._x, self._y + self._height))

    # 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

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

    # toString()
    # not completed
    def __str__(self):
        return "h" + str(self._height)
        
# 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

    # 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.getX(), 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 = []

    # toString()
    # not completed
    def __str__(self):
        string = ""
        for x, seg in self._segList:
            string += seg + ", "
        return 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
    def addLine(self, line):
        self._lineList.append((line.getX(), line))

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

    # 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

#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()
    lineList.at(1).at(0).setHeight(100)
    lineList.at(1).addSegment(Segment(200, 150, 100))
    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:        
                    packed.append(tallestRect)
                    tallestRect.setX(line.getX()) # sets the official packed coords
                    tallestRect.setY(segment.getY())

                    # will later put into method?
                    # shorten seg
                    segment.setY(tallestRect.getY()+ tallestRect.getHeight())
                    #print(segment.getY())
                    segment.setHeight(MAX_HEIGHT - segment.getY())
                    line.sort()
                    # add another line
                    lineList.addLine(Line(tallestRect.getX() + tallestRect.getWidth(),
                                          MAX_HEIGHT))
                    # need to figure out how to shoren segments where have rectangle crossing

                    # -- Testing graphical output --
                    canvas.clear()
                    lineList.draw(canvas)
                    for rect in packed:
                        rect.draw(canvas)
                    lineList.draw(canvas)
                    
                    lineList.sort()
                    print(lineList)
                    
                    unpacked.remove(tallestRect)
                    tallestRect = findTallestRect(unpacked, segment)
                    
def main2():
    win = GraphicsWindow(int(MAX_WIDTH), int(MAX_HEIGHT))
    canvas = win.canvas()

    test(canvas)
    
main()

#main2()