Déterminer une zone de convergence

Bonjour, je ne sais pas si j'ai bien choisi titre de ma discussion, c'est vous qui en jugerai :)

Soyez indulgent je suis totalement débutant en terme d'algorithme :?

Je vous expose pourquoi je fais appel a vous :

Je dois déterminer une position x,y avec éventuellement un rayon autour de cette position .

Cette position est déterminé par le croisement de plusieurs cercles (plus ou moins précis le croisement) sachant que je connais la position X,Y de chaque cercles ainsi que leurs rayons.
Il faut savoir qu' il y a parfois dans cet ensemble de cercle, un ou plusieurs cercles qui ne croise pas correctement les autres pour déterminer la zone de convergence.

Dans l'image jointe, on y voit 4 cercles qui convergent vers la zone entouré par le triangle rouge et un 5eme qui lui ne fais qu'entourer complètement la zone en question.

Nota : les cercles sont affichés sous formes d'ellipse car il s'agit d'une projection géographique (le cercle se retrouve écraser de par cette projection)

Le but de l'algo que je cherche est donc de déterminer la position la plus probable de convergence des cercles, il y aura toujours au minimum 3 cercles et au maximum 7 cercles.

J'espère avoir exposé mon problème correctement, je suis quasiment sur que c'est très simple, mais je ne sais même pas par quel bout commencer ni quoi taper dans google pour faire une recherche :D

Citation:

---

Envoyé par timeout92

Le but de l'algo que je cherche est donc de déterminer la position la plus probable de convergence des cercles, il y aura toujours au minimum 3 cercles et au maximum 7 cercles.

---

Il y a donc au maximum 42 points d'intersections.

Le point recherché minimise la distance jusqu'a ces 42 intersections, ou du moins a une importante partie de ces 42 intersections. Je vois donc bien un algo de type Ransac.

Il est possible qu'il n'y ai aucune intersection, dans le pire des cas (je ne l'ai pas encore eu , mais c'est possible) petit cercle dans d'autre plus grand etc...

Il faut que l'algo soit capable de déterminer ou ils auraient du se croiser.

J'ai regardé RANSAC , effectivement ça a l'air intéressant par contre je ne sais pas par quel bout l'attraper :) pour l'implémentation, suis plutôt mal a l'aise avec les pseudocodes :?

J'ai téléchargé la RANSAC toolbox pour Matlab je regarderai ça demain au boulot, mais si une bonne âme veut bien me donner une piste (lien vers une implémentation par exemple)
Je vais encore regarder si j'en trouve sur le NET

En tout cas merci Pseudocode pour ta rapide réponse :)

Moi à ta place j'utiliserai une méthode basée image. Sur la pièce jointe on voit bien que la zone recherche est celle qui concentre le plus de pixels foncés. Il suffirait juste de réduire la taille de l'image d'un facteur dépendant de la tolérance voulue, puis de chercher le pixel le plus foncé (ou le plus clair si on dessine les ellipses en blanc sur fond noir).

Attention en dessinant les ellipses de bien avoir un comportement d'accumulation : si deux ellipses passent par le même pixel il faut que sa valeur soit plus élevée que s'il n'y en a qu'une. Cela peut se gérer soit par la transparence (comme sur l'image jointe) ou, mieux je pense, en traitant l'image comme un accumulateur (on commence avec tout les pixels à zéro puis on fait +1 à chaque pixels tracé).

Chercher le point qui minimise la somme des distances (ou peut-etre meme mieux, des carres des distances) aux ellipses?

(Ca ressemble aux calculs qui doivent etre fait pour determiner la position par GPS -- chercher une reference sur ces calculs pourrait aider).

sinon se tourner vers les maths.

Il faut trouver le point commun aux cercles (ellipses) d'équations

X^2/a1^2 + Y^2/b1^2 = 1
....

On aura donc une matrice, dont le début du calcul du déterminant déterminera si il y a intersection ou non.



Sinon, en procédant de proche en proche, en faisant de la "concaténation" de polygones : ajouter cercle1 et cercle2 : en déduire le polygone. Trouver éventuellement les points d'intersections. Itérer.

Je me suis tourne vers les maths , je determine tous les points d'intersections pour l'ensemble des ellipses. Maintenant il faut que je détermine la zone qui correspond le mieux a la zone de convergence des cercles.

Mon souci c'est de pouvoir prendre en compte les cas aberant :(