Programming Fun Challenge 5: Polygon Packing (Winning Solution)

pfc5.cpp

// 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;
}