Calcul d'angle d'intersection de cercle

[sihem-manel]

Bonjour à tous, je suis informaticienne de formation , je dois implémenter un programme qui permet de tester la couverture du périmètre des capteurs sans fil, et pour cela je dois tester chaque segment du périmètre s'il est couvert part d'autre capteur voisin qui sont a 2R de distance sachant le rayon de couverture et R, donc mon mon problème:
1- dans un cercle ayant plusieurs voisins chacun le coupe en deux point forant une angle donc mon but est de sommer les angles formé et tester si elle est égale à 2P alors tout le périmètre est couvert, mais c'est pas suffisant, car je dois rajouter une condition pour éliminer les chevauchement des angles et la je ne sais plus quoi faire,j'aurai ailer dessiner mais j'ai pas su.
2- je cherche une formule général de résolution d’équation de deux cercle qui se chevauche en deux point car je dois créer une boucle pour tester tt les capteurs :marteau:

[Robic]

Je crois avoir compris le 1. Effectivement il y a le problème des chevauchements. Une solution, c'est de définir des coordonnées dans un repère.

Représentons en mémoire d'une façon ou d'une autre l'intervalle [0°;360°]. Pour chaque cercle voisin, on cherche les deux points d'intersection, puis on en déduit les angles correspondant. Si par exemple ces deux angles sont 45° et 55°, alors on vire [45°;55°] de l'intervalle de départ, il reste [0°;45°] et [55°;360°]. Si les deux angles des points d'intersection du cercle voisin suivant sont 30° et 50° (chevauchement), on obtient [0°;30°] et toujours [55°;360°]. Et ainsi de suite. On va donc définir une liste de sous-intervalles et, pour chaque point d'intersection, donc pour chaque angle correspondant, il faudra examiner chaque sous-intervalle pour voir s'il y a quelque chose à lui enlever. Quand un sous-intervalle est entièrement vidé, il faut l'enlever de la liste. Si à la fin la liste des sous-intervalle est vide, c'est que tout le périmètre est couvert. Pour programmer ça, c'est ton rayon, mais j'imagine que ça peut se faire avec un arbre et des pointeurs pour gérer la création de sous-intervalles...

Attention que les angles peuvent être 355° et 10°, auquel cas il faut enlever [355°;360°] et [0°;10°].

C'est une suggestion, mais j'imagine qu'il peut y avoir plus simple.

Reste à calculer les points d'intersections, c'est la question 2. Calculons les coordonnées de deux cercles dont l'un est centré en O (c'est le cercle de référence, autant mettre l'origine en son centre).

- Cercle de référence, de rayon R : x² + y² = R².
- Cercle voisin quelconque, de centre (a,b) et de rayon r : (x-a)² + (y-b)² = r².

C'est parti les calculs...

... ... ....

Zut, c'est une horreur !

Finalement j'ai préféré "tricher" et chercher sur Internet. Avec Google, on trouve immédiatement ça : http://www.loria.fr/~roegel/notes/note0001.pdf (algorithme complet à la fin). En plus il a utilisé les mêmes notations que moi !

Une fois connus les points P et Q avec leurs coordonnées repectives, il reste à calculer les angles (je suppose toujours que le cercle de référence a pour centre O). Pour ça il faut utiliser une fonction qui convertit les coordonnées cartésiennes en coordonnées polaires ou bien un arc tangente à valeurs dans [0°;360] (ou autre intervalle de longueur 2 pi). En langage C, par exemple, il faut utiliser la fonction atan2(y,x) (et non pas atan(y,x) !) qui rend un angle entre -pi et +pi (ça marche parce que justement le centre du cercle est l'origine).

[sihem-manel]

Bonjour, je vous remercie infiniment pour votre réponse qui a été très trés bénéfique
alors j'ai lu et relu votre réponse à millier de fois pour essayer de comprendre cette histoire d'nterval, mais quand je travaille avec des capteurs, je ne peux pas me reperer ou mes axe sont fixé à la zone de deploiement, je ne sais definir mes début d'angles peut etre c'est qui comprend mal les math, :mur: je pensai à travailler avec les droite chaque centre du cercle je lui crée une droite avec le point d'intersection et tester
pour l'angle SVP SVP pouvez vous etres plus clair par exemnple j'ai les 2pt d'intersection et le centre comment reccuperer l'angles SVP, je suis nul en math svp :cry:

autre chose tu me dis de calculer arct2 entre 2 points, j'ai mon centre de cercle O avec deux point d'intersection A(x,y), et B(x',y'), comment definir cet angle svp

salutations

[siger]

Bonjour, je vous remercie infiniment pour votre réponse qui a été très trés bénéfique
alors j'ai lu et relu votre réponse à millier de fois pour essayer de comprendre cette histoire d'nterval, mais quand je travaille avec des capteurs, je ne peux pas me reperer ou mes axe sont fixé à la zone de deploiement, je ne sais definir mes début d'angles peut etre c'est qui comprend mal les math, :mur: je pensai à travailler avec les droite chaque centre du cercle je lui crée une droite avec le point d'intersection et tester
pour l'angle SVP SVP pouvez vous etres plus clair par exemnple j'ai les 2pt d'intersection et le centre comment reccuperer l'angles SVP, je suis nul en math svp

autre chose tu me dis de calculer arct2 entre 2 points, j'ai mon centre de cercle O avec deux point d'intersection A(x,y), et B(x',y'), comment definir cet angle svp

salutations

Bonjour,

Si j'ai bien compris l'angle cherché est l'angle couvert entre les deux points d'intersection des cercles d'emission.
Dans ces conditions il vaut mieux travailler en coordonnées polaires (à partir du centre du premier cercle et avec un axe d'angle phi avec la direction OC1) pour obtenir directement l'angle cherché
cercle C(0,0) de rayon r
cercle C1 (rc, phi) de rayon R
point d'intersection sur le cercle C definis par alpha/OC1
C : rho = r
C1 : rho² - 2rc*rho*cos (alpha-phi) + rc² = R²
les points d'intersection sont donc definis par alpha0 tel que
cos(alpha0 - phi) = (r² -R² + rc² )/(2*rc*r)
ce qui conduit evidemmnt a deux angles symetriques par rapport a l'axe OC1

Avec rc = 2R ? (je ne suis pas certain d'avoir compris)

[siger]

Bonjour, je vous remercie infiniment pour votre réponse qui a été très trés bénéfique
alors j'ai lu et relu votre réponse à millier de fois pour essayer de comprendre cette histoire d'nterval, mais quand je travaille avec des capteurs, je ne peux pas me reperer ou mes axe sont fixé à la zone de deploiement, je ne sais definir mes début d'angles peut etre c'est qui comprend mal les math, :mur: je pensai à travailler avec les droite chaque centre du cercle je lui crée une droite avec le point d'intersection et tester
pour l'angle SVP SVP pouvez vous etres plus clair par exemnple j'ai les 2pt d'intersection et le centre comment reccuperer l'angles SVP, je suis nul en math svp

autre chose tu me dis de calculer arct2 entre 2 points, j'ai mon centre de cercle O avec deux point d'intersection A(x,y), et B(x',y'), comment definir cet angle svp

salutations

Bonjour,

Si j'ai bien compris l'angle cherché est l'angle couvert entre les deux points d'intersection des cercles d'emission.
Dans ces conditions il vaut mieux faire un peu de geometrie :
Soit
O le centre du premier cercle C1 de rayon r
C le centre du second cercle C2 de rayon R tel que OC1 = a
Appelons M un des deux points d’intersection des deux cercles
Dans le triangle OMC1 le theoreme d’Al-Kashi permet d’ecrire
MC1² = MO² + OC1² - 2*MO*OC1* cos (alpha) avec alpha = angle MOC1
Soit encore
Cos(alpha) = (MO² + OC1² - MC1²)/2*MO*OC1
De qui conduit a
Cos(alpha) = (r² + a² - R²)/(2*r*a)
On obtient alors l’angle MOM’ = 2alpha formé par les deux points d’intersection des cercles
cos(2alpha) = 2*cos²(alpha)-1 = ((r^4 + R^4 + a^4) – 2R²(a²+r²))/2r²a² (sauf erreur)

Avec a = 2R ? (je ne suis pas certain d'avoir compris)

Pour revenir au probleme le domaine est couvert de maniere symetrique autour de l'axe OC1 (+alpha,-alpha). si cet axe est determiné par une direction phi par rapport a un axe donné (necessaire pour pouvoir determiner d'autres sources Cn) il faut ajouter l'angle phi
donc angle couvert : de alpha - phi à alpha + phi a partir de l'axe de reference

[Dlzlogic]

Bonjour,
Je repose le problème pour savoir si j'ai bien compris.
On a une certain nombre de capteurs dont on connait la position et la puissance : le rayon R.
On cherche à savoir s'il y a des "trous", c'est à dire des zones éloignées de plus de R de tous les capteurs.
Si la question est bien celle-là, je ne suis par sûr que la méthode qui consiste à calculer l'angle total de réception est la meilleure.
Je pencherais plutôt par une méthode de triangulation.
On divise le périmètres en triangles (l'algorithme de Delaunay est très connu et très efficace). Ensuite, dans chaque triangle on cherche s'il existe un point qui se trouve à une distance supérieure à R des 3 sommets.
Ceci me paraitrait beaucoup plus facile.

[Robic]

tu me dis de calculer arct2 entre 2 points, j'ai mon centre de cercle O avec deux point d'intersection A(x,y), et B(x',y'), comment definir cet angle svp

Dans la méthode que je préconisais, avec des coordonnées, on ne calculait pas l'angle AOB (n'était-ce pas inutile puisque ça ne marchera pas à cause des chevauchements ?) mais l'angle (Ox,OA) et l'angle (Ox,OB). On calculait donc deux angles (avec la fonction arc tangente 2) ce qui permettait de déterminer l'intervalle d'angles entre les deux points. Le but, pour contrer l'inconvénient des chevauchements, était ensuite d'éliminer progressivement tous les angles entre 0 et 2 pi et espérer qu'une fois tous les cercles balayés, il ne reste plus rien.

Mais je pense qu'on n'est pas sur la même longueur d'onde. J'ai répondu uniquement au problème mathématique en me basant sur les explications du 1 et du 2 ,mais ce que dit Dizlogic indique que j'ai dû mal comprendre. En fait, je pense que la phrase « chacun le coupe en deux point forant une angle » devrait être expliquée de façon précise (pour moi, l'angle était l'angle entre les deux points d'intersection et le centre, apparemment ce n'est pas ça).

[sihem-manel]

Bonjour a tous,
merci bcp frenchement vous l'avez impressionné vraiment vraiment vraiment, je voudrai vous envoyé une image mais j'ai pas su, alors je vous envoi ce lien j'ai essayé de l'hebergé laba.

http://img809.imageshack.us/img809/1226/sanstitrelz.png

pour robic c'est vraiment ce que je cherche, donc si je démare avec les 2 premiers point d'intyersection avec le premier capteur, je calcul l'intervall d'arc je fais la meme chose avec les autre capteurs apres je fais la soustraction ou quoi??? desolée je suis tres tres nule en math :mur: :mur: :mur: :mur:
donc dans l'image la partie d, le capteur en rouge est totalement couvert et vous remarqué les chevauchement

merci bcp siger pour votre reponse

salutations

[Robic]

Ah oui, c'est bien comme j'avais compris.

La méthode que je préconise, s'il est possible d'utiliser des coordonnées, c'est de faire une boucle sur tous les cercles voisins (j'appelle "cercle rouge" celui dessiné en rouge et " cercles voisins" tous les autres).

Pour chaque cercle voisin, on détermine les deux points d'intersection, puis les deux angles, et donc l'intervalle d'angles. Par exemple [45°;100°]. Cet intervalle doit être effacé de la liste.

Quand la boucle est terminée (tous les cercles voisins ont été balayés), l'intervalle de départ [0°;360°] doit avoir disparu (à force d'effacer des intervalles d'angles).

Pour faire ça, il reste à modéliser la situation et ce n'est pas un problème de maths mais d'informatique. Plus haut je parlais d'arbre, en fait je verrais plutôt une liste. Chaque élément de la liste est une structure dont les champs sont angle1 = l'angle de gauche, angle2= l'angle de droite, plus les pointeurs vers la structure précédente et la structure suivante. Cette liste va permettre de modéliser quelque chose comme [0°;40°] union [60°;210°] union [245°;360°].

Imaginons par exemple qu'au bout de deux intersections on ait supprimé [40°;60°] et [210°;245°], on aurait alors la liste que je viens de décrire au paragraphe précédent.

Troisième cercle voisin : on trouve comme angles 355° et 30°. Il faut supprimer [355°;30°]. Pour ce faire, on compare les deux angles en question avec les champs angle1 et angle2 de la liste afin de transformer :
[0°;40°] union [60°;210°] union [245°;360°]
en :
[30°;40°] union [60°;210°] union [245°;355°].

À force de balayer les cercles voisins, on risque d'avoir une liste de plusieurs sous-intervalles, qu'on ne connaît pas à l'avance (d'où l'idée d'une liste avec pointeurs). Mais à la fin de la boucle, on peut espérer que les sous-intervalles vont disparaître. Si le cercle rouge est entouré comme il faut, il ne doit plus rien rester (liste vide).

Mais bon, là je parle de techniques de programmation, et tu connais ça beaucoup mieux que moi.

(Et si tu ne peux pas utiliser de coordonnées, je ne sais pas comment faire.)

[siger]

Bonjour a tous,
merci bcp frenchement vous l'avez impressionné vraiment vraiment vraiment, je voudrai vous envoyé une image mais j'ai pas su, alors je vous envoi ce lien j'ai essayé de l'hebergé laba.

http://img809.imageshack.us/img809/1226/sanstitrelz.png

pour robic c'est vraiment ce que je cherche, donc si je démare avec les 2 premiers point d'intyersection avec le premier capteur, je calcul l'intervall d'arc je fais la meme chose avec les autre capteurs apres je fais la soustraction ou quoi??? desolée je suis tres tres nule en math :mur: :mur: :mur: :mur:
donc dans l'image la partie d, le capteur en rouge est totalement couvert et vous remarqué les chevauchement

merci bcp siger pour votre reponse

salutations

Pour ma part, malgré le schema joint, je n'ai pas encore compris exactement ce que tu cherches
- en particulier ce que veut dire
s'il est couvert part d'autre capteur voisin qui sont a 2R de distance sachant le rayon de couverture et R,
- quels sont les parametres variables (s'ils existent), autrement dit s'il s'agit d'un constat a partir de capteurs determines ou d'une optimisation a partir d'un ou plusieurs parametres

L'angle de couverture entre eux cercles est proportionnel à r, R et a la distance entre les centres.
Si ces trois parametres sont fixés (ansi que l'angle entre les capteurs) on ne peut que constater le resultat ( avec recouvrement ou pas)

Si le nombre de capteurs est fixé (n) par exemple, mais pas leur position, la couverture complete sans recouvrement sera obtenue pour un angle entre deux capteurs de 2*pi/n
Si r et R sont fixes la couverture sera complete avec des capteurs situes sur un cercle centré sur la zone a couvrir et de rayon a = 2cos(pi/n) + V( r²sin²(pi/n) +R²)
Si la distance a est egale a 2R, .......

[sihem-manel]

alors robic merci bcp bcp pour ces explication, j'ai essayé d'utiliser ta méthode en calculant debut et fin de chaque segment pour cela j'ai utilisé ces équations suivante pour eviter de calculer les point d'intersection
soit Si and Sj , deux capteur ayant comme coordonés (xi, yi) and (xj, yj)
Oi and Oj est leur centre et est l'angle entre OiOj et l'axe des X

= arctan (yj;) yi /Xj-xi) . on peut prouver facilement que

P1OiOj =;)OjOiP2 = = arccos(distance entre Si et Sj)/ 2R . Since 0 < d(i,j) <2rs, we have 0 < < /2.

donc l'angle de couverture du capteur Sj est [;) , + ] ~ =;)j;)i.

http://imageshack.us/photo/my-images/708/sanstitreifm.png/


voila cette image pourra t'aider. mais maintenant mon probleme c'est l'angle en lui méme, en utilisant arctg j'ai trouvé des valeurs negatif : quel est le resultat de arctan comment je peut recuper l'angle lui meme.
par exemple mon exemple: [19, 55] [0, 90] [-37,55, -109] et la je ne sais plus quoi faire
je sais t'es entrain de dir que celle la est nulle en math, je sais trés bien, :mur:

[sihem-manel]

svp si je prend :
y = arctang (y2-Y1/x1-x2) quel est le resulat obtenu j'aurai par example cette valeur : 56.33 c'est en raduis ou en degrés , comment le transformer en fonction de P , et si j'ai une valeur negative quesu'il faut faire :cry:
merci chers amis je compte sur vous pour me répondre

[Dlzlogic]

Bonsoir,
Excusez-moi si je radote, mais on ne sait toujours pas ce que vous cherchez à faire.
Je crains que vous soyez dans le cas type où vous avez choisi la solution avant d'avoir décrit le problème.
Croyez-moi, votre calcul sur les angles est très compliqué et ne peut se justifier que s'il n'y a pas d'autre solution.
Donc, s'il vous plait, expliquez ce que vous devez faire, on pourra vous aider sur la méthode.

Si vous en êtes vraiment à vous demander comment fonctionne un atan, atan2, que se passe-t-il suivant son signe etc., il vaut mieux arrêter.

PS. lu votre dernier message : on reprend tout à zéro : expliquez ce que vous devez faire, surtout sans parler d'angles, et on pourra peut-être vous aider.

[Robic]

Pour ma part je crois avoir compris quelque chose, sans en être sûr. Donc je réponds par rapport à ça : le problème est qu'on a un "cercle rouge" entouré de "cercles voisins" qui coupent le "cercle rouge", ce qui définit des arcs de cercle communs, et on veut savoir si l'ensemble des arcs de cercle commun fait tout le "cercle rouge" ou s'il reste des "trous" (disons). Si ce n'est pas le problème, il serait temps de m'arrêter...

Pour répondre à Sihem-manel :
- En C, il faut utiliser la fonction arc tangente 2 de la bibliothèque standard, pas arc tangente. Dans un autre langage, je ne connais pas, mais il faut trouver une fonction équivalente.
- En C, l'arc tangente 2 fournit un angle entre -Pi/2 et +Pi/2, donc les angles peuvent être négatifs. Dans ce cas, au lieu de travailler sur [0°; 360°] ou [0; 2Pi], on travaille sur [-Pi/2 ; +Pï/2].

Si tes connaissances mathématiques ne sont pas suffisantes pour manipuler ces notions, aïe aïe aïe... (je n'ai pas le temps de te faire un cours de trigo... :lol3: )

[Dlzlogic]

@ Robic,
La fonction atan2 doit exister à peu près dans tous les langages. En fait elle résout tout simplement le problème qui consiste à effectuer la division par le plus grand de X ou de Y.

[sihem-manel]

Robic frenchement t'es TOP, j'ai pu executer mon programme en C++ et j'ai crée des tableau pour chaque capteur , la ou j'ai inseré mes debut et fin de chaque angle, et j'ai fais l'union et ça fonctionne je viens de le faire mainetenat disant je travaille sous NS3 qui est un simulateur réseau, désolée parce que je suis nulle en math j'ai perdu tt mes repere en math, mais vraiment j'ai appris bcp de chose grâce à vous et bien sur votre forum, et je remercie toute personne a participé a ce sujet merci merci merci

[sihem-manel]

slt, je reviens encor une fois à vous
pour le doc PDF que tu m'a envoyé, les équations sont fausse car si je prend un cas très simple de deux cercle qui se chevauche et je remplace alors je trouves pas les bon point d’intersection:

Oi (4,3) et Oj(6,5) avec r=2 pour les deux cercle