Arrange letters of a sentence in a minimum area?

Question

I'm going to write a program that rearranges letters of a sentence in a minimum area. The tool that I'm going to write this app is not important. The problem is that I nearly have no idea how I can do this.

I want something like this :

Is there any algorithm to sort some surfaces (let's suppose each letter a polygon surface) in a minimum area?

Answer 1

In this paper you can find insights of Wordle, a tool to do beautiful tag clouds. It does a randomized greedy algorithm approximation of the bin packing problem.

Answer 2

Its not easy at all... it is related to the "Bin Packing Problem" which is proven NP-HARD.
Additionally, your problem involves non-rectangular objects so it's a bit harder but not by magnitude.

you should go for an Optimization algorithm approach like Genetic Algorithms or such...

Google for "Bin Packing 2D" will result in quite a few helpful links and articles.

Answer 3

My approch for such an algorithm would be a genetic one.This would be a sample data structure sample in Java.

public class Individual{
 char letter;
 double x;
 double y;
 double rotation;
}

public class Population{
 private Individual[] individuals;

 public Population(String s) {
  individuals = new Individual[s.length()];  
  for(int i = 0; i < s.length(); i++ {
   Individual individual = new Individual();
   individual.letter = s.charAt(i);
   // set random x, y, and rotation;
   individuals[i] = individual; 
  } 
 }
 // Calculate Fitness: (1/Totalspace needed ) - Overlapping Space
 // Envolve Population
}