algorithm - 如何将有序文本打包成任意二维多边形？

Question

问题

我正在尝试找到解决经典 2D 包装问题变体的方法 - 类似于 this question .

给定一个任意多边形 P 和一个短语 W，我想将 W 的字母“打包”到 P ，使用平移、缩放和 90 度旋转，这样:

• W的字母尽可能覆盖P；
• W 的字母通常保持有序(也就是说，虽然 W 可能被分解成更小的序列，但该序列中的字母应该保持可读)。

我正在努力实现的一些例子:

当前方法

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

• 在 256x256 网格内映射 P；
• 为 W 中的每个字母创建一个简化的边界多边形；
• 使用每个字母的位置、旋转和比例作为染色体(作为格雷编码的二进制字符串，x 位置、y 位置和比例各有 8 位，旋转有 2 位，导致染色体大小 26*length(W) 位);
• 使用交叉策略，从 A 中获取 n 个字母，从 B 中获取 length(W) - n 个字母>;
• 使用一个简单的突变策略，其中每个比特在被选为突变的个体中发生突变的概率是 1/26；
• 目前根据边界字母多边形覆盖的 P 量评估适应度。

目前，该算法已启动并正在运行并寻找解决方案，尽管它们还不是特别漂亮，因为适应度函数没有考虑字母之间的重叠或可读性约束。

它也很慢，因为适应度评估需要大量的几何计算(我正在用 Ruby 编写算法，但对几何内容使用 C 扩展)。我正在考虑使用神经网络(或者可能是支持向量机)来生成符合 this paper 中想法的适应度估计值。和 this paper .

问题

我对到目前为止所做的事情有几个问题:

• 首先，整体方法是否有意义？显然，大部分工作和计算时间都将花在调整适应度函数上，但在我深入了解它的本质之前，我想检查一下我是否朝着正确的方向前进，并且没有其他方法可以解决这个问题更好。

• 如何制定适应度函数来考虑字母顺序/可读性约束？

• 我是否可以对适应度函数进行任何优化以提高我可以计算的世代数？

任何其他想法或建议也将不胜感激。我已经通读了大多数关于类似主题的现有 SO 问题，并阅读了许多关于该主题的论文，但没有遇到任何专门处理文本打包的内容。

谢谢!

Answer 1

Q: How can I formulate the fitness function to account for the letter ordering / readability constraint?

文本可读性与流程有关，即一个单词的后续字母与眼球移动的后续方向相同。我认为像下面这样的简单技术可能会奏效。

步骤:

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

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