Using least squares regression to calculate a circle from a freehand drawing | Hacker News Reader

Using least squares regression to calculate a circle from a freehand drawing

vladgotlib.com

59 pointscurtis23 comments

The score is a bit silly; to get a better one, just add more points.

A smattering of poits scribbled close together nets me 220000, while a single big ring earns only 700.

I noticed the same thing. I was able to really boost my score by just drawing over the 'same' circle a bunch of times. Doing that got my score up into the 7-8 million range.

But that makes sense. If people draw a circle by overlaying multiple approximations, it gets better.

If there were a contest out of this, it could be disqualified: i.e. you start and finish on approximately the same point.

You can also just "color" the entire page and get a fairly high score.

To get zero error, you can just draw 3 points.

My record score 276000 with radius 45 and 155 points. Kinda addicting for some reason.

Edit: Just got 902017 for 232 points, 62 radius.

Quick version in Desmos:

https://www.desmos.com/calculator/7dpcup8iwk

Here you move the points by dragging instead of creating them by drawing, which I find more fun in some ways, and less fun in others.

Edit: constraining the radius makes the system behave like a hoop attached to springs https://www.desmos.com/calculator/a2pfwqrtmb

Not that I have a better suggestion (except something might be wrong with "disbalance"), but this is pretty obviously "that that good"

http://i.imgur.com/m8MOtUU.jpg

Least squares to calculate a circle. How utterly ...

... fitting! :)

<brag>Tried four times; hit 3.5M on third try, then 4.8M, and got bored.</brag>

If you want to do it properly, use Singular Value Decomposition, eg

http://tube.geogebra.org/student/m1113573

I'm not sure I understand the use of least squares here.

Why not use a Hough transform with each drawn point voting for a center, then average the radius?

It's not a critic - just me wondering why.

how bout explaining why what you proposed is better?

Using a Hough transform to find a circle with an unknown radius is expensive. You have a 3D parameter space, and each point has to "vote" for a 2D subsurface of that space. Discretizing the entire volume at a high resolution is going to require a lot of memory.

I agree it is going to expensive but it's not because of memory. You could probably just try every (x,y) center and have all points vote for the radius, and just keep max before moving on to next point.

A sensible, easy thing to do here seems to be to just find the centroid of the cluster points. Then convert all the points into polar coordinates around that centre, and average the R's. The R's could be weighted rather than taken at face value.

There is actually statistical theory on the best methods for fitting a circle to data. Here's an open-access paper:

https://projecteuclid.org/euclid.ejs/1251119958

I believe this website is using what the paper calls the geometric fit, which is considered one of the better methods, but the paper develops an even better method.

(I had to use this, strangely, in a physics lab course. I was measuring the Zeeman effect by looking at the diameter of rings of light projected by an interferometer; I took webcam images of the ring and used the algorithm to fit circles to the ring and hence measure its diameter.)

There's a bug in your code somewhere: http://i.imgur.com/p4tn4Kx.png

You added a point by mis-clicking very near the analyze button. It tried.

This is why we use L_1 regression!

This make me remember the Giotto big O history [1]. The pope was looking for a painter and requested samples to artists and Giotto sent for him just a circle.

[1] https://100swallows.wordpress.com/2007/09/14/giottos-o/

My best of 11,396,452: http://imgur.com/aO3xA0l

sometimes I am wondering what get voted up on HN

Sure I can help with server costs. I can eliminate them by pointing you to: https://pages.github.com/

Reply on news.ycombinator.com