通过删除不必要的点和叠加形状来优化矢量图像

Question

通过删除不必要的点和叠加形状来优化矢量图像

algorithmmathematical-optimizationpath-findingvector-graphics

7

我需要优化一个由贝塞尔曲线构成的填充形状的矢量图像。输入图像和分离后形状如下：

我要通过删除不必要的线条并依靠形状的堆叠来优化图像，但要少得多的顶点数。结果形状应该是这样的：

这个问题可以分解为以下步骤:

1. 检测堆叠的线条。 2. 找到其他形状填充区域的贝塞尔路径。 3. 找到最佳的堆叠顺序，使顶点数最小。 4. 如果形状中有孔，则表示其内部所有内容都应该堆叠在其上。

总体而言，第二步似乎是最麻烦的，因此我需要一点指引。

就样例图片而言，如何找到贝塞尔路径，让绿色形状的被遮挡部分穿过蓝色形状（和可选的黄色形状），反之亦然？我不需要最短的路径，我需要其中顶点最少的路径。

实质上，我需要找到这些路径，顶点数最少。

- Athari

1

@matt 这是一个纯粹的[标签:算法]问题，语言并不重要。 - Athari

@matt 你可以假设所有形状都被切割出来，没有重叠，所有形状完美接触，相邻形状的顶点完美匹配，一个形状中的顶点不包含重复，没有自交和其他使编写算法更容易的前提条件。 - Athari

[...] (1) 我没有找到任何路径的方法，因此没有什么可以简化的。(2) 如果找到的路径靠近形状的边界，任何简化都几乎肯定会使路径超出边界。因此，要么路径查找需要以某种方式找到更接近形状“中心”的路径，要么简化需要以某种方式尊重其他形状的边界。//@גלעדברקן 假设所有形状都被定义为贝塞尔链 [A p₁ p₂ B p₁ p₂ C ... Y p₁ p₂ Z]，带有相同方式定义的可选孔。如果您不想处理孔，请随意跳过它，这种情况可以单独处理。 - Athari

1

(1) 第一条路径是未堆叠的边界。如果您查看蓝色和绿色之间的边界，则可以确定蓝色位于“顶部”，绿色的第一个猜测是用蓝色的未堆叠线替换堆叠线。(2) 这并非针对“任何”简化都是正确的。我认为您考虑了简化接口线而不是非接口线。 - matt

我相信你可以在光栅域中准确地解决这个问题（即将曲线/形状映射到特定DPI/分辨率的预定网格上）。一旦在光栅域中解决了问题，你就可以用更简单的曲线集合来近似光栅解决方案，或者将光栅解决方案用作指南。这是否是一个可接受的答案？如果是，我可以详细说明如何做到这一点。 - ldog

显示剩余9条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

我看到这里有多个难点的问题。以下是我的一些想法:

直接处理贝塞尔曲线似乎很困难。 我建议通过多边形或成对多边形逼近它们。如果选择后者，则需要考虑曲线的二阶导数，以确定它是凸面还是凹面，或者是否从凸面转变为凹面（如果是，则在其拐点处切割）。

曲线方向可以识别孔洞。 如果边界曲线的方向被定向为右侧是形状内部，则逆时针方向的曲线表示孔洞。对于简单的贝塞尔形状，包含相应顺时针边界的任何形状都必须叠放在前面。简单多边形的顺时针/逆时针方向可以通过带符号面积测试。

曲线简化是最短路径问题，但度量不是欧几里得度量。假设我们知道一些简单多边形的叠放顺序。给定其中一个多边形P，我们形成包含P和与之相交的每个在P前面的多边形的联合的多边形Q。我们希望连续改变P边界的部分，使其在Q内的边数最小化。对于每个部分，我们应该能够通过可见性算法在隐式无限图中从一个端点模拟广度优先搜索到另一个端点。

优化叠放顺序感觉NP-hard。 我还没有想出简化；这只是我作为有资格的算法设计者的直觉感受，即似乎更简单的排序问题-反馈弧集-是NP-hard，并且简单多边形为构造器件提供了很多自由度。在实践中，我的建议是计算每个多边形的凸包，并声明其凸壳不相交的两个多边形的顺序不重要。取此图的补集并枚举其不包含循环的方向（有有效的算法可用）。对于每个定向，执行拓扑排序将其扩展为总体顺序，然后相应地优化曲线。如果仍然过于昂贵，我会使用遗传算法，特别是BRKGA与自然解码器（每个染色体包含一个数字，表示每种形状；按数字对形状进行排序）。