Rudimentary tree packing class. Mainly intended for use with packing images for use in texture atlases. Uses pointers, so it's inherently evil.

binpack.cc

// binpack.cc -- Noel Cower -- Public Domain

#include "binpack.hh"

namespace snow
{

binpack_t::binpack_t(const recti_t &frame, binpack_t *right, binpack_t *bottom) :
  pack_right_(right), pack_bottom_(bottom), frame_(frame), loaded_(false)
{}

binpack_t::binpack_t(const recti_t &frame) :
  pack_right_(nullptr), pack_bottom_(nullptr), frame_(frame), loaded_(false)
{}

binpack_t::~binpack_t()
{
  if (pack_right_) delete pack_right_;
  if (pack_bottom_) delete pack_bottom_;
}

auto binpack_t::find_unused_bin(const dimensi_t &size) -> binpack_t*
{
  const int f_width = frame_.size.width;
  const int f_height = frame_.size.height;

  if (loaded_ || f_width < size.width || f_height < size.height) {
    binpack_t *result = nullptr;

    if (pack_right_ && pack_bottom_ && ! (pack_bottom_->loaded() || pack_right_->loaded())) {
      int delta, opposite;

      if (size.width >= size.height) {
        delta = pack_bottom_->dimens().width - size.width;
        opposite = pack_right_->dimens().width;
      } else {
        delta = pack_bottom_->dimens().height - size.height;
        opposite = pack_right_->dimens().height;
      }

      const bool bottom_first = (0 < delta && delta < opposite);


      if (! (result = (bottom_first ? pack_bottom_ : pack_right_)->find_unused_bin(size)))
        result = (bottom_first ? pack_right_ : pack_bottom_)->find_unused_bin(size);
    } else { // pack_right_ && pack_bottom_ && ...
      if (pack_right_)
        result = pack_right_->find_unused_bin(size);
      if ( ! result && pack_bottom_)
        result = pack_bottom_->find_unused_bin(size);
    } // pack_right_ && pack_bottom_ && ...

    return result;
  } // loaded_ || f_width < size.width || ...

  if (loaded_ && pack_right_ && pack_bottom_) {
    return nullptr;
  }

  if (pack_right_ || pack_bottom_) {
    const int bottom_delta = f_height - size.height;
    const int right_delta = f_width - size.width;

    if (bottom_delta > 0 && ! pack_bottom_) {
      pack_bottom_ = new binpack_t(make_rect(0, 0, f_width, bottom_delta), nullptr, pack_bottom_);
    }

    if (right_delta > 0 && ! pack_right_) {
      pack_right_ = new binpack_t(make_rect(0, 0, right_delta, f_height), pack_right_, nullptr);
    }
  } else { // pack_right_ || pack_bottom_
    const int width_delta = f_width - size.width;
    const int height_delta = f_height - size.height;
    recti_t right_rect = {0}, bottom_rect = {0};

    if (height_delta < width_delta) {
      right_rect.size = make_dimens(width_delta, size.height);
      bottom_rect.size = make_dimens(f_width, height_delta);
    } else {
      right_rect.size = make_dimens(width_delta, f_height);
      bottom_rect.size = make_dimens(size.width, height_delta);
    }

    pack_right_ = new binpack_t(right_rect);
    pack_bottom_ = new binpack_t(bottom_rect);
  } // pack_right_ || pack_bottom_

  if (pack_right_)
    pack_right_->frame_.origin = make_point(frame_.origin.x + size.width, frame_.origin.y);

  if (pack_bottom_)
    pack_bottom_->frame_.origin = make_point(frame_.origin.x, frame_.origin.y + size.height);

  frame_.size = size;
  loaded_ = true;

  return this;
}

void binpack_t::merge_empty_recursive()
{
  const int f_width = frame_.size.width;
  const int f_height = frame_.size.height;

  if (pack_right_)
    pack_right_->merge_empty_recursive();

  if (pack_bottom_)
    pack_bottom_->merge_empty_recursive();

  if (pack_right_) {
    if ( ! pack_right_->loaded() && pack_right_->dimens().height == f_height) {
      frame_.size.width += pack_right_->dimens().width;
      binpack_t *old_right = pack_right_;
      pack_right_ = pack_right_->pack_right_;
      delete old_right;
    }

    if (pack_bottom_ && ! pack_bottom_->loaded() && pack_bottom_->dimens().width == f_width) {
      frame_.size.height += pack_bottom_->dimens().height;
      binpack_t *old_bottom = pack_bottom_;
      pack_bottom_ = pack_bottom_->pack_bottom_;
      delete old_bottom;
    }
  }

  if (pack_bottom_) {
    if ( ! pack_bottom_->loaded() && pack_bottom_->dimens().width == f_width) {
      frame_.size.height += pack_bottom_->dimens().height;
      binpack_t *old_bottom = pack_bottom_;
      pack_bottom_ = pack_bottom_->pack_bottom_;
      delete old_bottom;
    }

    if (pack_right_ && ! pack_right_->loaded() && pack_right_->dimens().height == f_height) {
      frame_.size.width += pack_right_->dimens().width;
      binpack_t *old_right = pack_right_;
      pack_right_ = pack_right_->pack_right_;
      delete old_right;
    }
  }
}

void binpack_t::unload()
{
  loaded_ = false;
  merge_empty_recursive();
}

auto binpack_t::loaded() const -> bool
{
  return loaded_;
}

auto binpack_t::origin() const -> pointi_t
{
  return frame_.origin;
}

auto binpack_t::dimens() const -> dimensi_t
{
  return frame_.size;
}

auto binpack_t::frame() const -> recti_t
{
  return frame_;
}

}

binpack.hh

// binpack.hh -- Noel Cower -- Public Domain

#ifndef __SNOW_BINPACK_HH__
#define __SNOW_BINPACK_HH__

#include "types_2d.hh"

namespace snow
{

class binpack_t
{
private:
  binpack_t *pack_right_;
  binpack_t *pack_bottom_;

  recti_t frame_;
  bool loaded_;

  binpack_t(const recti_t &frame, binpack_t *right, binpack_t *bottom);

public:
  // This is the constructor you want.
  binpack_t(const recti_t &frame);
  virtual ~binpack_t();

  virtual auto find_unused_bin(const dimensi_t &size) -> binpack_t*;
  virtual void merge_empty_recursive();
  // After calling unload(), one should discard any pointers to the binpack_t
  // it's called from.
  virtual void unload();

  virtual auto loaded() const -> bool;
  virtual auto origin() const -> pointi_t;
  virtual auto dimens() const -> dimensi_t;
  virtual auto frame() const -> recti_t;
};

}

#endif /* end __SNOW_BINPACK_HH__ include guard */

types_2d.hh

// types_2d.hh -- Noel Cower -- Public Domain

#ifndef __TYPES_2D_HH__
#define __TYPES_2D_HH__

#include <iostream>
#include <algorithm>

namespace snow
{

template <class T>
struct rect_t;

template <class T>
struct dimens_t;

template <class T = int>
struct point_t
{
  T x;
  T y;

  auto max(const point_t &other) const -> point_t
  {
    return {
      std::max(x, other.x),
      std::max(y, other.y)
    };
  }

  auto min(const point_t &other) const -> point_t
  {
    return {
      std::min(x, other.x),
      std::min(y, other.y)
    };
  }

  operator rect_t<T> () const
  {
    return {
      *this,
      { T(), T() }
    };
  }
};

template <class T = int>
struct dimens_t
{
  T width;
  T height;

  auto max(const dimens_t &other) const -> dimens_t
  {
    return {
      std::max(width, other.width),
      std::max(height, other.height)
    };
  }

  auto min(const dimens_t &other) const -> dimens_t
  {
    return {
      std::min(width, other.width),
      std::min(height, other.height)
    };
  }

  operator rect_t<T> () const
  {
    return {
      { T(), T(), },
      *this
    };
  }
};

template <class T = int>
struct rect_t
{
  point_t<T> origin;
  dimens_t<T> size;

  auto intersects(const rect_t &other) const   -> bool
  {
    return !(other.right() < left() ||
             other.bottom() < top() ||
             right() < other.left() ||
             bottom() < other.top());
  }

  auto intersection(const rect_t &other) const -> rect_t
  {
    point_t<T> point_max = origin.max(other.origin);
    return {
      point_max,
      {
        std::max(T(), std::min(right(), other.right()) - point_max.x),
        std::max(T(), std::min(top(), other.top()) - point_max.y)
      }
    };
  }

  auto padded(T horizontal, T vertical) const -> rect_t
  {
    return {
      {
        origin.x - horizontal,
        origin.y - vertical
      },
      {
        size.width + horizontal * 2,
        size.height + vertical * 2
      }
    };
  }

  auto pad(T horizontal, T vertical) -> rect_t&
  {
    origin.x -= horizontal;
    origin.y -= vertical;
    size.width += horizontal * 2;
    size.height += vertical * 2;
    return *this;
  }

  auto right() const  -> T
  {
    if (size.width < T())
      return origin.x;
    else
      return origin.x + size.width;
  }

  auto left() const   -> T
  {
    if (size.width < T())
      return origin.x + size.width;
    else
      return origin.x;
  }

  auto top() const    -> T
  {
    if (size.height < T())
      return origin.y;
    else
      return origin.y + size.height;
  }

  auto bottom() const -> T
  {
    if (size.height < T())
      return origin.y + size.height;
    else
      return origin.y;
  }

  auto contains(const point_t<T> &point) const -> bool
  {
    return (left() <= point.x && point.x <= right() &&
            bottom() <= point.y && point.y <= top());
  }
};

template <class T = int>
auto make_point(T x, T y) -> point_t<T>
{
  return {
    x, y
  };
}

template <class T = int>
auto make_dimens(T width, T height) -> dimens_t<T>
{
  return {
    width, height
  };
}

template <class T = int>
auto make_rect(T x, T y, T width, T height) -> rect_t<T>
{
  return {
    { x, y },
    { width, height }
  };
}

template <class T>
std::ostream &operator << (std::ostream &out, const point_t<T> &in)
{
  return out << "{ x: " << in.x << ", y: " << in.y << " }";
}

template <class T>
std::ostream &operator << (std::ostream &out, const dimens_t<T> &in)
{
  return out << "{ width: " << in.width << ", height: " << in.height << " }";
}

template <class T>
std::ostream &operator << (std::ostream &out, const rect_t<T> &in)
{
  return out << "{ origin: " << in.origin << ", size: " << in.size << " }";
}

typedef point_t<float> pointf_t;
typedef point_t<double> pointd_t;
typedef point_t<long> pointl_t;
typedef point_t<int> pointi_t;

typedef dimens_t<float> dimensf_t;
typedef dimens_t<double> dimensd_t;
typedef dimens_t<long> dimensl_t;
typedef dimens_t<int> dimensi_t;

typedef rect_t<float> rectf_t;
typedef rect_t<double> rectd_t;
typedef rect_t<long> rectl_t;
typedef rect_t<int> recti_t;

}

#endif /* end __TYPES_2D_HH__ include guard */