Skip to content

Instantly share code, notes, and snippets.

@gudnm
Created March 29, 2011 18:33
Show Gist options
  • Save gudnm/892951 to your computer and use it in GitHub Desktop.
Save gudnm/892951 to your computer and use it in GitHub Desktop.
Simple procedural program that finds a smallest rectangle to accommodate a given set of rectangles
#include <iostream>
#include <cmath>
using namespace std;
struct placedRect
{
int x,
y,
width,
height;
};
struct rectToPack
{
int width,
height,
area,
weight;
};
void swap(int& a, int& b)
{
a+=b;
b=a-b;
a-=b;
}
bool print_layout(char* a, int width, int height)
{
for (int i=0; i<height; i++) {
for (int j=0; j<width; j++) {
cerr << a[i+j*height];
}
cerr << "\n";
}
return true;
}
int compare_weights (const void * a, const void * b)
{
return (*((int*)b+3) - *((int*)a+3));
}
int find_next_divisor(int number, int previous)
{
for (int i=previous+1; i<=sqrt(number); i++)
if (number % i == 0)
return i;
return 0;
}
void place(char * bin, placedRect best, int const height, char * layout)
{
int xBoundary=best.x+best.width;
for (int i=best.x; i<xBoundary; i++) //from left side to right
memset(bin+i*height+best.y,'\1',best.height); //set all columns to 'x's
int x1=best.x,
x2=best.x+best.width-1,
y1=best.y,
y2=best.y+best.height-1;
//drawing
layout[x1*height+y1] = '+';
layout[x1*height+y2] = '+';
layout[x2*height+y1] = '+';
layout[x2*height+y2] = '+';
for (int i=x1+1; i<x2; i++) {
int j=y1;
layout[i*height+j] = '-';
j=y2;
layout[i*height+j] = '-';
}
for (int j=y1+1; j<y2; j++) {
int i=x1;
layout[i*height+j] = '|';
i=x2;
layout[i*height+j] = '|';
}
}
int scores(char * bin, placedRect pos, int const width, int const height)
{
int score=0;
int const i=pos.x, j=pos.y, fw=pos.width, fh=pos.height, iw=i+fw, jh=j+fh;
//find left side touching perimeter
if (i==0) {
score+=fh;
} else if (i-1>=0) {
int n=i-1;
for (int m=j; m<jh; m++) {
if (bin[n*height+m]) {
score++;
}
}
}
//find bottom side touching perimeter
if (j==0) {
score+=fw;
} else if (j-1>=0) {
int m=j-1;
for (int n=i; n<iw; n++) {
if (bin[n*height+m]) {
score++;
}
}
}
//find right side touching perimeter
if (iw==width) {
score+=fh;
} else if (iw<width) {
int n=iw;
for (int m=j; m<jh; m++) {
if (bin[n*height+m]) {
score++;
}
}
}
//find top side touching perimeter
if (jh==height) {
score+=fw;
} else if (jh<height) {
int m=jh;
for (int n=i; n<iw; n++) {
if (bin[n*height+m]) {
score++;
}
}
}
return score;
}
bool fits(char * bin, placedRect pos, int const height)
{
int const ip = pos.x+pos.width;
//checking if all cells are 0's
for (int i=pos.x; i<ip; i++)
{
if (memchr(bin+i*height+pos.y, '\1', pos.height))
return false;
}
return true;
}
bool allocate(char* bin, rectToPack file, placedRect &best, int width, int height)
{
int orientations=2, score=0;
bool foo = false;
if (file.width==file.height)
orientations=1;
for (int i=0; i<orientations; i++) {
if (i==1) //rotate file
swap(file.width, file.height);
int fWidth = file.width, fHeight = file.height,
wBoundary = width-fWidth+1, hBoundary = height-fHeight+1;
//find the best position
for (int j=0; j<wBoundary; j++) {
for (int k=0; k<hBoundary; k++) {
if (!bin[j*height+k]) {
placedRect pos;
pos.x=j;
pos.width=fWidth;
pos.y=k;
pos.height=fHeight;
if (fits(bin, pos, height)) {
int scorebar = scores(bin, pos, width, height);
if (scorebar>score) {
score=scorebar;
best=pos;
foo=true;
}
}
}
}
}
if (i==1) //rotate back
swap(file.width, file.height);
}
return foo;
}
bool packs(rectToPack files[], int n, int area, int div)
{
int width;
if (!(width = area/div)) return false;
char* bin, * layout;
bin = new (nothrow) char[area];
layout = new (nothrow) char[area];
if (bin == 0 || layout == 0) {
cout << "Error: " << area << " bytes could not be allocated";
return false;
}
memset(bin, '\0', area);
memset(layout, ' ', area);
placedRect best;
//try to place
for (int i=0; i<n; i++) {
if (allocate(bin, files[i], best, width, div)) {
place(bin, best, div, layout);
} else {
delete[] bin;
delete[] layout;
return false;
}
}
print_layout(layout, width, div);
delete[] layout;
delete[] bin;
return true;
}
bool is_enough(rectToPack files[], int n, int area, int maxw, int maxh)
{
int div = maxh - 1;
div = find_next_divisor(area, div);
if (div==0 || area/div<maxw) {
return false;
}
//try to pack
while (!packs(files, n, area, div)) {
div = find_next_divisor(area, div);
if (div == 0) {
return false;
}
}
return true;
}
int main (int argc, char * const argv[]) {
int n;
cin >> n;
if (n>0) {
rectToPack* files;
files = new (nothrow) rectToPack[n];
if (files == 0) {
cout << "Error: " << n*4 << " bytes could not be allocated";
return false;
}
int maxHeight=0, maxWidth=0, totalArea=0;
//reading input to files, calculating areas and weights, max width and height
for (int i = 0; i < n; i++) {
cin >> files[i].width >> files[i].height;
if (files[i].width < files[i].height)
swap(files[i].width, files[i].height);
if (files[i].width > maxWidth)
maxWidth=files[i].width;
if (files[i].height > maxHeight)
maxHeight=files[i].height;
int perimeter = 2*(files[i].width + files[i].height);
files[i].area = files[i].width * files[i].height;
totalArea+=files[i].area;
files[i].weight = sqrt(files[i].area)*perimeter;
}
qsort(files, n, sizeof(*files), compare_weights);
int area = totalArea;
while (true)
{
if (is_enough(files, n, area, maxWidth, maxHeight)) {
cout <<area;
return 0;
} else if (area > 2*totalArea) {
cout << "-1\n";
return 0;
} else{
area++;
}
}
delete[] files;
} else {
cout << "-1\n";
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment