Merge pull request #2 from FOSSEE/develop

Develop

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