-4

Given a series of points, I need to assert that the plotted points form an arc (with a certain level of confidence), and I need to approximate the radius of the arc.

For example, the following points :

[
  [337,401], [333,395], [330,392], [327,391], [324,390], [322,389],
  [319,389], [317,390], [314,391], [312,392], [309,395], [306,400]
]

should produce the curve at the bottom of the canvas (see CodePen) :

Canvas plotter

What would be an efficient way to detect the curve and approximate it's radius? I was thinking of calculating the angles between each points, where the sum would indicate the amplitude of the curve, and the average would somehow help find the center.

How can this be done?

  • 2
    Which search terms did you try? I tried "best fitting circle 2D", and the top answer from google is this link. As you can see, this is a scientific paper of 22 pages, and not overly detailed. I don't think something like this could be squeezed easily here into an answer. – Doc Brown Nov 6 at 19:52
  • While I appreciate the suggestion, I am not a mathematician, and reading scientific papers filled with math expressions (and no programming implementation) is not really a solution for me. To me, this is like asking how something is pronounced in Russian (I do not speak Russian) and you would give me a Russian dictionary with no speech synthesis. – Yanick Rochon Nov 6 at 19:59
  • 1
    Well, you asked about mathematical problem - don't be astonished to get a mathematical answer ;-) But why not look at the search results to the keywords above? It seems Google presents you some implementations in different programming languages to the circle fitting problem. – Doc Brown Nov 6 at 20:04
  • You can also search for a "javascript circle fitting library" or "python circle fitting library". I think this problem requires you to be willing to dive in into at least some of the math, though, in order to be able to interpret fitting results. – Filip Milovanović Nov 6 at 20:18
  • I do not understand the downvotes. Clearly, I did not know what to look for when I asked the question, and now that I know that the problem is called "least squares circles", I can start looking at libraries. But everything I find so far are incomplete snipets of code, or does not work (fails with errors and I have no idea how to fix them). This question gives a sandbox, and shows that I obviously need help with this. So... why the downvotes? – Yanick Rochon Nov 6 at 20:39
1

Approximate fit? How about the exact circle?

First you want to guard against some annoying edge cases:

  • No two points should be identical. Duplicate points contribute no additional information. Ergo you trio is down to two...
  • The points should not be on the same straight line. Grab a circle and try and draw a line that intersects the circles three times. Spoiler: It can't happen.

Okay now we know that we have three distinct points that are definitely on a curve.

If we knew the radius of the circle that has these three points on its edge we could simple draw three circles around each point and find where they all intersect. That would be the centre of the circle you are looking for.

Unfortunately we don't know the radius.

Interestingly though we can draw a line where every point is the centre of a circle that intersect two of those points.

  • take two points and find their mid-point. ((x1 + x2)/2, (y1 + y2)/2)
  • draw the line through that mid-point perpendicular to the line through those two points.
    • to do this find the slope of the original line (x2 - x1)/ (y2 - y1)
    • invert it, and negate it: -(y2 - y1) / (x2 - x1)
    • the line containing all the circle centre's between these two points is then: y = (-(y2 - y1) / (x2 - x1))(x - (x1 + x2)/2) + (y1 + y2)/2

Now two points by themselves these would be useless but we have three points, and because those three points are not on the same line, these two mid-point lines cannot be parallel, and will intersect somewhere. The point of intersection is the centre of the circle that exactly fits all three circumference points.

So we have two equations with from the three co-ordinates (x1, y1), (x2, y2), (x3, y3):

   y = (-(y2 - y1) / (x2 - x1))(x - (x1 + x2)/2) + (y1 + y2)/2
   y = (-(y3 - y2) / (x3 - x2))(x - (x2 + x3)/2) + (y2 + y3)/2

We can solve for x by substituting for y:

   (-(y2 - y1) / (x2 - x1))(x - (x1 + x2)/2) + (y1 + y2)/2 = (-(y3 - y2) / (x3 - x2))(x - (x2 + x3)/2) + (y2 + y3)/2

Which reduces to:

   (-(y2 - y1) / (x2 - x1))(x - (x1 + x2)/2) + (y1 + y2)/2 = (-(y3 - y2) / (x3 - x2))(x - (x2 + x3)/2) + (y2 + y3)/2
   (-(y2 - y1) / (x2 - x1))x - (-(y2 - y1) / (x2 - x1))(x1 + x2)/2 + (y1 + y2)/2 = (-(y3 - y2) / (x3 - x2))x - (-(y3 - y2) / (x3 - x2))(x2 + x3)/2 + (y2 + y3)/2
   (-(y2 - y1) / (x2 - x1))x - (-(y3 - y2) / (x3 - x2))x = -(-(y3 - y2) / (x3 - x2))(x2 + x3)/2 + (-(y2 - y1) / (x2 - x1))(x1 + x2)/2 + (y2 + y3)/2 - (y1 + y2)/2
   ((-(y2 - y1) / (x2 - x1)) - (-(y3 - y2) / (x3 - x2)))x = -((-(y3 - y2) / (x3 - x2))(x2 + x3) + (-(y2 - y1) / (x2 - x1))(x1 + x2) + (y2 + y3) - (y1 + y2))/2
   x = -((-(y3 - y2) / (x3 - x2))(x2 + x3) + (-(y2 - y1) / (x2 - x1))(x1 + x2) + (y2 + y3) - (y1 + y2)) / 2((-(y2 - y1) / (x2 - x1)) - (-(y3 - y2) / (x3 - x2)))

Double check my working, and you can simplify further as you wish. Substitute in the x1, x2, x3 and y1, y2, y3 co-ords for your three points and the result is the x co-ordinate for the circle centre.

Plug that x back into either of the two original formulas to find the y co-ordinate for the circle centre.

To discover the radius apply the standard h = sqroot(a^2 + b^ 2). Where a and b are the x and y deltas between the circle centre and one of circumference points.


Expanding that to multiple points introduces uncertainty, as its unlikely that more than three points will share the same circle.

You will need to consider how tolerant your circles will be of points that are not quite on their circumference.

  • First to determine if they should be treated as part of the same circle,
  • Second to determine how much they affect they have on determining the circle centre.
  • Thank for this well explained anwer! – Yanick Rochon Nov 7 at 13:45
1

You said approximate, not best fit, so a simple approach is likely called for.

I'm going to decompose this into three problems for you:

  1. Find the radius given 3 points
  2. Feed your array of points to the first problem 3 at a time, advancing by 1 each time
  3. Find the statistical average of a multitude of points

Fair warning, I haven't read the Scientific paper Doc Brown pointed you to but if it goes on for 22 pages this is likely the naive approach. I'm sure there are optimizations I'm ignoring but if this is fast enough and close enough for you I don't see why you should care.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.