6 ms·

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

59 points by curtis 12y ago

8note 12y ago
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.
- austin_y 12y ago
  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.
  - kazinator 12y ago
    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.
- inverba 12y ago
  You can also just "color" the entire page and get a fairly high score.
- bananabob 12y ago
  To get zero error, you can just draw 3 points.
- jlarocco 12y ago
  My record score 276000 with radius 45 and 155 points. Kinda addicting for some reason. Edit: Just got 902017 for 232 points, 62 radius.
guylhem 12y ago
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.
- the_cat_kittles 12y ago
  how bout explaining why what you proposed is better?
- teraflop 12y ago
  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.
  - rawnlq 12y ago
    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.
- kazinator 12y ago
  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.
- capnrefsmmat 12y ago
  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 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.)
murkle 12y ago
If you want to do it properly, use Singular Value Decomposition, eg http://tube.geogebra.org/student/m1113573 http://tube.geogebra.org/student/m1113573
fruchtose 12y ago
There's a bug in your code somewhere: http://i.imgur.com/p4tn4Kx.png http://i.imgur.com/p4tn4Kx.png
- Maome 12y ago
  You added a point by mis-clicking very near the analyze button. It tried.
  - TTPrograms 12y ago
    This is why we use L_1 regression!
eof 12y ago
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 http://i.imgur.com/m8MOtUU.jpg
kazinator 12y ago
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>
jwmerrill 12y ago
Quick version in Desmos: https://www.desmos.com/calculator/7dpcup8iwk 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 https://www.desmos.com/calculator/a2pfwqrtmb
biot 12y ago
My best of 11,396,452: http://imgur.com/aO3xA0l http://imgur.com/aO3xA0l
ebauch 12y ago
sometimes I am wondering what get voted up on HN
bbcbasic 12y ago
Sure I can help with server costs. I can eliminate them by pointing you to: https://pages.github.com/ https://pages.github.com/
anodari 12y ago
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/ https://100swallows.wordpress.com/2007/09/14/giottos-o/

59 points by curtis 12y ago

8note 12y ago

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.

austin_y 12y ago
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.
- kazinator 12y ago
  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.
inverba 12y ago
You can also just "color" the entire page and get a fairly high score.
bananabob 12y ago
To get zero error, you can just draw 3 points.
jlarocco 12y ago
My record score 276000 with radius 45 and 155 points. Kinda addicting for some reason. Edit: Just got 902017 for 232 points, 62 radius.

guylhem 12y ago

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.

the_cat_kittles 12y ago
how bout explaining why what you proposed is better?
teraflop 12y ago
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.
- rawnlq 12y ago
  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.
kazinator 12y ago
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.
capnrefsmmat 12y ago
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 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.)

murkle 12y ago

If you want to do it properly, use Singular Value Decomposition, eg http://tube.geogebra.org/student/m1113573 http://tube.geogebra.org/student/m1113573

fruchtose 12y ago

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

Maome 12y ago
You added a point by mis-clicking very near the analyze button. It tried.
- TTPrograms 12y ago
  This is why we use L_1 regression!

eof 12y ago

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 http://i.imgur.com/m8MOtUU.jpg

kazinator 12y ago

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>

jwmerrill 12y ago

Quick version in Desmos: https://www.desmos.com/calculator/7dpcup8iwk 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 https://www.desmos.com/calculator/a2pfwqrtmb

biot 12y ago

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

ebauch 12y ago

sometimes I am wondering what get voted up on HN

bbcbasic 12y ago

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

anodari 12y ago

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/ https://100swallows.wordpress.com/2007/09/14/giottos-o/