Skip to content

Instantly share code, notes, and snippets.

@codemonkey-uk
Created November 6, 2014 22:03
Show Gist options
  • Save codemonkey-uk/4c2ef01c3849be089dda to your computer and use it in GitHub Desktop.
Save codemonkey-uk/4c2ef01c3849be089dda to your computer and use it in GitHub Desktop.
Programming Fun Challenge 5: Polygon Packing (Winning Solution)
// pfc5.cpp v2 (c) T.Frogley 2002
// Programming Fun Challenge 5: Polygon Packing
// http://www.kuro5hin.org/story/2002/5/24/171054/160
//
// My solution does not provide an optimal packing,
// instead it produces a reasonable packing,
// and very good throughput, scaling very well,
// packing thousands of polys in sub-minute times,
// rather than hundreds in hours.
//
// possible improvements include:
// * look up tables for sin/cos
// * rotating calipers or similar for finding minimal AABB
//
// fatal flaw: Effectivness of placement is highly input data order dependant
#ifdef _MSC_VER
//identifier was truncated to '255' characters in the browser information
#pragma warning (disable : 4786)
#endif
//IO headers
#include <iostream>
#include <fstream>
//STL containers
#include <deque>
#include <vector>
#include <string>
//algorithms, etc
#include <algorithm>
#include <cmath>
//debug code
#include <cassert>
using namespace std;
// Some MSVC++ / Visual Studio 6 fixes
#ifdef _MSC_VER
//min & max should be in <algorithm>
//see: http://www.sgi.com/Technology/STL/max.html
//unfortunatly the Microsoft compiler\headers arn't standard compliant
//see: http://x42.deja.com/getdoc.xp?AN=520752890
//thus:
#ifdef max
#undef max
#endif
#ifdef min
#undef min
#endif
template<class T> inline
const T& max(const T& a, const T& b)
{ return (a>b)?a:b; }
template<class T> inline
const T& min(const T& a, const T& b)
{ return (a<b)?a:b; }
#endif
//alternative getline function
inline string getline(istream& i)
{
string s;
while(i.good()){
char c;
i.get(c);
if (i.gcount()==1 && c!='\n')
s += c;
else break;
}
return s;
}
// alternative for_each function
// operates on a whole container
template <typename C, typename F>
void for_each(C& container, F& fn){
for_each( container.begin(), container.end(), fn);
}
template <typename C, typename F>
void for_each(const C& container, const F& fn){
for_each( container.begin(), container.end(), fn);
}
//print function object type template
//untility class, lets you print types using for_each
template< typename T >
class Print{
public:
Print(ostream& o) : out(o)
{ }
void operator()( const T& t ){
out << t;
}
private:
ostream& out;
};
// Split helper function
// makes a vector of strings from one string,
// splitting at (and excluding) delimiter "token"
inline vector<string> Split( const string& s, const char token )
{
vector<string> result;
string::const_iterator i = s.begin();
string::const_iterator j = s.begin();
const string::const_iterator e = s.end();
while(i!=e){
while(i!=e && *i++!=token);
result.push_back( string( j, i ) );
j = i;
}
return result;
}
//use doubles to maintain reasonable accuracy
typedef double scalar;
const scalar PI = 3.1415926535898;
//Point type
struct Point{
scalar x;
scalar y;
//default construct
Point( scalar _x=0, scalar _y=0 ) : x(_x), y(_y)
{ }
//construct from string def
Point( const string& pointdef ){
vector<string> s = Split(pointdef,',');
if (s.size()!=2) throw exception();
x=atof(s[0].c_str());
y=atof(s[1].c_str());
}
//move a point along a vector
Point& operator+=( const Point& vec ){
x += vec.x;
y += vec.y;
return *this;
}
//rotate a point around a pivot
void Rotate( const scalar rot, const Point& pivot ){
x -= pivot.x;
y -= pivot.y;
const scalar x2 = cos(rot)*x - sin(rot)*y;
const scalar y2 = sin(rot)*x + cos(rot)*y;
x = x2 + pivot.x;
y = y2 + pivot.y;
}
//functor for moving vectors
class MoveFnObj{
public:
MoveFnObj(const Point& v):vec(v)
{ }
void operator()(Point& p)const{
p += vec;
}
private:
const Point& vec;
};
//functor for rotating vectors
class RotFnObj{
public:
RotFnObj(const scalar r, const Point& p):rot(r),pivot(p)
{ }
void operator()(Point& p)const{
p.Rotate(rot,pivot);
}
private:
const scalar rot;
const Point& pivot;
};
};
// binary subtract operator for Point
// - returns the vector between two points
inline Point operator-(const Point& a, const Point& b){
return Point(a.x-b.x, a.y-b.y);
}
//Axis Aligned Bounding Box
struct AABB {
//default construct, invalid state (inverted unit square),
//must use assignment before any other operation
AABB():
x1(0),x2(-1),y1(0),y2(-1)
{ }
//ctor
AABB(const Point& p) : x1(p.x),x2(p.x),y1(p.y),y2(p.y)
{ }
//assignment
AABB& operator=(const Point& p){
x1 = x2 = p.x;
y1 = y2 = p.y;
return *this;
}
// stream operator - in this case "adds" a point to the aabb
// that is, expand the aabb to fit the point
AABB& operator<<( const Point& p){
assert(x2>=x1 && y2>=y1);
if (p.x<x1) x1=p.x;
if (p.x>x2) x2=p.x;
if (p.y<y1) y1=p.y;
if (p.y>y2) y2=p.y;
return *this;
}
// stream operator - in this case "adds" a aabb to the aabb
// that is, expand the aabb to fit the aabb
AABB& operator<<( const AABB& other ){
assert(x2>=x1 && y2>=y1);
*this << other.BottomLeft();
*this << other.BottomRight();
*this << other.TopLeft();
*this << other.TopRight();
return *this;
}
//compare sizes of AABBs
bool CanContain( const AABB& other )const{
assert(x2>=x1 && y2>=y1);
return (GetWidth()>=other.GetWidth() && GetHeight()>=other.GetHeight());
}
//move by vector
void Move( const Point& vec ){
assert(x2>=x1 && y2>=y1);
x1 += vec.x;
y1 += vec.y;
x2 += vec.x;
y2 += vec.y;
}
// some helper functions:
inline scalar GetWidth()const{
assert(x2>=x1);
return (x2-x1);
}
inline scalar GetHeight()const{
assert(y2>=y1);
return (y2-y1);
}
inline scalar GetArea()const{
return GetWidth()*GetHeight();
}
Point BottomLeft()const{
assert(x2>=x1 && y2>=y1);
return Point(x1,y1);
}
Point BottomRight()const{
assert(x2>=x1 && y2>=y1);
return Point(x2,y1);
}
Point TopLeft()const{
assert(x2>=x1 && y2>=y1);
return Point(x1,y2);
}
Point TopRight()const{
assert(x2>=x1 && y2>=y1);
return Point(x2,y2);
}
Point GetMidPoint()const{
assert(x2>=x1 && y2>=y1);
return Point(x1+(x2-x1)/2,y1+(y2-y1)/2);
}
//functor for adding points to the poly
class CanContainFnObj{
public:
CanContainFnObj( const AABB& other ):my_aabb(other)
{ }
bool operator()( const AABB& p )const{
return p.CanContain(my_aabb);
}
private:
const AABB& my_aabb;
};
//functor for adding points to the poly
class AddPointFnObj{
public:
AddPointFnObj( AABB& to_poly ):my_aabb(to_poly)
{ }
void operator()(const Point& p){
my_aabb << p;
}
private:
AABB& my_aabb;
};
private:
scalar x1,y1,x2,y2;
};
//Poly, points, plus AABB
class Poly{
public:
//construct from string
Poly(const string& polydef){
vector<string> points = Split( polydef, ' ' );
AddPointFnObj fn(*this);
for_each( points, fn );
}
//member function ads point to poly
void AddPoint( const Point& p ){
if (points.empty()){
bounds = p;
}
else{
bounds << p;
}
points.push_back( p );
}
//moves the origin of the AABB to the Point
void MoveTo( const Point& p ){
//movement vector
Point vec = p - bounds.BottomLeft();
//move aabb
bounds.Move(vec);
//move all points in poly
Point::MoveFnObj fn(vec);
for_each( points, fn );
}
//rotate poly around a pivot
void Rotate( const scalar rot, const Point& pivot ){
Point::RotFnObj fn(rot, pivot);
for_each( points, fn );
RecalcBounds();
}
// some helper functions
bool Empty()const {
return points.empty();
}
Point GetMidPoint()const{
return bounds.GetMidPoint();
}
const AABB& GetBounds() const {
return bounds;
}
ostream& Print(ostream& o)const{
::Print<Point> fn(o);
for_each( points, fn );
return o << endl;
}
private:
//axis aligned bounding box
AABB bounds;
//actual points
vector<Point> points;
//best to just recalulate aabb after rotation, helper function:
void RecalcBounds(){
assert( !points.empty() );
bounds = points.front();
AABB::AddPointFnObj fn( bounds );
for_each( points, fn );
}
//functor for adding points to the poly
class AddPointFnObj{
public:
AddPointFnObj(Poly& to_poly):my_poly(to_poly)
{ }
void operator()(const string& point_def){
my_poly.AddPoint( Point( point_def ) );
}
private:
Poly& my_poly;
};
};
// stream out a poly
ostream& operator<<(ostream& o, const Poly& p){
return p.Print(o);
}
// stream out a point
ostream& operator<<(ostream& o, const Point& p){
return o << p.x << "," << p.y << " ";
}
int main(int argv, char** argc)
{
//we'll start with an empty, but valid AABB at 0,0
AABB bounds(Point(0,0));
//and we'll keep track of space inside it as "bins"
typedef deque<AABB> Bins;
Bins bins;
//get the polys from std-in
while(cin.good() && !cin.eof()){
try{
//get the poly
Poly p(getline(cin));
if (!p.Empty()){
//linear search to find rotation out of 16 that minimises AABB
// this code sucks, but I don't have time to implement code
// to construct a convex hull, and do rotating calipers,
Poly temp = p;
scalar prot = 0;
const scalar step = PI/32;
for (scalar r=step;r<=PI/2;r+=step){
Poly b = temp;
b.Rotate(r,b.GetMidPoint());
if (b.GetBounds().GetArea()<p.GetBounds().GetArea()){
p = b;
prot = r;
}
}
//find an empty bin within existing AABB to put poly
Bins::iterator i = find_if(bins.begin(), bins.end(), AABB::CanContainFnObj( p.GetBounds() ) );
//if would not fit in existing bin like so, rotate 90 degrees and try again
if (i==bins.end()){
Poly b = temp;
b.Rotate(prot + PI/2,b.GetMidPoint());
i = find_if(bins.begin(), bins.end(), AABB::CanContainFnObj( b.GetBounds() ) );
if (i!=bins.end()){
p = b;
prot = prot + PI/2;
}
}
//it fitted in existing bin.
if (i!=bins.end()){
// move poly to bin
p.MoveTo(i->BottomLeft());
// create sub bins
AABB newBinA(p.GetBounds().TopLeft()),
newBinB(p.GetBounds().BottomRight());
newBinB << i->TopRight();
newBinA << newBinB.TopLeft();
//remove parent bin, and insert sub bins with nonzero (integer) area
bins.erase(i);
if (newBinA.GetArea()>=1)
bins.push_back( newBinA );
if (newBinB.GetArea()>=1)
bins.push_back( newBinB );
}
// poly does not fit inside main AABB, we will have to glue it to the side
else{
// select 90 rotation of poly that expands the bounds by least
Poly b = temp;
b.Rotate(prot + PI/2,b.GetMidPoint());
if ( min( (bounds.GetWidth()+p.GetBounds().GetWidth()) * max(bounds.GetHeight(), p.GetBounds().GetHeight()) ,
max(bounds.GetWidth(), p.GetBounds().GetWidth()) * (bounds.GetHeight()+p.GetBounds().GetHeight()))
>
min( (bounds.GetWidth()+b.GetBounds().GetWidth()) * max(bounds.GetHeight(), b.GetBounds().GetHeight()) ,
max(bounds.GetWidth(), b.GetBounds().GetWidth()) * (bounds.GetHeight()+b.GetBounds().GetHeight()))){
p = b;
prot = prot + PI/2;
}
//select best edge to glue poly to
if ( (bounds.GetWidth()+p.GetBounds().GetWidth()) * max(bounds.GetHeight(), p.GetBounds().GetHeight()) <
max(bounds.GetWidth(), p.GetBounds().GetWidth()) * (bounds.GetHeight()+p.GetBounds().GetHeight())){
// put the poly on the right edge
p.MoveTo(bounds.BottomRight());
// create new bin
if (p.GetBounds().GetHeight() > bounds.GetHeight()){
AABB newBin(bounds.TopLeft());
newBin << p.GetBounds().TopLeft();
bins.push_back( newBin );
}
else if (bounds.GetHeight() > p.GetBounds().GetHeight()){
AABB newBin(bounds.TopRight());
newBin << p.GetBounds().TopRight();
bins.push_back( newBin );
}
}
else{
// put the poly on the right edge
p.MoveTo(bounds.TopLeft());
// create new bin
if (p.GetBounds().GetWidth() > bounds.GetWidth()){
AABB newBin(p.GetBounds().BottomRight());
newBin << bounds.BottomRight();
bins.push_back( newBin );
}
else if (bounds.GetWidth() > p.GetBounds().GetWidth()){
AABB newBin(p.GetBounds().TopRight());
newBin << bounds.TopRight();
bins.push_back( newBin );
}
}
//expand the global bounds
bounds << p.GetBounds();
}
//were done with this poly now, write it back out
cout << p;
}
}
catch(exception&){
//problem with the IO - quit
break;
}
}
//cerr << (long)(bounds.GetArea()) << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment