// ----------------------------------------------------------------------------------------
// Name : rect_placement.cpp
// Description : A class that fits subrectangles into a power-of-2 rectangle
// (C) Copyright 2000-2002 by Javier Arevalo
// This code is free to use and modify for all purposes
// ----------------------------------------------------------------------------------------
/*
* You have a bunch of rectangular pieces. You need to arrange them in a
* rectangular surface so that they don't overlap, keeping the total area of the
* rectangle as small as possible. This is fairly common when arranging characters
* in a bitmapped font, lightmaps for a 3D engine, and I guess other situations as
* well.
*
* The idea of this algorithm is that, as we add rectangles, we can pre-select
* "interesting" places where we can try to add the next rectangles. For optimal
* results, the rectangles should be added in order. I initially tried using area
* as a sorting criteria, but it didn't work well with very tall or very flat
* rectangles. I then tried using the longest dimension as a selector, and it
* worked much better. So much for intuition...
*
* These "interesting" places are just to the right and just below the currently
* added rectangle. The first rectangle, obviously, goes at the top left, the next
* one would go either to the right or below this one, and so on. It is a weird way
* to do it, but it seems to work very nicely.
*
* The way we search here is fairly brute-force, the fact being that for most off-
* line purposes the performance seems more than adequate. I have generated a
* japanese font with around 8500 characters and all the time was spent generating
* the bitmaps.
*
* Also, for all we care, we could grow the parent rectangle.
*
* I'd be interested in hearing of other approaches to this problem. Make sure
* to post them on http://www.flipcode.com
*/
#include "rect_placement.h"
// --------------------------------------------------------------------------------
// Name :
// Description :
// --------------------------------------------------------------------------------
void CRectPlacement::Init( int w, int h )
{
End();
m_size = TRect( 0, 0, w, h );
m_vPositions.push_back( TPos( 0, 0 ) );
m_area = 0;
}
// --------------------------------------------------------------------------------
// Name :
// Description :
// --------------------------------------------------------------------------------
void CRectPlacement::End()
{
m_vPositions.clear();
m_vRects.clear();
m_size.w = 0;
}
// --------------------------------------------------------------------------------
// Name : IsFree
// Description : Check if the given rectangle is partially or totally used
// --------------------------------------------------------------------------------
bool CRectPlacement::IsFree( const TRect& r ) const
{
if( !m_size.Contains( r ) )
return false;
for( CRectArray::const_iterator it = m_vRects.begin();
it != m_vRects.end(); ++it )
{
if( it->Intersects( r ) )
return false;
}
return true;
}
// --------------------------------------------------------------------------------
// Name : AddPosition
// Description : Add new anchor point
// --------------------------------------------------------------------------------
void CRectPlacement::AddPosition( const TPos& p )
{
// Try to insert anchor as close as possible to the top left corner
// So it will be tried first
bool bFound = false;
CPosArray::iterator it;
for( it = m_vPositions.begin();
!bFound && it != m_vPositions.end();
++it )
{
if( p.x + p.y < it->x + it->y )
bFound = true;
}
if( bFound )
m_vPositions.insert( it, p );
else
m_vPositions.push_back( p );
}
// --------------------------------------------------------------------------------
// Name : AddRect
// Description : Add the given rect and updates anchor points
// --------------------------------------------------------------------------------
void CRectPlacement::AddRect( const TRect& r )
{
m_vRects.push_back( r );
m_area += r.w * r.h;
// Add two new anchor points
AddPosition( TPos( r.x, r.y + r.h ) );
AddPosition( TPos( r.x + r.w, r.y ) );
}
// --------------------------------------------------------------------------------
// Name : AddAtEmptySpot
// Description : Add the given rectangle
// --------------------------------------------------------------------------------
bool CRectPlacement::AddAtEmptySpot( TRect& r )
{
// Find a valid spot among available anchors.
bool bFound = false;
CPosArray::iterator it;
for( it = m_vPositions.begin();
!bFound && it != m_vPositions.end();
++it )
{
TRect Rect( it->x, it->y, r.w, r.h );
if( IsFree( Rect ) )
{
r = Rect;
bFound = true;
break; // Don't let the loop increase the iterator.
}
}
if( bFound )
{
int x, y;
// Remove the used anchor point
m_vPositions.erase( it );
// Sometimes, anchors end up displaced from the optimal position
// due to irregular sizes of the subrects.
// So, try to adjut it up & left as much as possible.
for( x = 1; x <= r.x; x++ )
{
if( !IsFree( TRect( r.x - x, r.y, r.w, r.h ) ) )
break;
}
for( y = 1; y <= r.y; y++ )
{
if( !IsFree( TRect( r.x, r.y - y, r.w, r.h ) ) )
break;
}
if( y > x )
r.y -= y - 1;
else
r.x -= x - 1;
AddRect( r );
}
return bFound;
}
#include <stdio.h>
// --------------------------------------------------------------------------------
// Name : AddAtEmptySpotAutoGrow
// Description : Add a rectangle of the given size, growing our area if needed
// Area grows only until the max given.
// Returns the placement of the rect in the rect's x,y coords
// --------------------------------------------------------------------------------
bool CRectPlacement::AddAtEmptySpotAutoGrow( TRect* pRect, int maxW, int maxH )
{
double growing_factor = 1.2; // Must be > 1.0, and event > 1.1 for fast optimization
#define GROW(x) ((x * growing_factor) + 1)
if( pRect->w <= 0 )
return true;
int orgW = m_size.w;
int orgH = m_size.h;
// Try to add it in the existing space
while( !AddAtEmptySpot( *pRect ) )
{
int pw = m_size.w;
int ph = m_size.h;
// Sanity check - if area is complete.
if( pw >= maxW && ph >= maxH )
{
m_size.w = orgW;
m_size.h = orgH;
return false;
}
// Try growing the smallest dim
if( pw < maxW && ( pw < ph || ( (pw == ph) && (pRect->w >= pRect->h) ) ) )
m_size.w = GROW( pw );
else
m_size.h = GROW( ph );
if( AddAtEmptySpot( *pRect ) )
break;
// Try growing the other dim instead
if( pw != m_size.w )
{
m_size.w = pw;
if( ph < maxW )
m_size.h = GROW( ph );
}
else
{
m_size.h = ph;
if( pw < maxW )
m_size.w = GROW( pw );
}
if( pw != m_size.w || ph != m_size.h )
if( AddAtEmptySpot( *pRect ) )
break;
// Grow both if possible, and reloop.
m_size.w = pw;
m_size.h = ph;
if( pw < maxW )
m_size.w = GROW( pw );
if( ph < maxH )
m_size.h = GROW( ph );
}
return true;
}