Restore circles from Bezier curves

Question

I am trying to restore original graphic primitives from Postscript / SVG paths. Thus, an original circle is created (in SVG markup) as:

<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" /> 

This is an approximation using Bezier curves to create a circle. In other places, circular arcs are approximated by connected Bezier curves.

My question is whether there is an algorithm that I can use to recognize this construct and restore the “best” circle. I am not against small mistakes - in the worst case they will be second order.

UPDATE: Please note that I do not know a priori that it is a circle or an arc - it can be anything. And on the curve there may be 2, 3 4 or, possibly, even more points. Therefore, I would really like a function of this kind:

 error = getCircleFromPath(path) 

where error will give an early indication of whether it could be a circle.

[I agree that if I know this is a circle, this is a simpler problem.]

UPDATE: @george does some way to answer my problem, but I don't think this is the whole story.

After translation to the beginning and normalization, I see the following four points on the curve:

 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 

This ensures that the tangent at each point is "parallel" to the direction of the path at the point. It also guarantees symmetry (a 4-fold axis with reflection, but it does not guarantee a circle. For example, a large value of d will give a rounded box and a small value of a rounded diamond.

My d value is about 0.57. It could be 1 / sqrt (3.), or it could be something else. These are the relationships I ask for.

@george gives the midpoint of the arc as:

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

therefore, in my example (from 1.0 to 0.1) it will be: [[1,0]+3[1,d]+3[d,1]+[0,1]] / 8 that is.

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

and if d = 0.57, this gives 0.71, therefore, possibly d

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

This is true for a square diamond, but for circular arcs the formula should be more general, and I would appreciate it if someone had it. For example, I am not familiar with Bezier's math, so @george's formula was new to me.

 enter code here 

Answer 1

Without any math for you .. this may help:

There are always 4 control points on bezier. Your curve - 4 beziers connected together with points 1-4, 4-7, 7-10 and 10-13 control points for each part. Points 1, 4, 7 and 10 (& 13 == 1) lie exactly on the curve. To find out if you have a good circle, consider:

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

make sure you get the same result using points 4 + 10 → {158.801, 141.309}

Once you know the center, you can try the points along the curve and see if you have a constant distance.

If you have only one bezier arc with 4 points, a useful formula is that the midpoint is at (p1 + 3 (p2 + p3) + p4) / 8. So you can find a circle passing through three points:

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

and draw other points on the curve again to decide if you really have an almost circular arc.

Change the Bezier formula as follows:

 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 

so for example at t = 1/4 you have

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

therefore, as soon as you find the center, you can easily check several points and calculate their distance.

I suspect that you only need to detect almost accurate circular arcs, then checking two additional points with a tight tolerance will do the job. If you want to discover things that are approximately circular, I would calculate a bunch of points and use the average error as a criterion.

Answer 2

If all your elements have a circle, then you can simply get the dimensions via path.getBBox() and create a circle from there. In this case, I am considering ellipses, but you can easily translate them into actual circle elements:

 var path = document.getElementById("circle_path"); var bbox = path.getBBox(); var rx = bbox.width/2; var ry = bbox.height/2; var cx = bbox.x + rx; var cy = bbox.y + ry; var ellipse = document.createElementNS(xmlns, "ellipse"); ellipse.setAttribute("fill", "none"); ellipse.setAttribute("stroke", "red"); ellipse.setAttribute("stroke-width", 0.1); ellipse.setAttribute("cx", cx); ellipse.setAttribute("cy", cy); ellipse.setAttribute("rx", rx); ellipse.setAttribute("ry", ry); svg.appendChild(ellipse); 

Here you can see the demo:

http://jsfiddle.net/nwHm6/

Answer 3

The end points of the Bezier curves are probably on the circle. If so, it is easy to restore the original circle.

Another possibility is to take the barycenter of the control points as the center of the circle, because the control points are probably located symmetrically around the center. From the center, you get the radius as the average distance of the four control points closest to the center.

Answer 4

You can define an ellipse as a unit circle centered on (0,0), translated (2 parameters), scaled (2 parameters) and rotated (1 pair). Therefore, on each arc, take five points (t = 0 ¼ ½ ¾ 1) and solve for these five parameters. Then take the intermediate four points (t = ⅛ ⅜ ⅝ ⅞) and check if they lie on the same transformed circle. If so, then who is it! This is (part of) a transformed circle.

Immediately before and after there may be another arc or arcn . Are these the same ellipses? If yes, and the trimmed corners touch, then put together your part descriptions.