如何简化由多个贝塞尔曲线组成的路径?

7
我有一条由多个三次贝塞尔曲线组成的路径,我需要将其简化为更平滑的路径。

paths

这基本上是Inkscape的简化(Ctrl+L)算法在多次应用时所做的事情。
在上面的示例中,我应用了simplify算法,直到节点数量变为< 10。虽然这不是强制性的,但任何节点数/阈值度量都是可以接受的,只要它不会变得难以忍受的缓慢。
以下是此示例中的两个路径,使用SVG语法:
Original path (black):
m 14550,8173.5 c 0,5 -7,10 -16,10 -20,0 -44,24 -44,44 0,19 -16,21 -23,3 -2,-6 -8,-8 -13,-4 -5,4 -2,13 6,18 11,8 12,12 3,16 -7,2 -13,17 -13,33 0,16 -6,31 -12,33 -10,4 -9,8 2,16 13,10 13,12 0,22 -11,8 -12,12 -2,16 6,2 12,11 12,20 0,19 24,43 43,43 9,0 18,6 21,12 5,10 7,10 12,0 3,-6 19,-12 35,-12 16,0 29,-5 29,-10 0,-6 9,-10 20,-10 13,0 20,-7 20,-20 0,-11 5,-20 10,-20 6,0 10,-5 10,-10 0,-6 -9,-10 -20,-10 -13,0 -20,7 -20,20 0,15 -7,20 -29,20 -16,0 -32,6 -35,12 -5,10 -7,10 -12,0 -3,-6 -14,-12 -24,-12 -10,0 -20,6 -23,12 -2,7 -8,9 -13,5 -5,-4 -2,-13 6,-18 11,-8 12,-12 3,-16 -7,-2 -13,-18 -13,-34 0,-29 0,-29 59,-29 38,0 61,4 64,12 4,10 8,9 16,-2 9,-13 12,-13 20,-1 8,12 12,12 25,-2 17,-17 22,-87 6,-87 -5,0 -10,-7 -10,-16 0,-23 -25,-44 -54,-44 -14,0 -26,-5 -26,-10 0,-6 -4,-10 -10,-10 -5,0 -10,4 -10,10 m 20,20 c 0,5 7,10 16,10 20,0 44,24 44,43 0,9 5,17 12,19 8,3 2,15 -15,32 l -28,28 -20,-23 c -17,-20 -22,-21 -30,-9 -8,13 -10,13 -20,0 -8,-11 -12,-12 -16,-3 -8,20 -23,15 -23,-7 0,-11 5,-20 10,-20 6,0 10,-7 10,-15 0,-16 39,-63 53,-64 4,-1 7,3 7,9 m -40,240 c 0,5 -4,10 -10,10 -5,0 -10,-5 -10,-10 0,-6 5,-10 10,-10 6,0 10,4 10,10

Simplified path (red):
m 14550,8173.5 c -87.258,33.0594 -133.146,148.0519 -100.308,233.0182 28.598,79.3143 205.987,42.2193 169.477,-27.3586 -37.609,79.4541 -211.748,14.7616 -116.882,-53.3781 65.16,23.4014 214.495,3.3059 154.09,-94.6746 -20.611,-36.676 -63.348,-64.0056 -106.377,-57.6069 z m 20,20 c 97.756,2.0053 70.654,166.2739 -23.471,106.0693 -77.428,-5.092 -32.934,-112.5198 23.471,-106.0693 z m -40,240 c -21.559,21.7572 -1.859,-30.1121 0,0 z

这个问题有已知的算法吗?

(很抱歉没有提供任何代码。我正在使用Python和svgpathtools。话虽如此,这不是一个问题:我接受任何语言(甚至只是伪代码!)的解决方案。

我查看了Inkscape的源代码,但是那里的算法实现非常庞大,并且似乎与Inkscape的内部紧密耦合。


为了好玩和更深入的理解,还要绘制曲线上和曲线外的点,包括之前和之后的点。因为我认为你不需要我们来完成这个任务:只需在每个步骤中绘制点,以便您可以看到它们如何移动,我相信这几乎会立即向您展示编写代码所需的内容,以实现相同的效果。 - Mike 'Pomax' Kamermans
1个回答

1

虽然我不确定Inkscape是否使用这种方法,但我认为你在寻找的是叫做“曲线拟合”的过程。曲线拟合是构建最适合一系列数据点的曲线或数学函数的过程,可能受到约束条件的影响。

curve fitting demo

实施方案,请参考:

  1. Philip J. Schneider的FitCurves.c
  2. C库ideasman42/curve-fit-nd
  3. Rust库ideasman42/raster-retrace


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接