如何将有序文本打包到任意2D多边形中？

Question

问题

我试图找到一个经典2D包装问题的变体的解决方案 - 类似于这个问题.

给定任意多边形P和短语W,我想使用平移,缩放和90度旋转将W的字母"打包" 到P中,这样:

• W的字母尽可能覆盖P ;
• W的字母通常按顺序保留(也就是说,当W可以被分解成更小的序列时,该序列中的字母应保持可读).

我想要实现的一些例子:

目前的方法

我已经开始建立一个遗传算法来尝试解决这个问题,它采用以下方法:

• 在网格内映射P256x256 ;
• 为W中的每个字母创建一个简化的边界多边形;
• 使用每个字母的位置,旋转和比例作为染色体(作为灰色编码的二进制字符串,每个x位置,y位置和比例为8位,旋转2位,产生大小26*length(W)位的染色体);
• 采用交叉战略,需要n从信一和length(W) - n信从乙 ;
• 使用简单的突变策略,其中每个位在被选择用于突变的个体中发生突变的概率是1 / 26;
• 目前,基于边界字母多边形所覆盖的P的量来评估适应度.

目前,算法正在运行并找到解决方案,尽管它们并不特别漂亮,因为适应度函数没有考虑字母之间的重叠或可读性约束.

它也很慢,因为适应性评估需要大量的几何计算(我在Ruby中编写算法,但使用C扩展来处理几何体).我正在考虑使用神经网络(或者可能是SVM)来生成符合本文和本文中的想法的适应度估计.

问题

关于到目前为止我做了什么,我有几个问题:

• 首先,整体方法是否有意义？显然,大部分的工作和计算时间都在调整适应度函数,但在我深入研究之前,我想检查一下我是朝着正确的方向前进,并且没有一种不同的方法可以解决这个问题.更好.

• 如何制定适应度函数来解释字母排序/可读性约束？

• 我是否可以对健身功能进行任何优化以改善我可以计算的世代数？

任何其他想法或建议也将非常感激.我已经阅读了大多数关于类似主题的现有SO问题,并阅读了很多关于该主题的论文,但没有涉及任何专门处理文本包装的问题.

谢谢!

Answer 1

问:我如何制定适应度函数来解释字母排序/可读性约束？

文本可读性与流程有关,即单词的后续字母处于眼睛移动的相同后续方向.我认为像下面这样简单的技术可能会起作用.

脚步:

1. 在放置之后计算每个字母的中心(这些字母可以简单地是字母的x和y范围的算术平均值).这些是上图中的红点.
2. 计算眼球运动方向角度绝对变化的值.我已经angle 1向angle 5上方展示了角度.
3. 选择要在流量中计算的最大可接受角度变化的限制,例如我们可以选择35 degrees作为我们的值.
4. 计算绝对值大于上一步限制的角度数.在我们上图中,两个角度angle 3和angle 4属于这一类,所以count = 2.
5. 如果count在上一步骤中获得的值大于特定值,则文本放置不可读.

我希望我能够解释这个想法.相同的衍生物可能是一个很好的解决方案.