具有优化的形状算法

Question

我有一个由直线段定义的形状.

我想简化用直线构造的形状,但只有一组有限的斜率.

我想尽量减少使用的段数,并尽量减少区域与前后形状的差异.

我想用用户定义的重量同时最小化这两件事,强调最小化另一个.

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

当w1和w2均为重量和长度是新段的长度.我想要一个算法来做到这一点.有任何想法吗？

下面我展示一些我可能希望它如何工作的图片.文献中是否有任何可能有助于编写算法的内容.谢谢!

Answer 1

这看起来是一个非常棘手的问题！我会首先定义两个例程来处理它：

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

考虑到这两个例程，我认为迭代的本地搜索过程可能会很好地工作。您将执行以下步骤：

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

重复此过程，直到测试完每对顶点并且发现没有改进的替代品为止。这显然不会给你一个最佳的解决方案，但我敢打赌它会表现得很好。