Monte-Carlo, plus grand cercle compris dans trois cercles

[ashrak]

Bonjour,

Je planche depuis un moment sur un petit problème d’optimisation. Le but est de déterminer le plus grand cercle compris dans trois autres cercles. J'ai au départ reproduit (sans le savoir) le problème d'Apollonius en demandant que ce cercle soit tri-tangent et vérifie donc pour trois cercles l'équation suivante:

C'est tout à fait faux, il faut en vérité voir une inégalité et maximiser R. Chose facile, il suffit de faire un petit solveur et c'est bon. Le hic c'est que j'effectue une simulation Monte-Carlo sur les trois cercles (position et diamètres) et que je dois réaliser un très grand nombre de calculs pour obtenir la distribution du rayon du fameux cercle. J'ai tenté pas mal d'approches analytiques en vain.

Si quelqu'un a une petite idée de solution ou une méthode numérique rapide de calcul, les inégalités c'est quand même très lourd à se trimbaler.

Cordialement,

Ashrak
-----

[Dlzlogic]

Bonjour,
J'ai pas vraiment compris votre problème.
Vous avez 3 cercles connus (entre et rayon), vous cherchez le cercle tangent extérieurement à ces 3 cercles ?
Je n'ai pas essayé de le résoudre analytiquement, mais par une méthode d'itération, ça devrait pas être trop dure.
1- on prend un point approché
2- on calcule l'écart par rapport à C1
3- on rectifie en conséquence
4- même chose par rapport à C2
5- même chose par rapport à C3
6- on recommence au point 2-

On s'arrête quand les 3 corrections sont inférieures à la précision recherchée.
A mon avis ce calcul peut se faire avec une simple calculette et juste un peu de rigueur.

[ashrak]

Bonsoir,
Justement non, je ne cherche pas la tangence aux trois cercles, je sais calculer ça explicitement. Je cherche le plus grand cercle qui est compris dans chacun des trois autres cercles. Il peut y avoir tri-tangence, bi-tangence ou égalité à un des cercles. Mais le calcul doit pouvoir se faire rapidement et avec certitude de convergence car intégré à une subroutine Monte-Carlo.

Cordialement,

[toothpick-charlie]

Je cherche le plus grand cercle qui est compris dans chacun des trois autres cercles.

bonsoir,

que signifie exactement l'expression "compris dans" ?

[A voir en vidéo sur Futura]

[Dlzlogic]

Bonjour,
Autre question : comment définiriez-vous "subroutine Monte-Carlo" ?

[ashrak]

Bonsoir,

Merci de prendre un peu de temps, par "compris" ou "inclus" j'entend que tout point du cercle recherché (dans le plan) doit se trouver dans chacun des cercles (). Donc dans le repère de chaque cercle (d'origine le centre du cercle) qui fait ma contrainte, les coordonnées (x,y) d'un point du cercle recherché doivent vérifier:

Ceci est donc à calculer pour donnés. Par subroutine Monte-Carlo, j'entend que j'ai des distributions pour certains paramètres de mes cercles de contrainte et je simule des tirages pour évaluer la distribution résultante du cercle recherché.

Voilà.

[toothpick-charlie]

donc tu cherches en fait le plus grand cercle inclus dans l'intersection de trois disques. Il faut distinguer plusieurs cas. Si par exemple l'un des disques est inclus dans l'intersection des deux autres, le cercle cherché est égal au cercle frontière dudit disque. Sinon, il faut discuter selon le nombre de points singuliers de la frontière de l'intersection des trois disques (ce nombre vaut 2, 3 ou 4).

[ansset]

bonsoir,
ben c'est loin d'être trivial.
autant avec 2 cercles ça va tout seul, trouver centre et rayon ,
avec trois c'est autre chose.
j'essaye d'étendre ma logique de 2 vers 3, mais ça coince un peu pour l'instant.

[ashrak]

Bonsoir,

donc tu cherches en fait le plus grand cercle inclus dans l'intersection de trois disques.

J'aurais du commencer par cette explication, plus rapide qu'un long discours. Il y a quelques cas "simples" mais en général ce n'est pas évident du tout. Pour poursuivre un peu sur le message d'ansset, j'ai regardé du côté des droites reliant les points d'intersections appartenant à un même cercle qui sont toutes concourantes, mais ça ne marche pas. Surtout quand les rayons sont différents.
Il est très prévisible qu'il n'existe pas de solution analytique et je vais sans doute avoir besoin de l'extension à 4 cercles ...

[toothpick-charlie]

si ce que tu cherches c'est la distribution du rayon de ce cercle, je ne suis pas sûr que tu aies besoin de faire des simulations. On sait calculer la distribution de la distance d'un point donné à un disque aléatoire (à condition de supposer que les centres des disques forment un processus de Poisson et que les rayons sont indépendants des centres). Il faudrait voir si on peut adapter le calcul à la situation qui t'intéresse (pas sûr non plus). Il y a des informations sur ce genre de calcul dans les livres de Kallenberg (Random Measures) ou bien celui de Stoyan, Kendall & Mecke (Stochastic Geometry). Enfin ce n'est pas forcément facile...

[ansset]

. J'ai au départ reproduit (sans le savoir) le problème d'Apollonius en demandant que ce cercle soit tri-tangent et vérifie donc pour trois cercles l'équation suivante:

C'est tout à fait faux, il faut en vérité voir une inégalité et maximiser R.

bonjour,
c'est effectivement le reflexe premier.
pourquoi dis tu que c'est tout à fait faux ?
ps : je ne doute pas de ce que tu dis, c'est pour ma propre gouverne.
merci
cordialement.

[toothpick-charlie]

c'est faux par exemple si l'un des disques est inclus dans l'intérieur de l'intersection des deux autres: le plus grand disque est égal au petit disque et n'est donc pas tangent aux deux grands disques.

[ansset]

oui, oui, j'ai failli corriger de moi_même , mais trop tard.
désolé

[ansset]

je trouve l'exercice très interessant.
ne peut-on pas faire une segmentation topologique avant de chercher une solution analytique pour chaque cas.
le nb de cas topologique est assez réduit après tout.
prenons 2 des 3 cercles.
- pas d'intersection -> pas de solution finale
- un seul point commun M ( cas spécifique facile à resoudre si M est ou pas ds le 3 ème cercle )
- 2 points d'intersection definissant une zone en forme d'amande ( et deux arcs de cercle )
le cercle inscrit maximum est dans ce cas là assez facile à déterminer. ( centre, rayon et coord des points d'intersection )
je l'appelle Cs.

on rajoute un cercle.
la on liste les différentes topologies possibles.
- le troisième cercle inclu les deux points d'intersection de Cs -> le premier cercle trouvé Cs est le bon
- le troisième cercle n'inclu aucun des points -> pas de solution
- le troisième cercle est inclus ds Cs , la solution est le troisième cercle
- le troisième cercle inclus Cs , la solution est Cs
- le nouveau cercle intersecte la zone sans être dans aucun cas précedent
- si c'est en un point, c'est la seule solution
- sinon il n'y a plus que qcq cas de figure
- un nouvelle zone à 3 points , ou à 4 points.
la solution à 3 points me semble pouvoir être résolue par la première équation postée.par l'auteur du post
à 4 points , pas encore reflechi....

[ashrak]

Bonsoir,

si ce que tu cherches c'est la distribution du rayon de ce cercle, je ne suis pas sûr que tu aies besoin de faire des simulations. On sait calculer la distribution de la distance d'un point donné à un disque aléatoire (à condition de supposer que les centres des disques forment un processus de Poisson et que les rayons sont indépendants des centres). Il faudrait voir si on peut adapter le calcul à la situation qui t'intéresse (pas sûr non plus). Il y a des informations sur ce genre de calcul dans les livres de Kallenberg (Random Measures) ou bien celui de Stoyan, Kendall & Mecke (Stochastic Geometry). Enfin ce n'est pas forcément facile...

Je recherche effectivement la distribution du rayon, les trois cercles de contrainte suivent une distribution expérimentale (c'est un processus de fabrication). Le but est de modifier ces distributions pour voir l'impact sur la distribution du rayon du cercle recherché. Je pense que c'est un secret de polichinelle mais bon, c'est un problème statistique de montabilité.
J'ai commencé à coder un petit programme, il tourne bien qu'un peu lent. Le problème va devenir plus ardu avec l'ajout de conditions supplémentaires.
Je vais étudier en détail les références.
@ansset: j'ai réalisé le même travail que toi mais je bloque au même endroit.

Cordialement,

[ansset]

si je te comprend bien, il ne reste que le cas à 4 points d'intersection !
ou bien ai-je mal saisi ?

[ansset]

je cherche une solution pour les 4 points avec deux arcs de même rayon et deux autres arcs de rayon diff
soit évidemment 3 rayons diff seulement.
à bientôt
pascal

[ansset]

je fait un up , car je pense avoir une approche pour les 4 points.
soit donc un espace délimité par 4 poins avec 4 arc de cercle entre les points dont 2 ont la même courbure.
mais en fait on s'en fout un peu.
je pense qu'on peut montrer que le plus petit des arcs de cercle ne sert à rien.
je veux dire qu'un cercle inscrit tangent à cet arc ne peu être le plus grand.
on remplace donc les 2 points entourant cet arc par le point extérieur .
on se retrouve avec la problématique à trois points qui est résolue.