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/

Answer 3

The endpoints of the Bézier curves are probably on the circle. If so, it's easy to reconstruct 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 laid out 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

One can define an ellipse as a unit circle centred on (0,0), translated (2 params), scaled (2 params), and rotated (1 param). So on each arc take five points (t=0 ¼ ½ ¾ 1) and solve for these five parameters. Next take the in-between four points (t=⅛ ⅜ ⅝ ⅞), and test whether these lie on the same transformed circle. If yes, whoopee!, this is (part of) a transformed circle.

Immediately before and after might be another arc or arcn. Are these the same ellipse? If yes, and the subtended angles touch, then join together your descriptions of the pieces.