2
$\begingroup$

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: https://i.stack.imgur.com/vSsZU.jpg

$\endgroup$
4
  • $\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$ Jun 21, 2018 at 14:51
  • $\begingroup$ there is potentially a much noisy dots with spikes, so it's probably not the best option. $\endgroup$ Jun 21, 2018 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$ Jun 21, 2018 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$ Jun 26, 2018 at 12:01

1 Answer 1

0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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