Sắp xếp các chữ cái của một câu trong một khu vực tối thiểu?

Question

Tôi sẽ viết một chương trình sắp xếp lại các chữ cái của một câu trong một khu vực tối thiểu. Công cụ mà tôi sẽ viết ứng dụng này không quan trọng. Vấn đề là tôi gần như không có ý tưởng làm thế nào tôi có thể làm điều này.

Tôi muốn một cái gì đó như thế này:

Có bất kỳ thuật toán để sắp xếp một số bề mặt (giả sử mỗi chữ cái một bề mặt đa giác) trong một khu vực tối thiểu?

Answer 1

Trong this paper bạn có thể tìm thấy thông tin chi tiết về Wordle, một công cụ để tạo những đám mây thẻ đẹp. Nó thực hiện một thuật toán tham lam ngẫu nhiên xấp xỉ của vấn đề đóng gói bin.

Answer 2

Không dễ chút nào ... nó liên quan đến "Sự cố đóng gói thùng" được chứng minh là NP-HARD.
Ngoài ra, vấn đề của bạn liên quan đến các đối tượng không phải hình chữ nhật, do đó nó khó hơn một chút nhưng không phải theo độ lớn.

bạn nên đi cho một cách tiếp cận thuật toán tối ưu hóa như thuật toán di truyền hay như vậy ...

Google cho "Bin đóng gói 2D" sẽ cho kết quả khá một vài liên kết hữu ích và bài viết.

Answer 3

Phê duyệt của tôi cho thuật toán như vậy sẽ là một thuật toán di truyền. Đây sẽ là mẫu cấu trúc dữ liệu mẫu trong 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 
}