Re: [Algorithms] Allocation of 2D space

[James R. <ja...@fu...>]

That's very similar to how I pack font glyphs offline.  Although I don't 
rotate low, wide glyphs to the vertical.

Sort by height and then width and then place in rows across the 
texture.  One thing I do which doesn't make it very suitable for real 
time applications is to scan from the top left of the texture each time 
searching for a space to fit the next glyph.  That way I am usually able 
to fit smaller glyphs in the gaps left between the larger ones and down 
the right side of the texture.

And in my experience it actually turns out to be a reasonably optimal 
algorithm for similarly-sized, not-too-large rectangles.


Sebastian Sylvan wrote:
>
>
> On Tue, Aug 11, 2009 at 8:41 PM, Brian Meidell <br...@ga... 
> <mailto:br...@ga...>> wrote:
>
>     Hi,
>
>     I'm looking for an algorithm to allocate 2d rectangles of different
>     sizes from a larger 2d rectangle (small areas out of a large texture),
>     while wasting as little space as possible without being insanely slow.
>
>     Search terms that yield google results are welcome answers (I tried,
>     but I guess my google-fu proved too weak).
>
>
> "Rectangle packing" is probably a good search phrase.
>
> One simple, quick and reasonably good algorithm (that I can't find the 
> paper for right now), is to first align all the rectangles so their 
> longest axis is pointing along y, then sort them by this height. Then 
> you simply start putting down rectangles left to right until you reach 
> the right edge (you have to guess how wide this is - if you're trying 
> to optimize for "squareness" a binary search can help), and then you 
> go right-to-left underneath that until you're back at the first edge. 
> Then move this last row of rectangles up so that it's as close to the 
> first row as possible. Repeat until you've run out of rectangles.
>
> Hardly optimal, but at least it's simple!
>
>  
>
>      
>
> -- 
> Sebastian Sylvan
> ------------------------------------------------------------------------
>
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day 
> trial. Simplify your report design, integration and deployment - and focus on 
> what you do best, core application coding. Discover what's new with 
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> ------------------------------------------------------------------------
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list