Cercle le plus proche de n points

Lancey · November 2018

Bonjour,

J'ai un problème un peu particulier et je ne sais pas par quel bout l'attaquer.
Je cherche à déterminer le centre d'un cercle passant par n points mais avec un rayon donné. Je ne cherche pas le rayon passant au mieux, mais le centre [x,y] du rayon R passant au plus près de mes points. Avec 2 points c'est assez simple mais à partir de 3, je ne vois pas comment procéder. Si vous avez une piste à me proposer, je vous en remercie par avance.

Cordialement.

gerard0 · November 2018

Bonjour.

Que signifie "au plus près". La somme des distances au cercle ? La somme des carrés des distances au cercle (cercle d'ajustement des moindres carrés) ? Autre chose ?
Et pourquoi "le centre" ? Il y a à priori plusieurs cercles, non ?

Nb : Tu devrais modifier ton titre, puisque ton cercle ne passe pas par les points.

Cordialement.

pappus · November 2018

Bonjour
Si on veut vraiment simplifier les calculs, commencer par faire $R=0$ pour voir ce que cela donne avec une définition raisonnable de la proximité.
Amicalement
[small]p[/small]appus

Lancey · November 2018

Bonjour et merci pour vos réponses, c'est vrai que le terme "au plus près" est discutable mais je cherche une méthode, oui comme par exemple les moindres carrés, qui me permet de "calculer" le centre du cercle.
Pourquoi le centre, car je connais déjà son rayon, c'est mon paramètre fixe.
Je demande cela, car dans le cadre de mon travail, nous usinons des pièces de forme cylindrique. La trajectoire de l’outil est codée en dur par des petits segments qui décrivent un cercle. Je ne peux donc pas modifier la valeur du rayon décrit. Je ne peux que déplacer le centre du rayon pour effectuer une correction. J’ai tenté une approche par justement la méthode des moindres carrés mais le résultat me donne qu’à moitié satisfaction. Je « trouve » effectivement les coordonnées du centre mais aussi le rayon théorique. De plus, je travaille sur des rayons assez grand (+600mm) mais avec une courte longueur d’arc (+/-50mm). Les valeurs de corrections que j’obtiens sont « aberrantes » d’un point de vue machine. Je voudrais donc coller à la réalité en fixant mon rayon et de le positionner « au mieux » pour coller à mes points de contrôle et en trouver son centre.

JLT · November 2018

Pas sûr qu'il existe une formule simple donnant le centre. Déjà pour 2 points il y a deux solutions, alors pour plusieurs points ça risque de se compliquer. Peut-être le mieux serait de tirer au hasard par ordinateur 1 million de points et chercher celui qui minimise la somme des distances au cercle.

gerard0 · November 2018

J Jacquelin, qui vient parfois sur ce forum, a mis à disposition des documents sur les approximations par les moindres carrés. Ton problème pourrait l'intéresser, mais je ne sais pas comment le contacter. Essaie un message privé à J.Jacquelin, mais je ne sais pas si ce nom est encore actif sur le forum.

Cordialement.

[Jean Jacquelin vient sur le forum avec le pseudo 'JJ'. AD]

Lancey · November 2018

Merci, je tente de le contacter.
Cordialement.

Math Coss · November 2018

En notant $(x_k,y_k)$ ($1\le k\le r$) les coordonnées des points, on peut chercher à minimiser \[\sum_{k=1}^r\bigl(x_k^2+y_k^2+bx_k+cy_k+d\bigr)^2,\] ce qui revient à déterminer la projection orthogonale dans $\R^r$ euclidien standard de $(x_k^2+y_k^2)_{1\le k\le r}$ sur l'espace engendré par $(x_k)_{1\le k\le r}$, $(y_k)_{1\le k\le r}$ et $(1)_{1\le k\le r}$. Le centre est alors $(-b/2,-c/2)$ et le rayon se calcule aussi. Ou bien je me plante ?

JLT · November 2018

Le rayon est fixé au départ.

Math Coss · November 2018

D'accord, j'avais lu le problème initial en début d'après-midi mais pas la suite.

Autre suggestion : considérer la grandeur \[\sum_{k=1}^r\bigl((x_k-b)^2+(y_k-c)^2-R^2\bigr)^2\] comme le potentiel d'un point $(b,c)=(b(t),c(t))$ et résoudre numériquement les équations de la mécanique : le point devrait s'approcher du ou d'un minimum (elle est convexe, cette fonction ?).

gerard0 · November 2018

Pour 2 points A et B et 2R>AB, il y a deux centres possibles. Donc la convexité ...

Cordialement.

YvesM · November 2018

Bonjour,

Et pourquoi pas le barycentre du nuage de points ?

P. · November 2018

D'apres les physiciens la bonne notion de distance d'un point par rapport a un cercle est le carre de sa puissance. Avec cette definition , methode des moindres carres marche parfaitement. Doc sur demande.

Lancey · November 2018

Merci beaucoup pour votre aide.
Je vais tenter une approche similaire a votre proposition JTL.

Je vais programmer des boucles qui balayent une zone en [x,y] avec un pas grossier et chercher celles qui minimise la somme des distances.
Ensuite rebalayer autour de ces coordonnées avec un pas de plus en plus fin jusqu’à la précision voulue.

Édite: Je retombe exactement sur votre formule Math Coss, merci encore!

JJ · March 2019

bonjour,

Par hasard je suis tombé sur cette discussion. Avec mes excuses pour cette réponse tardive,

Voici une méthode pour calculer approximativement les coordonnées du centre du cercle. Si plus de précision était nécessaire, il faudrait mieux spécifier les critères d'optimisation et procéder par itération comme cela a été évoqué dans la discussion.

La méthode suivante (en page jointe) est une adaptation de la méthode de régression circulaire donnée pp.11-13 dans l'article :
https://fr.scribd.com/doc/14819165/Regressions-coniques-quadriques-circulaire-spherique :
On verra aisément en quoi consiste cette adaptation par rapport à la méthode originelle.

L'exemple numérique est volontairement limité à un faible nombre de points ne décrivant qu'une petite partie du cercle et avec une forte dispersion. Ceci afin d'illustrer la robustesse du procédé.

PS. : Bonjour et merci à gerard0. Son message (dans la discussion suivant la question) a attiré mon attention sur ce problème. 85416

Cercle le plus proche de n points

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 22