Determine if a Path describes a circle

Question

I am trying to test if a path or polyline describes a circle in java. How can i do this? I am thinking about testing if the biggest distance between two points is nearly the same for all points on the path (with some mistake in mind). Can this work? What other possibilities did I have to check that?

Answer 1

Assuming 2D...

1. compute bbox

   so find min and max x,y coordinate values from all the sample points x[i],y[i] you got. Lets call them x0,y0,x1,y1 where x0<=x1 and y0<=y1

2. compute center of circle cx,cy

   simply center of bbox so:

   cx = 0.5*(x1+x0)
   cy = 0.5*(y1+y0)
   

3. compute radius

   if you got really a circle then bbox should be square so

   fabs((x1-x0)-(y1-y0)) <= zero_threshold
   

   if not you do not have a circle. If yes radius is

   r = ~0.5*(x1-x0) = ~0.5*(y1-y0)
   

   so do the average ...

   r = 0.25*(x1-x0 + y1-y0)
   

4. check for deviation from circle

   compute max abs difference ...

    d = max ( fabs( (x[i]-cx)^2 + (y[i]-cy)^2 - r^2) )
   

   if d > max_radius_difference_threshold^2 then you do not have a circle.

Also check this out:

• Algorithms: Ellipse matching

There are also another tell tels like

• if you know radius and path length then it should match the circle circumference
• avg point of uniformly sampled closed circular path is also the center
• angle between line segments of uniformly sampled circular path is constant
• circle is convex only