diff options
Diffstat (limited to 'pcbnew/autorouter/rect_placement/RectanglePlacement.txt')
| -rw-r--r-- | pcbnew/autorouter/rect_placement/RectanglePlacement.txt | 38 |
1 files changed, 38 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 |