trouver rapidement un cercle passant par n points ...
Laurent B.
je cherche un moyen le plus rapide possible pour trouver un cercle passant
par le plus grand nombre de n points donnés (max =360 pts). (1 point = 1°)
le resultat que je dois obtenir est le centre ,le rayon et le taux de
reussite de recherche de ce cercle (0 à 100%)
(si tous les points sont sur le cercle 100%, si tous les points sont
dispersés et incohérents une valeur proche de 0%).
quelques idées ou suggestions ?
actuellement, j'effectue les calculs de n/3 cercles en prenant 3 points
opposés (triangulairement)
et detecte le rayon et centre le plus redondant dans la liste des cercles
calculés.
merci de vos remarques.
Benoit Rivet
> Bonjour.
>
> je cherche un moyen le plus rapide possible pour trouver un cercle passant
> par le plus grand nombre de n points donnés (max =360 pts). (1 point = 1°)
> le resultat que je dois obtenir est le centre ,le rayon et le taux de
> reussite de recherche de ce cercle (0 à 100%)
> (si tous les points sont sur le cercle 100%, si tous les points sont
> dispersés et incohérents une valeur proche de 0%).
>
> quelques idées ou suggestions ?
Le plus élémentaire :
- prendre pour centre du cercle O le centre de gravité du nuage de
points,
- et pour rayon r, la moyenne quadratique des distances au centre de
gravité : r^2 = moyenne de OM^2.
Le taux de dispersion S peut ensuite être calculé comme :
S^4 = moyenne de ( (OM^2 - r^2)^2 ) / r^4
--
Benoît RIVET
Arthur B.
"Laurent B." <l.ba...@prodel-techno.fr> a écrit dans le message de news:
at75gk$19g2$1...@feed.teaser.net...
> Bonjour.
Bonjour. Tu cherches deux choses :
- 1 rayon r
- 1 centre (x,y)
Tu veux par exemple minimiser
Somme ( dist( A_i, cercle)² )
Cette fonction dépend de r,x,y
Tu peux rechercher le minimum de cette fonction
par des méthodes classiques.
Didier Lauwaert
> Bonjour.
>
> je cherche un moyen le plus rapide possible pour trouver un cercle passant
> par le plus grand nombre de n points donnés (max =360 pts). (1 point = 1°)
> le resultat que je dois obtenir est le centre ,le rayon et le taux de
> reussite de recherche de ce cercle (0 à 100%)
> (si tous les points sont sur le cercle 100%, si tous les points sont
> dispersés et incohérents une valeur proche de 0%).
>
> quelques idées ou suggestions ?
Les moindres carrés ça me semble pas mal.
Tu cherche la formule donnant le carré de la distance d'un point
à un cercle quelconque.
Tu fais la somme.
Tu dérives par rapport aux trois composantes du cercle x,y,R.
Tu égales à zéro.
Et tu obtiens un système que tu résouds.
Ce ne devrait pas être mortel (pour une droite c'est élémentaire,
pour un cercle ça doit être quelque peu plus compliqué).
Il reste à programmer les équations ainsi obtenues.
Reste à convertir l'écart quadratique E en %
avec un truc du genre : K * 100 /(E + K) ?
Bon courage,
La Terre
Ca dépend si tu cherches le cercle passant au plus pres de tous les points
ou le cercle passant exactement par un maximum de points ce qui n'est pas du
tout la meme chose
Le cercle qui passe au plus pres de l'ensemble peu tres bien ne passer
exactement par aucun points
Alors quelle est le motif de cette recherche de cercle?
--
(¯`·.¸-= La Terre =-¸.·´¯)
aupetit
tu auras un cercle qui minimise la somme des écarts quadratiques...
donc qui peut ne passer par aucun des points.
Exemple si tu prends 359 points sur le cercle et le 360e légèrement décalé,
il y a de fortes chances que le cercle ne passe par aucun des points
bien qu'il soit très proche des 359 points cocycliques.
Si tu cherche la solution qui maximise le nombre de points "appartenant"
au cercle (et pas simplement les plus "proches" du cercle),
l'approche par minimisation au sens des moindres carrés
me paraît inadaptée. Ton pb ressemble plus à un problème de combinatoire
(recherche exhaustive de toutes les combinaisons possibles)
et là il faut voir avec les gens d'IA pour élaguer l'arbre de
recherche et éviter l'énumération exhaustive.
Michaël
Laurent B.
en fait le pb est le suivant je dispose d'un bitmap généré par une
acquisition numérique en 256 gris
pour une zone donnée de l'image ou devrait (pas sur ... d'ou le pourcentage)
se trouver un cercle,
j'extrais des points signicatifs. (valeus entieres de coordonnées puisque
précision en pixels)
à partir de ces points, en effet ce que je recherche c'est le cercle
passant par le plus grand nombre de points.
c'est pour cela que j'effectuais (pas tous! ) les combinatoires 3 à 3.
mais déja la réponse de Benoit
"prendre pour centre du cercle O le centre de gravité du nuage de points"
me donne un direction pour accelerer mes calculs.
... a suivre ....
Ilan Vardi
>
> je cherche un moyen le plus rapide possible pour trouver un cercle passant
> par le plus grand nombre de n points donnés (max =360 pts). (1 point = 1°)
> le resultat que je dois obtenir est le centre ,le rayon et le taux de
> reussite de recherche de ce cercle (0 à 100%)
> (si tous les points sont sur le cercle 100%, si tous les points sont
> dispersés et incohérents une valeur proche de 0%).
>
> quelques idées ou suggestions ?
S'il y a plus de deux points distincts et il sont tous sur une ligne droite, il
n'y aura aucune reponse possible. Cette singularite a l'effet que dans les
cas pratiques ou tes points on environ la forme d'une ligne droite,
tout algorithme ne prenant pas ceci en compte va echouer.
La seule maniere de resoudre ce probleme est de definir une ligne droite
comme un cas particulier d'un cercle, ce qui est vrai.
-ilan
Thomas Baruchel
>La seule maniere de resoudre ce probleme est de definir une ligne droite
>comme un cas particulier d'un cercle, ce qui est vrai.
Que veux-tu dire ?
--
Deux choses remplissent le coeur d'une admiration et d'une vénération
toujours nouvelles et toujours croissantes, à mesure que la réflexion
s'y attache et s'y applique : le ciel étoilé au-dessus de moi et la loi
morale en moi. (Emmanuel Kant)
Denis Feldmann
> Le 11 Dec 2002 10:35:30 -0800, Ilan Vardi a écrit :
>> La seule maniere de resoudre ce probleme est de definir une ligne
>> droite comme un cas particulier d'un cercle, ce qui est vrai.
>
> Que veux-tu dire ?
Pour parodier un auteur que tu aimes bien : " La droite est un cercle dont
le rayon est infini et le centre n'est nulle part..."
Thomas Baruchel
>Pour parodier un auteur que tu aimes bien : " La droite est un cercle dont
>le rayon est infini et le centre n'est nulle part..."
En effet, d'abord un tel cercle ne correspond manifestement plus à
aucune définition, que cette dernière repose sur une équation x²+y²=r,
qu'elle repose sur des considérations géométriques (l'ensemble des points
situés à une même distance du centre), etc. Ne confond-on pas la limite
et la figure même ? d'autant qu'un tel cercle serait inconstructible.
En outre, on devrait pouvoir donner d'autres points du plan appartenant aussi
au cercle sans appartenir à la droite, tout en considérant que la droite
passe par eux :-(
Mais de même que la limite est fréquemment d'un autre ordre que ce dont elle
est la limite, n'y a-t-il pas un abus à parler ici de cercle ?
Mehdi Tibouchi
> J'avais bien pensé à cela, mais y a-t-il là plus qu'un jeu de l'esprit ?
> En effet, d'abord un tel cercle ne correspond manifestement plus à
> aucune définition, que cette dernière repose sur une équation x"+y"=r,
> qu'elle repose sur des considérations géométriques (l'ensemble des points
> situés à une même distance du centre), etc.
Une équation de cercle, en général, est de la forme :
a(x^2 + y^2) + bx + cy + d = 0 (*)
et une droite correspond alors au cas particulier a = 0. Cette façon de
voir est effectivement intéressante, parce qu'elle permet de mettre de
la structure sur « l'espace des cercles » (précisément, de l'identifier
à un espace projectif). Deux cercles sont identiques si et seulement
s'ils ont des équations (*) avec des coefficients proportionnels, et
l'on peut donc convenir que les cercles sont les quadruplets (a,b,c,d)
non nuls, à proportionnalité près (on note (a:b:c:d) une classe de
proportionnalité).
On remarque alors que beaucoup de transformations naturelles sur les
cercles s'expriment de manière très naturelle sur les (a:b:c:d). En
particulier, l'inversion géométrique a ici une allure vraiment
alléchante : c'est essentiellement (a:b:c:d) -> (d:b:c:a). On a alors
immédiatement, par exemple, la propriété que l'inversion échange les
cercles passant par l'origine et les droites (ce qui suggère que,
quelque part, il faut regarder les droites comme des cercles).
C'est aussi dans ce cadre que l'on récrit proprement la théorie
classique des faisceaux de cercles (qui apparaît alors comme un cas très
particulier de l'étude des sous-espaces projectifs, autrement dit, de
l'algèbre linéaire élémentaire).
--
M. Tibouchi <med...@alussinan.org>
que la théorie des faisceaux de cercles n'a rien à voir avec la théorie
des faisceaux...
Ilan Vardi
> Le 11 Dec 2002 10:35:30 -0800, Ilan Vardi a écrit :
> >La seule maniere de resoudre ce probleme est de definir une ligne droite
> >comme un cas particulier d'un cercle, ce qui est vrai.
>
> Que veux-tu dire ?
Une premiere reponse est exactement le phenomene que j'ai cite, c'est-a-dire,
que l'approximation par un cercle echoue pour une ligne droite. La raison
est exactement celle mentionnee par Denis Feldmann.
Une facon plus explicite de le voir est par les transformation par "inversion"
par rapport a un cercle.
Dans une inversion, un cercle est transforme en un cercle ou une ligne
droite, donc cercles et lignes droites deviennent equivalentes.
Par exemple, le theoreme qu'il existe un cercle qui touche trois
autres cercles qui se touchent deux par deux devient trivial quand on
inverti pour que les trois cercles deviennent deux lignes droites paralleles
et un cercle qui touche les deux lignes. Ici "touche" veut dire qu'il existe
un seul point d'intersection et deux lignes droites se touchent si elles
sont paralleles (se touchent a l'infini). Pour plein d'exemples, voir le
livre "Redecouvrons la geometrie" par Coxeter et Greitzer, ou n'importe
quel livre de geometrie ecrit avant 1900.
-ilan
aupetit
"Laurent B." wrote:
Une autre possibilité:
si tu te restreint au centre de gravité des points, celui ci est toujours
à l'intérieur de l'enveloppe convexe de tes points, tu ne detecteras pas
de cercle si tous les points cocylciques sont d'un même côté du diamètre
du cercle. De plus, si la répartition de tes points n'est pas
symétrique autour du cercle, le CDG sera peut-etre assez élloigné du centre.
Idée pour améliorer l'approche initiale du centre: calculer les points
d'intersection
de plusieurs médiatrices issues de différents couples de points, puis prendre le
CDG de ces points d'intersection comme point de départ.
Si tous les point sont cocycliques, toutes les médiatrices se coupent au même
endroit centre du cercle.
Michaël
Ilan Vardi
> Par exemple, le theoreme qu'il existe un cercle qui touche trois
> autres cercles qui se touchent deux par deux devient trivial quand on
> inverti pour que les trois cercles deviennent deux lignes droites paralleles
> et un cercle qui touche les deux lignes.
Je voulais dire que l'on peut toujours trouver une inversion qui renvoie
a ce cas trivial. Voici les idees :
D'abord, une inversion est essentiellement la fonction x -> 1/x sur R,
c'est l'inversion par rapport au cercle d'unite. Tout autre inversion
est simplement l'analogue.
Deux proprietes importantes de l'inversion sont :
1. Tout cercle ou ligne droite qui ne passe pas par le centre d'inversion
devient un cercle.
2. Tout cercle qui passe par le centre d'inversion devient une ligne droite.
Donc, si on a trois cercles qui se touchent deux a deux, on peut faire une
inversion par rapport a un cercle qui a son centre a un des points de
contact. Les regles 1 et 2 demontrent que les trois cercles originaux sont
transformes en deux lignes droites paralleles et un cercle qui touche
les deux lignes. Le cercle qui touche ces trois objects est trivial,
c'est simplement un cercle decale entre les deux lignes paralleles.
On fait l'inverse de l'inversion, et l'image du nouveau cercle est la solution
du probleme original.
-ilan
Laurent B.
centre dans mon cas.
en effet je rayonne autour d'un point par pas de x degrés. et je suppose que
ce point est dans le cercle cherché.
merci.
Laurent.
"aupetit" <aup...@dase.bruyeres.cea.fr> a écrit dans le message de news:
3DF84862...@dase.bruyeres.cea.fr...
Laurent B.
mais un peu de philosophie est bienvenue dans ce chaotique monde de brutes.
ce qui me fait penser qu'un cercle est un ellipse qui a bien tourné.
Laurent.
*.h.e.n.d.r.i.X
salut voici une solution bien tordue je sais pas ce qu elle vaut lol
sur un bitmap en niveau de gris tu trace un maximum de mediatrices de
couple de point du cercle à trouver,
mais quand tu trace les lignes au lieu d'utiliser une valeur fixe, tu
augmentes la valeur des pixels de 1, au croisement tu va obtenir des
superpositions , donc des valeur de pixels plus forte...
ensuite tu fais un barycentre des pixels pondéré par leur valeur... en
ne prenant par exemple que les valeur plus grande que 2...
c tordu et je sais sauf qu avec un peut de chance, tracer des lignes de
cette manière sur un bitmap est géré en hard par certaine carte graphique...
david b. (gueule de bois ce matin)
*.h.e.n.d.r.i.X
si le coup de la carte video est trop tordu hihi...
on peut bien sur calculer les intersections des mediatrices est tracer
les points correspondant en augmentant de 1 la valeur du pixel...
puis faire le barycentre pondéré...
ps2 : ca va mieux la gueule de bois...
*.h.e.n.d.r.i.X
ou alors au lieu du bitmap... un arbre à 4 direction (sud-ouest,
sud-est, nord-ouest, nord-est) pour maintenir une liste des
intersections... :)
pour le calcul du barycentre ça devrait aller plus vite... :p
Laurent B.
tordue ou pas, c'est comme ça qu'on avance mais le coup de la mediatrice est
bon pour trouver le centre.
c'est en fait un dérivé de la fonction de Hough que tu utilises .(avec un
accumulateur).
mais en plus simple, je vais l'experimenter ..
ça ne me ferait que n/2 calculs de droite + remplissage de l'accu. +
reherche du maxi pour trouver le centre.
le rayon devrait pouvoir se faire de la meme maniere sachant que mon bitmap
n'est pas infini......
merci pour cette piste...
Laurent
JAGUTS
Salut.
Moi j'opérerais par estimation statistique.
L'équation d'un cercle étant (X-Xc)²+(Y-Yc)²=r, en développant, à
partir des coordonnées X,Y et de la somme X²+Y² de chaque point, on
peut faire une régression multiple et avoir une première estimation de
(Xc,Yc) (les coordonnées du centre) et du rayon r. le R² de la
régression indique si l'on est proche ou pas de la forme d'un cercle.
Il faut ensuite retirer les points les plus éloignés du cercle calculé
(1 par 1, ou bien les 5% des plus éloignés, ou encore en fonction d'un
point d'inflection de la courbe de distance décroissante). Par
itération, on devrait converger vers le cercle.
Le problème se pose si la forme n'est pas un cercle, particulièrement
si elle contient plusieurs formes de cercles : soit l'algorithme ne
converge pas, soit il ne converge qu'avec très peu de points. Il
faudrait peut être auparavant effectuer une classification
hiérarchique des points avec la distance "minimum" pour repérer des
chaînages de points entre eux, lancer l'algorithme sur les chaînes et
regrouper celles qui ont des références (Xc,Yc,r) proches.
Compte tenu du faible nombre de points, ces algorithmes devraient
tourner assez rapidement.
A plus
*.h.e.n.d.r.i.X
lol, faut que tu expliques
mais si j'ai bien compris le probleme le cercle peut ne pas etre
completement bien scanné et les points ne sont pas forcément distribué
de manière homogène autour du centre...
est ce que ça invalide l'approche statistique ?
JAGUTS
Je suis désolé, c'est peut-être un peu compliqué quand on ne connaît
pas. Et je ne connais pas lol. Je vais essayer d'être clair et simple.
La régression "simple" cherche la ligne droite qui passe au milieu
d'une série de points. La modélisation est aX + b = Y + e. X et Y sont
les coordonnées des points. a et b sont les coefficients du modèle (b
est la constante). e est l'écart entre la valeur calculée par le
modèle et la valeur réelle (on appele cela les résidus). On suppose
que les résidus sont répartis aléatoirement autour de la valeur
calculée (ils peuvent être dus à des imprécisions de mesure par
exemple).
Le R² du modèle indique l'importance du modèle par rapport à
l'importance des résidus. Si tous les points sont sur la droite (les
résidus sont tous nuls), le R² vaut 1. Si le modèle est mauvais (les
résidus sont importants), le R² est proche de 0.
La régression multiple est simplement l'extension du modèle à
plusieurs variables : a1X1 + a2X2 + ... +b = Y + e.
Lors du scan du cercle, tu peux te retrouver avec plusieurs problèmes
d'erreurs de mesure. L'épaisseur du trait peut être de plusieurs
pixels, ou bien en dessous d'un pixel. Le seuillage est alors très
délicat. Une fois seuillée on peut transformer l'image en série de
points (X,Y) (on ne prend que les points noirs).
Pour un cercle, l'équation est (X-Xc)² + (Y-Xc)² = r. (Xc,Yc) sont les
coordonnées du centre, et r le rayon. En développant, on doit pouvoir
aboutir à une équation du genre a(X²+Y²) + bX +c = Y, avec a, b et c
s'exprimant en fonction de Xc, Yc et r (je n'ai pas pris le temps de
développer, mais ça n'est pas très compliqué).
On calcule les coefficients de la régression de Y par rapport à
(X²+Y²) et X, et on en déduit les coordonnées du centre et le rayon.
En recalculant le Y issu du modèle pour chaque point, on en déduit
l'écart avec le Y réel (la valeur des e). On peut ainsi écarter les
points les plus éloignés du cercle calculé, et relancer la régression
sur les points restant.
Pour les algorithmes de régression, je ne peux pas te donner de
référence car j'utilise des logiciels qui intègrent cela en standard.
Avec 2 variables, ça ne devrait pas être très compliqué. Demande à
d'autres programmeurs.
Mais avant de te lancer en programmation, essaye peut-être sous Excel
(ou autre tableur proposant la régression multiple). Traduit tes
points seuillés en coordonnées (X,Y), passe les dans une feuille de
calcul et teste l'ajustement avec les fonctions existantes.
J'espère que c'est assez clair.
Eventuellement, envoie-moi une série de (X,Y), et j'essayerai de faire
la modélisation sous Excel pour voir ce que ça donne.
Bon courage.
David Berlioz
je vais relire tout ça trankillou avec un petit tas de feuille et un
crayon ( et une gomme )
ps : lol = lots of laugh
mdr en english koi
Laurent B.
ouaaaah, à première vue, ça a l'air la methode qui'il me faut.
pas trop de tour de boucle ...
pas trop de calculs complexes ....
...
merci pour toutes ces infos. et à tous pour la contribution.
dès que j'ai 5 mn ,j'essaies de coder tout ça (C++)
et si reussite, je vous en fait profiter....
Laurent.
PS:
l'image vient en fait d'une caméra N&B 640*480.
et les temps de calculs se doivent d'etre le + court possible.