diff options
Diffstat (limited to 'pcbnew/autorouter/rect_placement')
| -rw-r--r-- | pcbnew/autorouter/rect_placement/RectanglePlacement.txt | 38 | ||||
| -rw-r--r-- | pcbnew/autorouter/rect_placement/rect_placement.cpp | 259 | ||||
| -rw-r--r-- | pcbnew/autorouter/rect_placement/rect_placement.h | 104 |
3 files changed, 401 insertions, 0 deletions
diff --git a/pcbnew/autorouter/rect_placement/RectanglePlacement.txt b/pcbnew/autorouter/rect_placement/RectanglePlacement.txt new file mode 100644 index 0000000..cecbf2e --- /dev/null +++ b/pcbnew/autorouter/rect_placement/RectanglePlacement.txt @@ -0,0 +1,38 @@ +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 in a different way +than power of two. It just happens that power of 2 is very convenient for +graphics hardware textures. + +I'd be interested in hearing of other approaches to this problem. Make sure +to post them on http://www.flipcode.com + +See also +http://www.flipcode.com/archives/Rectangle_Placement.shtml +http://kossovsky.net/index.php/2009/07/cshar-rectangle-packing diff --git a/pcbnew/autorouter/rect_placement/rect_placement.cpp b/pcbnew/autorouter/rect_placement/rect_placement.cpp new file mode 100644 index 0000000..f562c2b --- /dev/null +++ b/pcbnew/autorouter/rect_placement/rect_placement.cpp @@ -0,0 +1,259 @@ +// ---------------------------------------------------------------------------------------- +// 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; +} diff --git a/pcbnew/autorouter/rect_placement/rect_placement.h b/pcbnew/autorouter/rect_placement/rect_placement.h new file mode 100644 index 0000000..b89b538 --- /dev/null +++ b/pcbnew/autorouter/rect_placement/rect_placement.h @@ -0,0 +1,104 @@ +// -------------------------------------------------------------------------------- +// Name : rect_placement.h +// Description : A class that allocates subrectangles into power-of-2 rectangles +// (C) Copyright 2000-2002 by Javier Arevalo +// This code is free to use and modify for all purposes +// -------------------------------------------------------------------------------- + +/** + * @file rect_placement.h + */ + +#ifndef _RECT_PLACEMENT_H_ +#define _RECT_PLACEMENT_H_ + +#include <vector> + +// -------------------------------------------------------------------------------- +// -------------------------------------------------------------------------------- + +class CRectPlacement +{ +public: + + // Helper classes + struct TPos + { + int x, y; + + TPos() : x( 0 ), y( 0 ) { } + TPos( int _x, int _y ) : x( _x ), y( _y ) { } + + bool operator ==( const TPos& p ) const { return x == p.x && y == p.y; } + }; + + struct TRect : public TPos + { + int w, h; + + TRect() : w( 0 ), h( 0 ) { } + TRect( int _x, int _y, int _w, int _h ) : TPos( _x, _y ), w( _w > 0 ? _w : 0 ), h( + _h > 0 ? _h : 0 ) { } + + bool Contains( const TPos& p ) const + { + return p.x >= x && p.y >= y && p.x < (x + w) && p.y < (y + h); + } + bool Contains( const TRect& r ) const + { + return r.x >= x && r.y >= y && + (r.x + r.w) <= (x + w) && (r.y + r.h) <= (y + h); + } + bool Intersects( const TRect& r ) const + { + return w > 0 && h > 0 && r.w > 0 && r.h > 0 + && ( (r.x + r.w) > x && r.x < (x + w) && (r.y + r.h) > y && r.y < (y + h) ); + } + + // static bool Greater(const TRect &a, const TRect &b) + // { return a.w*a.h > b.w*b.h; } + // Greater rect area. Not as good as the next heuristic: + // Greater size in at least one dim. + static bool Greater( const TRect& a, const TRect& b ) + { + return (a.w > b.w && a.w > b.h) || (a.h > b.w && a.h > b.h); + } + }; + + // --------------------- + + typedef std::vector<TPos> CPosArray; + typedef std::vector<TRect> CRectArray; + + // --------------------- + + CRectPlacement() { Init(); } + ~CRectPlacement() { End(); } + + void Init( int w = 1, int h = 1 ); + void End(); + + bool IsOk() const { return m_size.w > 0; } + + int GetW() const { return m_size.w; } + int GetH() const { return m_size.h; } + double GetArea() const { return m_area; } + double GetTotalArea() const { return (double)m_size.w * m_size.h; } + + bool AddAtEmptySpotAutoGrow( TRect* pRect, int maxW, int maxH ); + +private: + TRect m_size; + CRectArray m_vRects; + CPosArray m_vPositions; + double m_area; + + // --------------------- + + bool IsFree( const TRect& r ) const; + void AddPosition( const TPos& p ); + void AddRect( const TRect& r ); + bool AddAtEmptySpot( TRect& r ); +}; + +#endif // _RECT_PLACEMENT_H_ |