Cercle enveloppe d'un nuage fini de n points

[André]

Bonjour !
Je me pose des questions sur un problème simple.
Soit un nuage fini de n points dont on connaît les coordonnées cartésiennes. On souhaite déterminer le cercle (coordonnées cartésiennes du centre et rayon) enveloppe de ce nuage, c'est-à-dire le plus petit cercle qui englobe ses n points.
Une personne "lambda" répondrait qu'il suffit de déterminer les 2 points du nuage les plus éloignés. Ils constituent alors le diamètre du cercle enveloppe. C'est évidemment une erreur classique !
Je cherche la méthode LA PLUS RAPIDE pour résoudre ce problème (utile pour programmer un algorithme très rapide).
Par exemple, une méthode serait de calculer les longueurs de toutes les pairs de points, de sélectionner la pair la plus longue, de déterminer le cercle dont le diamètre est effectivement cette pair et de vérifier qu'il contient bien tous les points. Si c'est le cas, il est bien le cercle enveloppe recherché. Sinon, le cercle enveloppe passe NECESSAIREMENT par trois points. Dans ce cas alors on doit déterminer tous les triplets possible de points et calculer le cercle circonscrit au triangle qu'ils constituent ; en ne conservant que les cercles qui contiennent tous les autres points, le cercle enveloppe est celui qui a le plus petit rayon.
Cette méthode est TRES simple, mais elle peut s'avérer LONGUE. Je suis persuadé qu'il y en a de plus rapides !
A vous de jouer !
Merci !

[Chimerade]

Je propose :

Tu calcules C l'isobarycentre de tes points. Puis la distance de tous tes points à C. Soit L le plus éloigné. Tu vas définir un point variable D situé sur CL, défini par , x variant de 0 à 1, le point D va décrire CL. Pour chaque point de ton nuage, tu vas déterminer la valeur de x pour laquelle le cercle de centre D et de rayon DL passera par ce point. Et tu vas choisir le point E parmi ces points comme celui qui donne le plus petit x. Soit N le milieu de EL. Enfin, tu vas faire évoluer ton cercle à partir de la position obtenue, cercle passant par E et L, en modélisant à nouveau l'équation de ton cercle par une variable y qui repèrera le centre d'un cercle variable passant par E et L : . Et tu calculeras pour tous les autres points la valeur de y pour laquelle le cercle variable passera par ce point. Et tu prendras la plus grande valeur de y.

Tu dois ainsi faire trois opérations, en n (si n est le nombre de tes points), et non en n² comme ton premier algorithme. Ca devrait aller vite.

[cesar]

Je propose :

Tu calcules C l'isobarycentre de tes points.
.

pourquoi ne pas dire "la moyenne" en X et Y tout simplement ?

[Chimerade]

pourquoi ne pas dire "la moyenne" en X et Y tout simplement ?

Par pure paresse ! Ça va plus vite de dire isobarycentre que de dire "le point dont l'abscisse est la moyenne des X et dont l'ordonnée est la moyenne des ordonnées". J'aurais pu dire "calculer la moyenne des X et la moyenne des Y mais ce ne sont pas ces moyennes qui m'intéressent : c'est le point lui même ! Alors, tu me demande "pourquoi ne pas dire "la moyenne" en X et Y tout simplement ?". Moi, je réponds, pourquoi pas ? En outre André est ingénieur : il sait forcément ce qu'est un isobarycentre !

[cesar]

il existe peut être un moyen qui améliore encore l'algo de Chimerade, sans en changer le principe. on calcule d'abord le barycentre comme le demande chimerade. Ensuite, il faut éliminer les points qui sont "interieurs" au nuage et ne laisser que ceux qui sont "à la peripherie", car le cercle s'appuiera obligatoirement sur eux. Pour cela, il faut proceder en utilisant les algo d'erosion de l'imagerie numerique : ils enlevent une rangée de points de la couche exterieure d'une tache colorée, il ne reste alors que les points interieurs. On sait alors quels sont les points à éliminer et ceux à garder. Si n est grand, cela peut être utile...

[Chimerade]

Ensuite, il faut éliminer les points qui sont "interieurs" au nuage et ne laisser que ceux qui sont "à la peripherie", car le cercle s'appuiera obligatoirement sur eux. Pour cela, il faut proceder en utilisant les algo d'erosion de l'imagerie numerique : ils enlevent une rangée de points de la couche exterieure d'une tache colorée, il ne reste alors que les points interieurs. On sait alors quels sont les points à éliminer et ceux à garder. Si n est grand, cela peut être utile...

Je ne comprends pas très bien la modification que tu proposes. En tout état de cause, les traitements d'image sont d'ordinaire assez coûteux : il y aura, en principe beaucoup plus de pixels que de points. Le temps de traitement dépendra du mode de visualisation des points, c'est-à-dire du nombre de pixels - à haute résolution, cela prendra plus de temps qu'à basse résolution. Cela n'est pas le cas pour ce que je propose : je travaille uniquement sur les coordonnées des points ; le temps de traitement ne dépend donc que du nombre de points, pas de la résolution de l'image utilisée pour les visualiser.
J'ai appliqué mon algorithme en C, qui semble bien marcher. Dans la figure ci-dessous, on voit le point C, isobarycentre des points, le point L, le plus éloigné, qui donne lieu au tracé du cercle de centre C passant par L. Ensuite en faisant se rapprocher le centre du cercle le plus possible de L on s'arrête lorsque le cercle touche le point E. On obtient le cercle bleu clair. En troisième lieu, on fait varier un cercle passant par L et E. On obtient le cercle bleu foncé. Bien sûr, il ne s'agit pas réellement de calculer des cercles : à chaque étape on balaye une fois l'ensemble des points pour déterminer le centre du meilleur cercle de cette étape. L'algorithme est assez rapide tel qu'il est. Pour 1000000 points, j'y passe 0,36 seconde. Pour 100000, ça tombe à 3 centièmes. Et pour 10000 points ça fait moins d'un centième de seconde. Est-ce que ça peut aller ?

[Fract83]

Hello,

Juste pour information, Chimerade, tu as trouve cet algo ou ?

Ou alors, comment t'es venu cette idee d'algo ?

Merci.

Bonne journee.

[Fract83]

Re,

Sinon, andre, cherche ca sur Internet :

"minimum enclosing circle"

C'est la traduction de ton probleme. Tu verras, ca a occupe pas mal de gens !!!

Par contre, ce qui me titille un peu, Chimerade, c'est que je n'ai pas vu ton algo dans les algos en temps lineaire ! Est-tu sur qu'il marche pour toutes les entrees (y compris les entrees degenerees) que tu peux lui fournir ?

Bonne journee.

[Chimerade]

Hello,

Juste pour information, Chimerade, tu as trouve cet algo ou ?

Ou alors, comment t'es venu cette idee d'algo ?

Re,

Sinon, andre, cherche ca sur Internet :

"minimum enclosing circle"

C'est la traduction de ton probleme. Tu verras, ca a occupe pas mal de gens !!!

Par contre, ce qui me titille un peu, Chimerade, c'est que je n'ai pas vu ton algo dans les algos en temps lineaire ! Est-tu sur qu'il marche pour toutes les entrees (y compris les entrees degenerees) que tu peux lui fournir ?

Bonne journee.

De retour après une semaine coupé du monde : un camion avait détruit mes lignes téléphoniques, donc mon accès internet...

Pour répondre à la première question : je n'en sais rien. J'ai pensé à ce que j'aurais fait "à la main" : choisir un centre "plutôt vers le milieu du nuage", alors pourquoi pas le barycentre. Prendre un cercle suffisamment grand pour contenir tous les points et le rapetisser peu à peu, il est évident que ça s'arrêtera avec le point le plus éloigné. D'où l'idée de calculer la distance de tous les points à ce centre et de garder le plus éloigné ! Ensuite continuer à rapetisser le cercle en m'appuyant sur ce point éloigné, et en forçant donc le centre à s'en rapprocher. Il est à nouveau évident que ça s'arrêtera dès que je rencontre un deuxième point. D'où l'idée de calculer les centres de tous les cercles obtenus avec ces contraintes et avec chacun des points restants et choisir le point qui donne le centre le plus éloigné. Enfin, pour essayer de rapetisser encore le cercle, il fallait que je m'appuie sur les deux premiers points...

Quant à la deuxième question, la réponse est non !
J'ai commencé l'étude de ce problème le 21 Novembre à 13 H 45, j'ai trouvé cette manière de faire, je l'ai "proposée" à 14 H 40 le même jour (voir mon post). Depuis je n'y ai pas davantage réfléchis : je me suis contenté de réaliser ce que je proposais, histoire de vérifier que ça marchait, et que c'était rapide... La raison pour laquelle tu n'as pas vu mon algo dans les algos en temps lineaire, c'est peut-être qu'il n'était pas connu de ta liste, ou que mon algo n'est pas "en temps linéaire"...Je pense qu'il est linéaire, en théorie, et pour l'avoir implémenté et et en avoir mesuré les performances jusqu'à 1000000 points, mais pas au point de mettre ma tête à couper... Mais, en suis-je sûr ? Non ! Si André doit implémenter cet algorithme sur des milliards de points, faudra voir, mais si c'est moins d'un million, je pense qu'il n'y a pas lieu de se casser la tête davantage...

P.S. Qu'appelles-tu des entrées "dégénérées" ?

[Fract83]

Hello,

Merci pour tes reponses... C'est impressionnant je trouve !

Un exemple d'une entree degeneree : une liste de points tous alignes...

Un autre exemple, quoi que peut etre moins intuitif : une liste de points sur un meme cercle...

Il doit y avoir d'autres cas, mais j'ai la flemme d'aller voir sur les sites retournes par Google

Bonne journee.

[Chimerade]

Un exemple d'une entree degeneree : une liste de points tous alignes...

Ah d'accord ! Pour ce cas là je pense que mon algo aurait des problèmes. En effet, des points tous alignés, ça a de fortes chances de ne pas exister "informatiquement parlant" (à cause des approximations au niveau des coordonnées inhérentes à toute approximation digitale d'un réel). Pour cette raison, il n'est pas évident de faire tourner correctement la phase 3 de mon algorithme, car pour un poil à droite ou un poil à gauche, le cercle peut se retrouver d'un côté ou de l'autre du segment défini par les deux premiers points et il n'est pas évident de s'arranger pour que ça marche à tous les coups.

Un autre exemple, quoi que peut etre moins intuitif : une liste de points sur un meme cercle...

Par contre dans ce cas-là je ne vois pas de nouveau problème : ça devrait marcher.