2D-Packing codeV6

From CSclasswiki
Jump to: navigation, search

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.


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