My target is to find a center of a circle that approximate a set of dots

i want to find minimum of a function: $$\sum_{i=0}^N (\sqrt{(x_i - a)^2 + (y_i - b)^2} - R)^2$$

this function represent an error of a my approximation of a set a dots on a plane with a circle.

I did a bit of a googling and find that Gradient Descent is a decent method for a numerical searching for a minimum of function.

But i have a trouble with understanding how i should correcnt my A,B,R with partial derrivative, when i have function of summ.

picture related for better explanation of my problem: http://imgur.com/gallery/ecUdXnB

  • $\begingroup$ Maybe this is banal, but: what about a simple average of the dots coordinates to find the circle center, and the average distance from that center to the dots to have the radius? $\endgroup$ – Vincenzo Lavorini Jun 21 '18 at 14:51
  • $\begingroup$ there is potentially a much noisy dots with spikes, so it's probably not the best option. $\endgroup$ – stronk_kisik Jun 21 '18 at 15:16
  • 1
    $\begingroup$ But if the source data is noisy, then the surface where you want your gradient to descent is also filled with local minima, and your gradient can fall down into one of those, missing the global minimum. So a simple solution like this is also much more robust: you are guaranteed to catch the global minima. And if you want to exclude outliers, you can use a two step process: extract circle center and radius in the way I suggested, excluding the dots too far from the radius, repeat the first step to extract the new center and radius. $\endgroup$ – Vincenzo Lavorini Jun 21 '18 at 15:31
  • $\begingroup$ @VincenzoLavorini , averaging doesn't work well for circle with skipped sector. I use averaged x,y coordinates and estimated radius as seed value for algorithm and it works good now. $\endgroup$ – stronk_kisik Jun 26 '18 at 12:01

I came up with the simple answer after I just rewrite this idea on paper:

$$\frac{\delta \sum \Big[f(x,y)\Big]}{\delta x} = \sum \frac{\delta f(x,y)}{\delta x}$$

so it's just partial derivative for each Experimental Dot summed. Algo works quite well.

  • $\begingroup$ Hey, the question is great. What does it mean when you say "experimental dot" summed? I am not familiar with this concept. $\endgroup$ – akshit bhatia Mar 4 '20 at 23:58

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.