Discussion :

[farfouch00]

Bonjour tout le monde.
Je cherche l'algorithme qui retourne les paramètres a et b de l'ovale de Cassini minimum englobant une image.
Rappel : Un ovale de Cassini de centre q1 et q2 (q1q2=a en terme de distance) et de rayon b est l'ensemble de point p tels que : pq1.pq2=b²=cte, autrement dit, c'est l'ensemble de points tels que le produit des distances entre ces point et les centres de l'ovale est constant.
Merci et bonne journée!

[pseudocode]

Je cherche l'algorithme qui retourne les paramètres a et b de l'ovale de Cassini minimum englobant une image.

Un oval engloblant une image rectangulaire (= englobant un rectangle), ou alors englobant une forme quelconque dans une image (= englobant un blob) ?

[farfouch00]

Bonjour,
Un ovale englobant un rectangle, c'est simple, c'est le cercle circonscrit...
L'ovale de Cassini englobe une forme quelconque... Par exemple, polygone à 10cotes ... :S

[farfouch00]

PS : La forme ou le polygone que j'essaie de traiter sont déjà isolés et stockés dans des matrices binaires...

[pseudocode]

Bonjour,
Un ovale englobant un rectangle, c'est simple, c'est le cercle circonscrit...

Le cercle est une solution possible. Mais une ellipse, ou un ovale ca "colle" mieux au rectangle, non ?

L'ovale de Cassini englobe une forme quelconque... Par exemple, polygone à 10cotes ... :S

Dans ce cas, on peut commencer par trouver le rectangle qui englobe le mieux la forme, puis trouver l'ovale qui engloble le mieux le rectangle, et finalement réduire le rayon de l'ovale pour "toucher" la forme

[farfouch00]

Parfait,
Mais en fait là j'essaie de trouver le polygone approximatif à la forme, devrais-je forcément trouver le rectangle englobant ce polygone? C'est pas parce que c'est difficile, mais c'est que ca va limiter les performances de mon projet (Je travail sur la reconnaissance de forme, les paramètres a et b seront stockés dans une table de hachage... Bref, il me faut une précision maximum sur ces paramètres...)

Je vous remercie énormément!

[farfouch00]

Rectif : J'ai dit N'IMPORTE QUOI dans ma derniére réponse.
J'ai bien compris ta proposition pseudocode... Je pense que c'est bien ce qu'il me faut!!
Merci encore une fois

[pseudocode]

Mais en fait là j'essaie de trouver le polygone approximatif à la forme

Juste pour ma culture personnelle, c'est quoi le rapport entre l'ovale de Cassini et du polygon-matching ?

[farfouch00]

J'ai oublié de cité deux contraintes...
1) Les centres de l'ovale de Cassini doivent appartenir à la forme en question.
2) Ces centre et le barycentre de la forme doivent étre sur la même droite...

En fait le choix de ces point se fait de la manière suivantes :
____a) Trouver barycentre G de la forme.
____b) Pour tout point P de la forme, trouver le point P' de l'autre coté sur la droite PG.
____c)Garder le couple (P, P') de distance maximale.

Et puis le choix de b est simple a expliquer, c'est le réel qui permet de construire le plus petit ovale englobant la forme.

[farfouch00]

Très intéressante question...
Si on veut appliquer l'algorithme du poste précédent sur la forme, ça sera très couteux en terme de temps d'exécution. Alors les points sur lesquels je ferais le traitement seront les coins du polygones...