Least square fit of circle to point set

[Tomas Gustafsson]

I have a set of points (x,y) in two-dimensional (earth surface) plane; these are actually trailpoints from a moving boat performing a turn left or right. I need to determine the radius of the turn it is executing - this has to do with prediction of the vessel's closest upcoming path.

Circular regression, i take it. There exists a circle centerpoint and a diameter that will give me the least square sum of the distances between points and circle. But the math (the optimal solution) turned out too tricky for me. I cannot figure out how to utilise the APL power here.

My guess is there will be less than 10 points. The homogenous coordinate space will (or can be) be cut so that a vertical and a horizontal edge of the pointcloud are (0,0).

Eternally grateful for a (dfn?) solution :-).

[JohnS|Dyalog]

I wonder if mean-under-log of the points as complex numbers might help:

      {|*(+⌿÷≢)⍟(↑⍵)+.×1 0j1} (1 1)(¯1 1)(¯1 ¯1)(1 ¯1)
1.414213562

To see how this works, )load dfns.dws on a Windows machine and type:

      ⍟ cxdraw 4    ⍝ visualisation of complex log

Then holding down the left mouse button, try to draw a (blue) circle around the origin. You'll see it maps to a (red) vertical line. Smoothing this line and taking the inverse (*) should map back to a smooth circle.

PS: The above produces a mean, rather than least-squares, fit. For least-squares, you'd need a ⌹ in there somewhere.

[Roger|Dyalog]

Given: a set S of complex numbers.

Find: real numbers a, b, r where a and b are the coordinates of the center (a+0j1×b) of a circle and r is its radius, such that the sum of squares of the distances from S to the circle is minimized.

I am not sure that ⌹ can be used directly because I don't see how to recast this into a _linear_ problem. If it really is a non-linear least squares problem you can use the Levenberg-Marquardt algorithm which can be implemented in APL as repeated application of a function involving ⌹.

Possibly a and b can be guessed (or even proved) to be the means of the real and imaginary parts of S, computed independently. In which case you just have to find r. The function which computes the distance from a point in S to the circle should be amusing to write.

[Roger|Dyalog]

Basic question: How do you know it's a circle?

[Roger|Dyalog]

Guess solution:

Center of circle: mean of x-coordinates, mean of y-coordinates
Radius of circle: mean of the distances from the given points to the center of the circle.

Sanity check: Draw a circle. Select random points on the circle. The above calculations should give you back the circle from those points.

[Tomas Gustafsson]

I don't see it yet. I can kind of feel the parts of the layout but making it linear crashes my head.

Abouth the guess: The points are all on a fairly short arc of a circle, like 1...few degrees. Meaning a guess of the circle's center point being in the middle of the pointsequence is very wrong - it's sits far outside the points. This is about resolving a ship's Rate of Turn (and turn radius) from a rather short set of trailpoints.

(The simulator may loop at 60 fps, and i can't maintain a data set of several seconds good of trailpoints, that would cause too big data -> too much processing as the calculation would likely happen during each frame, each time on a slightly modified ("FIFO'ed") data set. The (ongoing) result would probably fluctuate a bit when the arc is short, but stabilizing it probably works best if just dampening it's updating.)

> How do i know it's a circle?

I don't, and it is probably something else than a circle. But the term "RoT" relates much to a (turn) radius and hence a circle. So the idea is to "enforce" the best circle from the point set. The centerpoint and radius are really the useful parts as they are commonly seen in ship plotter displays. Familiar stuff for the skippers. I will probably then complete this calculation with a reasonable-degree polyfit for a short (say 20 secs) path prediction, but that's basic domino stuff..