2D-Packing codeV6
Add a description of what this code does. Purpose: collage. Input. Output. Might be nice to have a diagram. Google docs has a draw option that allows for nice charts.
Contents
generateCollage.bat
::Youyou Tian
::12/22/14
::Batch file that calls python programs to create csv files used for resizing
::images and then takes each image, resizes them based on a certain weight
::and puts them on a collage.
::File must be in the same directory as the csv files
::
::Purpose: Build a collage
::Input: Images in a folder
::Output: A collage (dimensions can be specified) of resized images
@ECHO OFF
setlocal EnableExtensions EnableDelayedExpansion
C:\Python33\python.exe generateDims.py
C:\Python33\python.exe generateWeightsDemo.py
C:\Python33\python.exe generateWeights.py
C:\Python33\python.exe generateRects.py
set newDirec=C:\Users\Youyou\Desktop\compSci\STRIDE_14-15\fixedPics\
set oldDirec=C:\Users\Youyou\Desktop\compSci\STRIDE_14-15\pics\
set /a count=1
FOR /F "tokens=1-6 delims=, " %%a IN (imageRect.csv) DO (
set ID=%%a
set oldName=%%b
set newName=_%%b
set x=%%c
set y=%%d
set width=%%e
set height=%%f
::Converts original image to new dimensions
convert C:\Users\Youyou\Desktop\compSci\STRIDE_14-15\pics\%%b -resize %%ex%%f! _%%b
move _%%b C:\Users\Youyou\Desktop\compSci\STRIDE_14-15\fixedPics\ >nul 2>&1
::Creates the collage
IF !count!==1 (
convert -page +0+0 C:\Users\Youyou\Desktop\compSci\STRIDE_14-15\fixedPics\_%%b -background black -mosaic collage.png
set /a count=count+1
) ELSE (
convert -page +0+0 collage.png -page +%%c+%%d C:\Users\Youyou\Desktop\compSci\STRIDE_14-15\fixedPics\_%%b -background black -mosaic collage2.png
del collage.png
ren collage2.png collage.png
)
)
pause
generateDims.py
# Youyou Tian
# 12/22/14
# Takes in the images located in a folder and generates a csv
# with an ID, imageName, width, height
#
# Input: Pictures in a specified directory. All types of pictures should be accepted
# Output: A .csv with an ID, the name of the image, and the image's width and height
import subprocess
import glob
import csv
#Location of the pictures
picDirec = "C:\\Users\\Youyou\\Desktop\\compSci\\STRIDE_14-15\\pics"
#Name and location of the output .csv, "imageDim.csv"
csvFile = "C:\\Users\\Youyou\\Desktop\\compSci\\STRIDE_14-15\\imageDim.csv"
try: #Clears the file if previously written
file = open(csvFile, "w").close()
except FileNotFoundError:
pass
#assumes all files in the directory are pictures
ID = 0
for pic in glob.glob(picDirec + "\\*"):
ID += 1
process = subprocess.Popen(["identify", pic],
shell = True,
stdout = subprocess.PIPE,
stderr = subprocess.STDOUT)
out = process.communicate()
info = out[0].decode("utf-8").split(" ")
name = info[0].split("\\")[-1]
dim = info[2].split("x")
width = int(dim[0])
height = int(dim[1])
with open(csvFile, "a") as output:
writer = csv.writer(output, lineterminator = "\n")
writer.writerow([ID, name, width, height])
Sample csv output:
ID, imageName, width, height
1,pic1.jpg,391,129
2,pic10.jpg,410,300
3,pic11.jpg,666,443
4,pic12.jpg,720,467
generateWeights.py
# Youyou Tian
# 12/22/14
# Takes in a csv with an ID and weight and computes
# the scale, percentage of the area of the canvas the images
# will be resized to.
# Items with the same weight should be the same size after
# scaling.
# Creates a csv that gives ID, weight, scale. The weight will
# be later replaced by relevant data. The larger the weight, the
# larger the scaled image.
import csv
import sys
direc = "C:\\Users\\Youyou\\Desktop\\compSci\\STRIDE_14-15\\"
csvFile = "C:\\Users\\Youyou\\Desktop\\compSci\\STRIDE_14-15\\imageWeight.csv"
weightCsv = "C:\\Users\\Youyou\\Desktop\\compSci\\STRIDE_14-15\\imageWeightDemo.csv"
try:
file = open(direc + "imageDim.csv", "r")
except FileNotFoundError:
print("Invalid File Name")
sys.exit()
try: #Clears the file if previously written
weightFile = open(csvFile, "w").close()
except FileNotFoundError:
pass
picsInfo = file.read().split("\n")
file.close()
weights = []
for line in open(weightCsv, "r").read().split("\n"):
if len(line) == 0:
continue
weights.append(int(line.split(",")[-1]))
totalWeight = sum(weights)
for i in range(len(picsInfo)):
try:
info = picsInfo[i].split(",")
ID = info[0]
scale = weights[i]/totalWeight
except:
continue
with open(csvFile, "a") as output:
writer = csv.writer(output, lineterminator= "\n")
writer.writerow([ID, weights[i], scale])
Sample csv output:
ID, weight, scale
1,70,0.08333333333333333
2,40,0.047619047619047616
3,40,0.047619047619047616
4,20,0.023809523809523808
generateRects.py
# Youyou Tian
# 12/22/14
# Takes in the csv generated by generateDims.py and generateWeights.py
# and runs the packing algorithm located in V6 of the packing code.
# Creates a csv used to resize the image and generate the final collage.
# ID, imageName, x, y, newWidth, newHeight
import csv
import sys
import math
from packingV6 import *
direc = "C:\\Users\\Youyou\\Desktop\\compSci\\STRIDE_14-15\\"
csvFile = "C:\\Users\\Youyou\\Desktop\\compSci\\STRIDE_14-15\\imageRect.csv"
MAX_WIDTH = 400
MAX_HEIGHT = 300
TOTAL_AREA = MAX_WIDTH * MAX_HEIGHT
# Opens up the csv files for original image dimensions
# and weights
try:
dimFile = open(direc + "imageDim.csv", "r")
weightFile = open(direc + "imageWeight.csv", "r")
except FileNotFoundError:
print("Invalid File Name")
sys.exit()
# Clears the csv if previously written
try:
rectFile = open(csvFile, "w").close()
except FileNotFoundError:
pass
dimsInfo = dimFile.read().split("\n")
weightsInfo = weightFile.read().split("\n")
dimFile.close()
weightFile.close()
rectList = []
IDmatch = {}
for i in range(len(dimsInfo)):
try:
dim = dimsInfo[i].split(",")
weight = weightsInfo[i].split(",")
ID = dim[0]
name = dim[1]
origW = int(dim[2])
origH = int(dim[3])
scale = float(weight[2])
IDmatch[ID] = name
except: # catches an error in the last line, which when
continue # created, is only a space.
# Calculates the new image dimensions
newArea = scale * TOTAL_AREA
newH = math.sqrt(newArea * origH/origW)
newW = newArea/newH
rectList.append(Rect(int(newW), int(newH), ID))
# Packs the rectangles to get location on scaled canvas
packedList = pack(MAX_WIDTH, MAX_HEIGHT, rectList, 1.4)
imageRow = []
for rect in packedList:
ID = str(rect.getID())
x = str(rect.getX())
y = str(rect.getY())
width = str(rect.getWidth())
height = str(rect.getHeight())
imageRow.append([ID, IDmatch[ID], x, y, width, height])
with open(csvFile, "a") as output:
writer = csv.writer(output, lineterminator = "\n")
writer.writerow([ID, IDmatch[ID], x, y, width, height])
Sample csv output:
ID, imageName, x, y, width, height
19,pic9.jpg,0,0,106,106
14,pic4.jpg,0,106,69,103
18,pic8.jpg,0,209,75,94
6,pic14.jpg,0,303,110,77
packingV6.py
# Youyou Tian
# 12/22/14
# Sample 2-D packing, implemented in python
# Algorithm by D. Thiebaut
# Version 6
from graphics import *
from random import randrange
import copy
import math
# Temp measurements
MAX_WIDTH = 400
MAX_HEIGHT = 300
# 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)
# 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
def getID(self):
return self._rectID
# 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]
# 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
# generateRandRectDim() generates random rectanges of a given
# randrange and returns a canvas width and height based on
# the aspect ratio of 4:3
# @param int num number of rectanges generated
def generateRandRectDim(num):
rList = []
area = 0
for i in range(num):
width = randrange(40, 150, 5)
height = randrange(50, 150, 5)
area += width * height
rect = Rect(width, height, i)
rList.append(rect)
height = int(math.sqrt(area*3/4))
width = int((4/3)*height)
return rList, width, height
# 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).
for rect in rectList:
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:
goodRect = True
for line in lineList:
lineList.sort()
line.sort()
if line.getX() > rectXf:
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
#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()
for line in lineList:
if line.getX() < rectX + rectW:
for seg in line:
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
#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())
newLine.setX(rectW + rectX)
lineList.addLine(newLine)
# removeByID() Removes a rect based on its ID
# @param List rectList list of rects
# @param int ID unique ID of rectangle that needs to be removed
def removeByID(rectList, ID):
for i in range(len(rectList)):
try:
if rectList[i].getID() == ID:
rectList = rectList[:i] + rectList[i+1:]
except IndexError: #Last Element
rectList = rectList[:i]
return rectList
# generateRectsDim() Opens up the generated CSV files for image
# width and height and weight and returns a list of modified
# rectangles with dimensions based on a given weight
def generateRectsDim(dimFileName, weightFileName, maxW, maxH):
try:
dimFile = open(dimFileName, "r")
weightFile = open(weightFileName, "r")
except FileNotFoundError:
print("Invalid File Name")
return
dims = dimFile.read().split("\n")
weights = weightFile.read().split("\n")
dimFile.close()
weightFile.close()
totalArea = maxW * maxH
rectList = []
for i in range(len(dims)):
try: #The CSV contains an extra new line
dim = dims[i].split(",")
image = dim[1]
origWidth = int(dim[2])
origHeight = int(dim[3])
except:
continue
weight = int(weights[i].split(",")[1])
w1 = weight/100
a1 = w1 * totalArea
newH = math.sqrt(a1*origHeight/origWidth)
newW = a1/newH
rectList.append(Rect(int(newW), int(newH), dim[0]))
return rectList
#returns list of packed Rect objects
def pack(maxW, maxH, unpacked, canvasScale):
maxW *= canvasScale
maxH *= canvasScale
win = GraphicsWindow(int(maxW), int(maxH))
canvas = win.canvas()
packed = []
lineList = LinesList(maxW, maxH)
counter = 0
#Only goes through the entire lineList twice
while(len(unpacked) > 0 and counter < 1):
for line in lineList:
for segment in line: # goes through each segment in the line and lineList
rmLargeRect(unpacked, maxW, maxH, lineList)
tallestRect = findTallestRect(unpacked, segment, lineList, maxW)
# continue using this segment until can't fill rects anymore
while tallestRect != None:
tallestRect.setCoords(line.getX(), segment.getY())
cutSegs(lineList, tallestRect)
line.sort()
lineList.sort()
unpacked = removeByID(unpacked, tallestRect.getID())
packed.append(tallestRect)
tallestRect = findTallestRect(unpacked, segment, lineList, maxW)
line.sort()
lineList.sort()
lineList.clearZeros()
counter += 1
return(packed)
#draws the rectangles on a canvas given the generated rectCsv
def draw(maxW, maxH, canvasScale, rectCsv):
maxW *= canvasScale
maxH *= canvasScale
win = GraphicsWindow(int(maxW), int(maxH))
canvas = win.canvas()
try:
rectFile = open(rectCsv, "r")
except FileNotFoundError:
print("Invalid File Name")
rectInfo = rectFile.read().split("\n")
for rectangle in rectInfo:
if len(rectangle) < 5:
continue
rect = rectangle.split(",")
ID = int(rect[0])
x = int(rect[2])
y = int(rect[3])
w = int(rect[4])
h = int(rect[5])
r = Rect(w,h,ID)
r.setCoords(x,y)
r.draw(canvas)
win.wait()
win.close()
