Как упаковать упорядоченный текст в произвольный 2D-многоугольник?

Проблема

Я пытаюсь найти решение вариации классической задачи 2D-упаковки - нечто похожее на этот вопрос .

Учитывая произвольный многоугольник P и фразу W , я хочу «упаковать» буквы W в P , используя перенос, масштабирование и поворот на 90 градусов, так что:

• буквы W покрывают P в максимально возможной степени;
• буквы W обычно остаются в порядке (то есть, хотя W может быть разбит на более мелкие последовательности, буквы в этой последовательности должны оставаться читаемыми).

Некоторые примеры того, чего я пытаюсь достичь:

Текущий подход

Я начал создавать генетический алгоритм, чтобы попытаться решить эту проблему, который использует следующий подход:

• Карты P внутри сетки 256x256 ;
• Создает упрощенный ограничивающий многоугольник для каждой буквы в W ;
• Использует положение, поворот и масштаб каждой буквы в качестве хромосомы (как двоичные строки в кодировке Грея с 8 битами для каждой из x-позиции, y-позиции и масштаба и 2 битами для вращения, что приводит к хромосомам размером 26 * длина (W) бит) ;
• Использует стратегию кроссовера, которая берет n букв из A и длины (W) - n букв из B ;
• Использует простую стратегию мутации, при которой вероятность мутации каждого бита у индивидуума, выбранного для мутации, составляет 1/26 ;
• В настоящее время оценивается пригодность на основе количества P co ограничены многоугольниками ограничивающей буквы.

В настоящее время алгоритм запущен и работает и находит решения, хотя они еще не особенно хороши, поскольку функция приспособленности не учитывает перекрытие букв или ограничение удобочитаемости.

Это также довольно медленно, так как оценка пригодности требует большого количества геометрических вычислений (я пишу алгоритм на Ruby, но использую расширение C для геометрического материала). Я рассматриваю возможность использования нейронной сети (или, возможно, SVM) для генерации оценок пригодности в соответствии с идеями, изложенными в этой статье и этой статье .

Вопросы

У меня есть пара вопросов о том, что я сделал до сих пор:

• Во-первых, имеет ли смысл общий подход? Очевидно, что большая часть работы и времени вычислений будет связана с настройкой фитнес-функции, но прежде чем я перейду к деталям, я хочу проверить, что я двигаюсь в правильном направлении, и нет другого метода, который мог бы решить эту проблему. лучше.

• Как я могу сформулировать функцию приспособленности, чтобы учесть ограничение порядка букв / удобочитаемости?

• Могу ли я внести какие-либо оптимизации в функцию приспособленности, чтобы увеличить количество поколений, которые я могу реально вычислить?

Любое другое идеи или советы также были бы очень признательны. Я прочитал большинство существующих вопросов SO по аналогичным темам и прочитал ряд статей по этой теме, но не нашел ничего, что конкретно касалось бы упаковки текста.

Спасибо!