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

Проблема

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

Для произвольного многоугольника P и фразы W я хочу "упаковать" буквы W в P, используя трансляцию, масштабирование и 90-градусное вращение, так что:

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

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

Example 1Example 2

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

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

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

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

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

Вопросы

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

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

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

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

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

Спасибо!

Ответы

Ответ 1

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

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

enter image description here

Шаги:

  • Вычислите центры каждой из букв после их размещения (это может быть просто среднее арифметическое для x и y экстентов букв). Это красные точки на рисунке выше.
  • Вычислите значения для абсолютного изменения угла в направлении движения глаз. Я показал углы angle 1 до angle 5 выше.
  • Выберите предел для максимально допустимого изменения угла, который будет учитываться в потоке, например, мы можем выбрать 35 degrees как наше значение.
  • Подсчитайте количество углов с абсолютными значениями, превышающими предел на предыдущем шаге. На нашем рисунке выше в эту категорию попадают два угла angle 3 и angle 4, поэтому count = 2.
  • Если count, полученный на предыдущем шаге, больше определенного значения, размещение текста не читается.

Надеюсь, я смогу объяснить эту идею. Производная от того же может быть хорошим решением.