Inscription / Connexion Nouveau Sujet
Intersection de 3 cercles
bonjour,
J'ai un challenge informatique pour lequel je dois trouver les points appartenant à un triangle équilatéral de coté 273 dont la distance de ces même point aux trois sommets sont des distances entières !
j'ai fais un premier programme mais qui ne marche pas suffisament rapidement.
Alors je change de méthode. Il faudrait que je trouve l'intersection des 3 cercles de centre et rayon respectif A(0,0) B(273,0) et C(136.5,273*sqrt(3)/2), ra ,rb, rc;
Donc je dois résoudre le système suivant :
x²+y²=ra²
(x-273)²+y²=rb²
(x-136.5)²+(y-273)²=rc²
J'ai voulu passer par la théorie et résoudre
(x-xa)²+(y-ya)²=ra²
(x-xb)²+(y-yb)²=rb²
(x-xc)²+(y-yc)²=rc²
Mais bon ça devient rapidement le bazarre !
Pouvez-vous me conseiller une méthode à suivre pour avoir mes conditions de tests ?
Merci d'avance
Erreur dans la 3ème équation.
x²+y²=ra²
(x-273)²+y²=rb²
(x-136.5)²+(y-273*V3/2)²=rc²
x²+y²=ra²
x²+y²-546x=rb²-74529
x²-273x + 18632,25 + y² - 273V3*y + 55896,75 = rc²
x²+y²=ra²
x²+y²-546x=rb²-74529
x²+y²-273x- 273V3*y + 74529 = rc²
546x = ra²-rb²-74529
et comme ra²-rb²-74529 est un entier, 546x doit être entier mais x <= 273
--> x est mutiple de 1/2
x = (1/2).k avec k dans N est dans [0 ; 546]
x²+y²-273x- 273V3*y + 74529 = rc²
273x + 273V3*y = 74529 + ra² - rc²
--> 273x + 273V3*y est entier
273*(x + V3*y) est entier
Comme V3 est irrationnel et x multiple de 1/2, on a y multiple de V3/2
----
x = k/2
y = k' * (V3)/2
Avec k dans N et dans [0 ; 546]
et k' dans N et dans [0 ; 273]
Les équations deviennent:
k²/4 + (3/4).k'² = ra²
k²/4 + (3/4).k'² - 273k + 74529 = rb²
k²/4 + (3/4).k'²- 136,5k - 409,5k' + 74529 = rc²
avec Avec k dans N et dans [0 ; 546]
et k' dans N et dans [0 ; 273]
-----
A partir de là, Excel trouve comme solutions:
k = 0 , k' = 0 --> P(0 ; 0)
k = 130 , k' = 0 --> P(65 ; 0)
k = 240 , k' = 0 --> P(120 ; 0)
k = 306 , k' = 0 --> P(153 ; 0)
k = 416 , k' = 0 --> P(208 ; 0)
k = 546 , k' = 0 --> P(273 ; 0)
k = 65 , k' = 65 --> P(32,5 ; 32,5*V3)
k = 81 , k' = 65 --> P(40,5 ; 32,5*V3)
k = 120 , k' = 120 --> P(60 ; 60*V3)
k = 426 , k' = 120 --> P(213 ; 60*V3)
k = 153 , k' = 153 --> (76,5 ; 76,5*V3)
k = 393 , k' = 153 --> (196,5 ; 76,5*V3)
k = 208 , k' = 208 --> (104 ; 104*V3)
k = 338 , k' = 208 --> (169 ; 104*V3)
k = 273 , k' = 273 --> (136,5 ; 136,5*V3)
-----
Pour le faire informatiquement, comme k dans N et dans [0 ; 546] et k' dans N et dans [0 ; 273], on peut en imbriquant 2 boucles et en vérifiant à chaque passage que k²/4 + (3/4).k'² = carré parfait
et k²/4 + (3/4).k'² - 273k + 74529 = carré parfait
et k²/4 + (3/4).k'²- 136,5k - 409,5k' + 74529 = carré parfait
...
-----
Sauf distraction. (Rien relu, comme d'habitude) 
Merci d'avoir pris le temps de me répondre aussi précisément ! Je vais coder tout ça maintenant !
Cependant j'avais un peu réfléchis pendant mon CM et je voulais savoir s'il été juste de procéder ainsi également !
Dans mon cas il ne pourra y avoir qu'un seul x et 1 ou 2 solutions pour y.
On part de là :
(1) (x-xa)²+(y-ya)²=ra² (3)<-(2)-(3) : x_bc=f(xb,xc,yb,yc,rb,rc) test BC
(2) (x-xb)²+(y-yb)²=rb² <=> (2)<-(1)-(2) : x_ab=f(xb,xa,yb,ya,rb,ra) test AB
(3) (x-xc)²+(y-yc)²=rc² (3)<-(1)-(3) : x_ac=f(xa,xc,ya,yc,ra,rc) test AC
Donc là on a x exprimé en fonction des constantes connues :
(1) <=> y² - 2*ya*y + ( x² - 2*xa*x - ra² + xa² + ya² ) = 0
(2) <=> y² - 2*yb*y + ( x² - 2*xb*x - rb² + xb² + yb² ) = 0
(3) <=> y² - 2*yc*y + ( x² - 2*xc*x - rc² + xc² + yc² ) = 0
On réinjecte les constantes x_ab dans (1), x_ac dans (1) et x_bc dans (2).
Sachant qu'on ne veut qu'un seul point de croisement entre deux cercles, il suffit alors de calculer le discriminant et vérifier qu'il vaut 0, dans ce cas là et c'est celui qui m'intéresse il n'y a qu'une solution.
Donc il suffit que je fasse mes boucles faisant varier la longueur de mes 3 rayons connaissant les coordonnées de leur centre et de faire les 3 tests suivant
Pour ra allant de ....
Pour rb allant de ....
Pour rc allant de ....
calcul de x_ab, x_ac, x_bc
calcul de 
ab, ac, bc
Si ( (bc=0)&&(ab=0)&&(ac=0) )
Retourner la valeur des rayons correspondant
Fin Si
Sinon Retourner 0
Fin boucle
Fin boucle
Fin boucle
Merci encore de votre aide !
Il y a beaucoup de façons de procéder.
Mais il est fort à parier que si tu le fais par 3 boucles imbriquées cela prendra plus de temps (car plus de cas à traiter).
On peut aussi le faire à partir des équations:
x²+y²=ra²
x²+y²-546x=rb²-74529
x²+y²-273x- 273V3*y + 74529 = rc²
On remarque alors que cela peut s'écrire:
x²+y²=ra²
ra²-546x=rb²-74529
ra²-273x- 273V3*y + 74529 = rc²
x = r²a - rb² + 74529
--> on faisant seulement 2 boucles imbriquées sur toutes les valeurs possibles de ra et rb, on peut directement calculer le x correspondant par x = r²a - rb² + 74529
Et en ayant la valeur de x, on a directement le y correspondante par x²+y²=ra²
On calcule, alors ra²-273x- 273V3*y + 74529 en utilisant les valeurs de x et y trouvées et on vérifie si le résultat est un carré parfait --> OUI, c'est une solution, Non, ce n'est pas une solution.
-----
Bref, de multiples chemins sont possibles.
Sauf distraction
Ok je voulais juste savoir si la mienne était valable !
La votre, il est vrai est la plus "optimisée" !
Merci encore et bonne continuation
Ecris-en plusieurs versions et regarde si les solutions trouvées sont les mêmes.
Si oui, prend celle qui va le plus vite.
Bonjour,
cette discussion date de 2008, mais je suis aussi confronté au même problèmes et je sollicite votre aide si possible.
Ma première question est d'abord: pourquoi avez vous besoin de faire des conditions sur les valeurs possible des rayons, puisque normalement pour l'intersection des trois cercles, les rayons sont connus et on cherches les valeurs possibles de x et y.
je vous remercie.
Cordialement.
Bonjour
Voici un raisonnement plus simple :
On peut supposer que les sommets du triangle sont (0;0), (273;0) et
On choisit un point entre les deux premiers sommets, situé à une distance entière de chacun d'eux, disons avec
.
La distance entre ce point et le troisième sommet est donc
Un bête programme montre rapidement que cette distance est un nombre entier lorsque
Oubliez ma réponse, j'avais compris qu'on cherchais un point sur le triangle et non pas à l'intérieur...
Bonjour,
Il s'agit de trouver (algorithmiques) le point d'intersection de cercles, en connaissant la position des cercles (coordonnées x et y par rapport au plan) et le rayon des cercles. il faut donc passer par des équations de cercles.
Bonjour Doingmath,
As tu également la condition que ces points d'intersection soient à coordonnées entières ?
Faut-il déterminer les points d'intersection de cercle deux à deux ou bien seulement les points qui appartiennent aux 3 (ou plus) cercles à la fois ?
Quel est ton problème exactement ?
Un point situé à distance de
et à distance
de
est de la forme
avec
et
...
La distance qui le sépare du point est alors
et on veut que ce nombre soit entier lorsque
et
sont entiers.
Voici un programme en "pseudo-langage"
For s = 0 To 273
For r = 0 To 273
Let x = (r^2-s^2+74529)/546
Let y2 = r^2-x^2
Let t = 2
If y2>=0 Then t = r^2-273*(x+Sqrt(3*y2))+74529
If Int(Sqr(t))^2 = t Then Print(x & " - " & Sqrt(y2))
Next r
Next s
Bonjour Noflah,
En effet, je veux déterminer les points d'intersection de cercle deux à deux; Par exemple si j'ai quatre cercles, j'aurai d'abord à chercher les intersection deux à deux, ce qui nous donne 6 combinaison possible de couple de cercles. ensuite l'intersection unique viendra après.
Concernant les coordonnées, je n'ai pas encore répondu à cette question, mais selon moi, il est judicieux de ne pas exiger qu'il soient seulement des entiers.
Je te remercie.
Cordialement.
Jalex, On ne parle pas du même problème je crois.
Bonjour Doingmath,
En effet Jalex répond au problème posé au tout début du topic, étant donné que tu disais avoir le même problème. Finalement ton problème semble quelques peu différent.
En quel langage écris-tu ? Qu'est ce qui te pose problème dans ton programme en particulier ?
En considérant que en entrée tu ais : une liste (ou vecteur en fonction du langage) de couple (x,y) représentant les centres de chaque cercle et une liste de même longueur comprenant le rayon de chaque cercle. Notons ces listes U et V, U[1]=(x1,y1) et V[1]=R1 etc.
Alors il faut considérer deux cercles parmi les n cercles, comparer la distance entre leur centres respectif avec la somme de leur rayons et il y a alors 3 cas à prendre en compte si je ne me trompe pas.
Ou alors tu peux présenter une résolution beaucoup plus systématique (moins géométrique), en posant le système et en faisant résoudre à la machine.
Ensuite mettons que tu présente en sortie la liste de tous les points d'intersection. Tu peux à chaque nouveau point vérifier avant de l'ajouter s'il n'appartient pas à la liste, afin de le coefficienter s'il est déjà dans la liste, ainsi tu distingueras en sortie les points qui sont intersections de 2 cercles, 3 cercles, ..., k cercles.
Peut être en effet que je suis resté sur le sujet de départ... et que ce nouveau sujet aurait mérité un nouveau topic...
En principe, quand on cherche l'intersection de plusieurs cercles, on commence par faire l'intersection de deux d'entre eux et on vérifie si les points d'intersection obtenus se trouvent sur les autres cercles. Je ne vois pas l'intérêt de calculer des intersections de cercles deux à deux...
Bonjour Jalex,
En effet, mais on ne sait pas ce que veux faire DoingMath avec ses points d'intersection. Peut être a-t-il besoin de tous les points.
EN fait, c'est aussi de l'intersection de trois cercles ou plus. Sauf que je n'envisage pas la même démarche que le début.
Je code en C. l'approche de départ est algébrique : utiliser les équation de cercles. calculer ainsi deux a deux leur intersection puis vérifier chacune des intersection avec un troisième cercle. Je m'explique: Si par exemple on a 3 cercles, ceci nous fera 3 possibilités. Donc on aura à chercher 3 couples d'intersection de cercles {(C1 inter C2),(C1 inter C3) et(C2 inter C3)}. ensuite vérifier si (C1 inter C2), donc leur point d'intersection est dans c3; Puis j'envisage une astuce qui me donnera l'intersection unique.
J'espère que j'ai été assez clair.
Cordialement.
Oui je crois comprendre ce que tu veux faire, mais puisque tu as une bonne idée de ce que tu veux faire, qu'est ce qui te bloque ? Où as tu besoin d'aide ?
Posté par ProfilJalex Jalex
Peut être en effet que je suis resté sur le sujet de départ... et que ce nouveau sujet aurait mérité un nouveau topic...
En principe, quand on cherche l'intersection de plusieurs cercles, on commence par faire l'intersection de deux d'entre eux et on vérifie si les points d'intersection obtenus se trouvent sur les autres cercles. Je ne vois pas l'intérêt de calculer des intersections de cercles deux à deux...
C'est en faisant une recherche que je suis tombé sur ce forum et absolument on aprle du même sujet, avec une démarche différente. Je suis d'accord que lorsqu'on cherche l'intersection de plusieurs cercles, on commence par faire l'intersection de deux d'entre eux et on vérifie si les points d'intersection obtenus se trouvent sur les autres cercles. Et c'est ça que je veut faire.
Je suis désolé sur le fait que ça devait mériter un nouveau topic.
Cordialement.
Bonjour Noflah,
Je suis bloqué sur les tests et il me semble que ma logique sur la partie de l'algorithme n'a pas été cohérent, je pense.
Cordialement.
Peux tu nous détailler jusque là la façon dont tu as procédé ? Ou bien dis nous ce que tu attends de nous ?
le nous, c'est juste une façon formelle de présenter.
voici un vite aperçu.
Fonction intersection_plus_cercles(nombre de cercles : n)
Fonction Combinaison Cnp = (factorielle n) / {(factorielle p) * (factorielle (n-p))}
Retourne nombre de combinaisons : nbcomb
Fin Fonction Combinaison
/*************Boucle while prenant en compte le nombre de combinaison************/
Tant que nbcomb pas atteint
Fonction_tirage_deux_nombre_aleatoire entre 1 et n : le couple tiré doit être unique (tiré une seule fois)
Retourne_un_couple = coordonnées centre cercle 1, rayon cercle 1, coordonnées centre cercle 2, rayon cercle2
Fin Fonction_tirage deux_nombre_aleatoire
// calcul l'intersection de cercles, deux à deux
Fonction Intersection_2_cercles (position capteur1, rayon capteur1, position capteur2, rayon capteur2)
Retourne_coordonnées_points_intersection_pour chaque_couple
Fin Fonction Intersection_2_cercles
Fin Tant que
//Fonction vérifiant si l'intersection (ou point d'intersection) de deux cercles, se trouve dans un troisième cercle.
Fonction intersection_unedroite_2cerles
Fin Fonction intersection_unedroite_2cerles
Fin Fonction intersection_plus_cercles
Cordialement.
Je rêve ou pour faire tous les couples possibles tu tire deux entiers de façon aléatoire jusqu'à avoir tous les couples possibles ????
Je pense qu'il vaut mieux faire deux boules for imbriquées, telles que :
Tu prend le premier cercle de la liste et fais son intersection avec les (n-1) suivants (un par un).
Puis le deuxième et fais son intersection avec les (n-2) suivants, etc.
N'est ce pas plus simple ?
Je ne comprends pas (entre autre) le besoin de dénombrer le nombre d'intersections à effectuer. Peut-être peut on envisager un programme du type
For i = 1 to n-1
For j = i+1 to n
----> intersection(cercle i,cercle j)
Next j
Next i
ou alors un programme récursif...
Ehhh ben, c'est pas al peine de rêver. c'est justement la raison pour laquelle la question est posée. je ne suis pas une génie de la prog, so.
merci pour vos suggestions et vos réponses quant à la cohérence de la démarche.
Ensuite comment garantir l'unicité entre les intersections de (c1, c2) et c3, (c2, c3) et c1 etc.
Il s'agit de la fonction vérifiant si l'intersection (ou point d'intersection) de deux cercles, se trouve dans un troisième cercle: Fonction intersection_unedroite_uncerle.les points d'intersections obtenus ( s'il y'en a deux bien sur) formeront une équation de droite par exemple. ensuite il faudra chercher laquelle des deux points obtenus de l'intersection des deux cercles est dans le troisième cercle et ceci pour chaque couple de cercles.
Puisque pour cherche l'intersection de trois cercles par exemple, il faut d'abord faire l'intersection de deux d'entre eux d'abord ensuite on vérifie si les points d'intersection obtenus se trouvent sur le troisième cercle.
Excuse moi, je ne pensais pas que tu étais novice en info.
Pour présenter les résultat voici ce que je proposerais :
Tu crée une liste vide au début de ton programme, et qui grossit à chaque exécution de la boucle. Seulement au lieu d'ajouter bêtement à chaque tour une nouvelle intersection, tu effectue au préalable une recherche dans ta liste déjà existante pour voir s'il cette solution n'est pas déjà apparu auparavant, auquel cas tu ne la rajoute pas.
Tu vois le principe ?
Pour les algorithme de recherche dans une liste (ou vecteur), tu peux regarder sur internet c'est quelque chose d'assez classique, du coup tu dois en trouver des très optimisé (en complexité). Sinon la bonne méthode naïve : tu parcours la liste en testant si ton objet est égal à celui pointé dans la liste.
Il n'y a pas de mal, c'est vrai que c'est en forgeant qu'on devient forgeron. Merci beaucoup encore pour vos réponses rapides.
Ok, Mais cela va pas toujours résoudre le problème de vérification de résultats de points d'intersection de deux cercles dans un troisième? mais les intersection de cercles deux a deux. Oubien?
Cordialement.
Et bien, si en faisant C1(inter)C3 tu obtiens un résultat que tu avais déjà obtenu avec C1(inter)C2 c'est bien que C1 C2 et C3 se coupent en ce point ?
Si ca peut vous aider : les points d'intersection de deux cercles
et
sont donnés vectoriellement par
avec
(distance entre les centres),
et
(si
!)
Bonjour,
Merci Jalex, ça peut toujours aider. Par contre peut-tu être plus précise s'il te plait si possible sur ta démarche. car lorqu'on passe par la résolution itérative d'équation de cercles, on trouve s'il ya lieu deux points d'intersection avec des coordonnées x et y plus complexes.
Cordialement.
Annuler
connectez vous
géométrie en post-bac