用优化算法进行形状算法

Question

我有一组由直线段定义的形状。

我想简化这个形状，使其只由一组有限斜率的直线段构成。

我希望在最小化使用的线段数量的同时，尽量减小形状变化前后的面积差异。

我希望能够同时最小化这两个因素，并根据用户指定的权重调整其中一个优先程度。

minimize { J = w1(number of segments/length) + w2(difference area/length) }

当w1和w2都是权重值，而长度为新段的长度时，我需要一个能够实现此功能的算法。有什么想法吗？

下面我展示几张图片来说明我希望它如何工作。在文献中是否有任何可以帮助编写算法的内容？谢谢！

- user1216527

Answer 1

这个问题似乎很棘手！我会先定义两个子程序来解决它：

1. diffArea(fig, target) 计算 fig 和 target 之间的差异面积。
2. decomp(fig, p1, p2, s1, s2) 计算通过用形状为 s1 和 s2 的一对线段替换 p1 和 p2 之间所有线段所建立的两个图形。例如，如果在 fig 中，点 p1 和 p2 之间有四条线段，则 decomp(fig, p1, p2, s1, s2) 返回两个图形，它们是通过用适当缩放版本的 s1 和 s2 替换这四条线段而生成的。在二维空间中，只有一种方法可以缩放 s1 和 s2 来填充 p1 和 p2 之间的空间，并且这两个图形来自于将它们排序为 s1 -> s2 或者 s2 -> s1。

鉴于这两个例程，我认为迭代局部搜索程序可能效果很好。您可以按照以下步骤进行：

1. 将fig设置为一个大的边界形状，围绕着target
2. 对于每一对在fig中的顶点(p1, p2)（从1个段之间的对开始，然后是2个段之间的对，...），以及每一对形状(s1, s2)：
   • 使用decomp(fig, p1, p2, s1, s2)计算fig1和fig2
   • 让e_fig成为fig中边缘的数量，e_new成为fig1和fig2中边缘的数量
   • 如果w1 * e_new + w2 * diffArea(fig1, target) < w1 * e_fig + w2 * diffArea(fig, target)，则用fig1替换fig
   • 如果w1 * e_new + w2 * diffArea(fig2, target) < w1 * e_fig + w2 * diffArea(fig, target)，则用fig2替换fig

重复此过程，直到您测试了每对顶点并且没有找到更好的替代方案为止。这显然不会给您最优的解决方案，但我敢打赌它会表现得相当不错。

- josliber

Answer 2

嗯，对于这种情况来说，“Pareto efficiency”似乎是一个不错的解决方案的衡量标准。 乍一看，使用离散优化可能是适当的选择。 具体算法的选择取决于要形成的图形的复杂程度。 对于大而复杂的图形，我建议使用遗传算法。

- NBR