reconstructing circles from Bezier curves

Question

I am trying to reconstruct original graphics primitives from Postscript/SVG paths. Thus an original circle is rendered (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 4 Beziers curves to create a circle.In other places circular arcs are approximated by linked Bezier curves.

My question is whether there is an algorithm I can use to recognize this construct and reconstruct the "best" circle. I don't mind small errors - they will be second-order at worst.

UPDATE: Note that I don't know a priori that this is a circle or an arc - it could be anything. And there could be 2, 3 4 or possibly even more points on the curve. So I'd really like a function of the sort:

error = getCircleFromPath(path)

where error will give an early indication of whether this is likely to be a circle.

[I agree that if I know it's a circle it's an easier problem.]

UPDATE: @george goes some way towards answering my problem but I don't think it's the whole story.

After translation to the origin and normalization I appear to have 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 guarantees that the tangent at each point is "parallel" to the path direction at the point. It also guarantees the symmetry (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 a rounded diamond.

My value of d appears to be about 0.57. This might be 1/sqrt(3.) or it might be something else.It is this sort of relationship I am asking for.

@george gives midpoint of arc as;

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

so in my example (for 1,0 to 0,1) this would be: [[1,0]+3[1,d]+3[d,1]+[0,1]] / 8 i.e.

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

and if d =0.57, this gives 0.71, so maybe d is

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

This holds for a square diamond, but for circular arcs the formula must be more general and I'd be grateful if anyone has it. For example, I am not familiar with Bezier math, so @george's formula was new to me

enter code here

Answer 1

Without doing all the math for you.. this may help:

there are always 4 control points on a bezier. Your curve is 4 beziers linked together with points 1-4 , 4-7 , 7-10 , and 10-13 the control points for each part. Points 1 , 4 , 7 and 10 (&13==1) lie exactly on the curve. To see if you have a nice circle calculate:

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

verify you get the same result using points 4+10 -> {158.801, 141.309}

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

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

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

and again sample other points on the curve to decide if you indeed have a near circular arc.

Edit the bezier formula is this:

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

so once you find the center you can readily check a few points and calculate their distance.

I suspect if you only want to detect nearly exact circular arcs then checking two extra points with a tight tolerance will do the job. If you want to detect things that are approximately circular I would compute a bunch of points and use the average error as a criteria.

Answer 2

If all your elements are circle-like then you can just get the dimensions through path.getBBox() and generate a circle from there. In this case I'm considering ellipses, but you can easily translate it to 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);

You can see a demo here:

http://jsfiddle.net/nwHm6/