Re: Allocation of 2D space

On Tue, Aug 11, 2009 at 8:41 PM, Brian Meidell <[email protected]>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
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list