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