Thread: Center-weighted bin packing algorithm?

  1. #1
    Registered User MathFan's Avatar
    Join Date
    Apr 2002
    Posts
    190

    Center-weighted bin packing algorithm?

    Hello, good people!

    I cannot for the life of me Figure out what type of rectangle packing algorithm is used for generating such word frequency clouds as this one:

    http://cfftjresources.wikispaces.com...ord-cloud1.jpg

    Does anyone have a clue? Any hints are much appreciated!
    Last edited by MathFan; 06-23-2011 at 05:03 AM. Reason: I'm sorry, the title should have been more specific - RECTANGLE packing algorithm, not BIN packing
    The OS requirements were Windows Vista Ultimate or better, so we used Linux.

  2. #2
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    You will want to read this:
    Fast optimizing rectangle packing algorithm for building CSS sprites - CodeProject

    Basically all words start by becoming individual rectangles of varying sizes, according to your word cloud algorithm.
    You then pack them following some appropriate method like the one described by Richard E. Korf. (here, pdf link)

    As far as generating the images, you can use a library like imagick for the web, or whatever is more appropriate for your programming language.

    EDIT: Hey, and welcome back.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  3. #3
    Registered User MathFan's Avatar
    Join Date
    Apr 2002
    Posts
    190
    Thank you! Glad to be back! It's been literally ages since my last post. I do have to admit to being more than slightly embarassed of my nick, avatar and sig...

    I will most probably use libcairo for my graphical needs. If pressed I could write to a PostScript file. I will be using C++ or Java for this btw.

    I am far more interested in the algorithmical basis of this. I have taken a look at both of your links - thanks! However, as far as I can see most of the word clouds I find have the largest rectangles gravitating towards the middle, while the smaller ones are more or less evenly distributed towards the edges. Is this how the algorithm works intrinsically? Or do I have to use some kind of tweaks?

    What if I want to shape my cloud as a drop or a circle or whatever? Any advice?
    The OS requirements were Windows Vista Ultimate or better, so we used Linux.

  4. #4
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Yup. Your post title makes it clear, but I didn't notice.

    The method described gives you a nice seemingly random distribution resembling the image you posted. The trick, if I'm not mistaken, is to look at the outer rectangle as extending the general properties of the smaller rectangles you want to pack. Being that these are images containing a word, you will want to make a slight modification to the steps on that Code Project article and sort your rectangles by width instead of height -- and starting with an outer rectangle that is as wide as the widest rectangle (because all your images to be packed will tend to be wider than they are taller).

    Now -- and this is speculation at this point and hopefully someone will correct me if I'm wrong -- but I believe you could, during the process described for packing the rectangles, alternatively add more space first to the left then to the right (and to the top and then to the bottom) moving the already parked rectangles up and down, left and right, in the opposite direction according to the algorithm rules. This would result in a final image that would tend (but not always) to pack the largest rectangles at the center, since they are sorted by size as you insert them, giving you your desired look.

    As for packing inside a circle or oval shape, the principle is exactly the same I believe. But with a tweak. You consider your outer rectangle, the rectangle that encloses your circle or oval. But when packing you take into account the 4 no-go zones that are the areas between the oval and the enclosing rectangle. In the end you will always be packing inside a rectangle, but -- provinding you have enough shapes to pack -- you'll come up with a circle or oval shaped cloud.
    Last edited by Mario F.; 06-23-2011 at 07:16 AM.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  5. #5
    Registered User MathFan's Avatar
    Join Date
    Apr 2002
    Posts
    190
    Thank you for your explanation - I will try out your suggestions as soon as I get the chance!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 'lazy / weighted' sort algorithm
    By tsnider in forum Tech Board
    Replies: 4
    Last Post: 05-11-2011, 02:24 PM
  2. center the GetOpenFileName
    By Joelito in forum Windows Programming
    Replies: 4
    Last Post: 04-15-2005, 11:26 AM
  3. Help - Weighted-Average Triangulation Algorithm
    By Geolingo in forum C++ Programming
    Replies: 0
    Last Post: 04-03-2004, 11:42 PM
  4. weighted links
    By WDT in forum C++ Programming
    Replies: 3
    Last Post: 02-29-2004, 09:29 AM

Tags for this Thread