Disponi le lettere di una frase in un'area minima?

Question

Ho intenzione di scrivere un programma che riorganizza le lettere di una frase in un'area minima. Lo strumento che sto per scrivere questa app non è importante. Il problema è che quasi non ho idea di come posso farlo.

voglio qualcosa di simile:

Esiste un algoritmo per ordinare alcune superfici (supponiamo ogni lettera una superficie poligono) in una superficie minima?

Answer 1

In this paper è possibile trovare approfondimenti di Wordle, uno strumento per creare bellissime nuvole di tag. Fa un'approssimazione dell'algoritmo avido randomizzato del problema dell'imballaggio del contenitore.

Answer 2

Non è affatto facile ... è correlato al "Problema di imballaggio del contenitore" che è dimostrato NP-HARD.
Inoltre, il tuo problema riguarda oggetti non rettangolari quindi è un po 'più difficile ma non di grandezza.

si dovrebbe andare per un approccio algoritmo di ottimizzazione come algoritmi genetici o tali ...

Google per "Bin Packing 2D" si tradurrà in un bel paio di link utili e articoli.

Answer 3

Il mio approcio per un tale algoritmo sarebbe genetico. Si tratterà di un esempio di struttura di dati campione 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 
}