从贝塞尔曲线重建圆

Question

我试图从Postscript/SVG路径重建原始图形基元.因此,原始圆圈(在SVG标记中)呈现为:

   <path stroke-width="0.5" d="M159.679 141.309 
        C159.679 141.793 159.286 142.186 158.801 142.186 
        C158.318 142.186 157.925 141.793 157.925 141.309 
        C157.925 140.825 158.318 140.432 158.801 140.432 
        C159.286 140.432 159.679 140.825 159.679 141.309" />

这是使用4个贝塞尔曲线创建圆的近似值.在其他地方,圆弧由链接的贝塞尔曲线近似.

我的问题是,是否有一种算法可以用来识别这个结构并重建"最佳"圆.我不介意小错误 - 最坏的情况是二阶.

更新:请注意,我不知道这是一个圆圈或圆弧 - 它可能是任何东西.曲线上可能有2,3,4或甚至更多的点.所以我真的很喜欢这种类型的功能:

error = getCircleFromPath(path)

哪里error会尽早表明这是否可能是一个圆圈.

[我同意,如果我知道它是一个圆圈,这是一个更容易的问题.]

更新:@george在某种程度上回答了我的问题,但我不认为这是整个故事.

在转换为原点和归一化后,我似乎在曲线上有以下四点:

point [0, 1] with control point at [+-d,1] // horizontal tangent
point [1, 0] with control point at [1,+-d] // vertical tangent
point [0, -1] with control point at [+-d,-1] // horizontal tangent
point [-1, 0] with control point at [-1,+-d] // vertical tangent

这保证了每个点处的切线与该点处的路径方向"平行".它还保证了对称性(带有反射的4倍轴.但它不能保证圆形.例如,较大的值d将给出圆形框,小值为圆形菱形.

我的价值d似乎约为0.57.这可能是1/sqrt(3.)或者它可能是其他东西.这就是我要求的这种关系.

@george给出弧的中点;

{p1,(p1 + 3 (p2 + p3) + p4)/8,p4}

所以在我的例子中(对于1,0到0,1),这将是: [[1,0]+3[1,d]+3[d,1]+[0,1]] / 8 即

[0.5+3d/8, 3d/8+0.5]

如果d = 0.57,则得到0.71,所以d可能是

(sqrt(0.5)-0.5)*8./3.

这适用于方形钻石,但对于圆弧,公式必须更加通用,如果有人拥有它,我将不胜感激.例如,我不熟悉Bezier数学,所以@george的公式对我来说是新的

enter code here

Answer 1

没有为你做所有的数学运算..这可能会有所帮助:

贝塞尔曲线上总有4个控制点.您的曲线是4个beziers链接在一起,每个部分的控制点分别为1-4,4-7,7-10和10-13.点1,4,7和10(&13 == 1)恰好位于曲线上.要查看你是否有一个漂亮的圆计算:

center =   ( p1+p7 )/2  =(  {159.679, 141.309} +  {157.925, 141.309} ) / 2
       = {158.802, 141.309}

使用积分4 + 10验证您得到相同的结果 - > {158.801,141.309}

一旦知道了中心,就可以沿着曲线采样点,看看你是否有一个恒定的距离.

如果你只有一个带有4个点的bezier弧,则一个有用的公式是中点位于(p1 + 3(p2 + p3)+ p4)/ 8.所以你可以找到通过三个点的圆圈:

{p1,(p1 + 3 (p2 + p3) + p4)/8,p4}

并再次对曲线上的其他点进行采样,以确定您是否确实具有近圆弧.

编辑bezier公式是这样的:

x=(1-t)^3 p1 + 3 (1-t)^2 t p2 + 3 (1-t) t^2 p3 + t^3 p4    with  parameter 0 < t < 1

所以例如在t = 1/4你有

x=( 27 p1 + 27 p2 + 9 p3 + 1 p4 ) / 64

因此,一旦找到中心,您可以轻松检查几个点并计算它们的距离.

我怀疑如果你只想检测几乎精确的圆弧,那么用一个严格的公差来检查两个额外的点就可以了.如果你想检测近似圆形的东西,我会计算一堆点,并使用平均误差作为标准.