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