Discussion :

[ToTo13]

Bonjour,

je souhaiterai savoir si quelqu'un sait comment on peut calculer le plus petit disque circonscrit d'une forme quelconque.

- Par quelconque, j'entend non convexe.

- ce n'est pas le milieu du diamètre (j'ai testé).


Merci par avance...

[macumba]

Je ne sais pas si c'est ca que tu cherches car ca me parait un peu trop simple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
   form1.Canvas.Ellipse(0,0,ClientWidth,clientHeight);
   form1.Canvas.Ellipse(0,0,Min(ClientWidth,ClientHeight),Min(ClientWidth,ClientHeight));

Edit : Arf ca y est j'ai compris avec les posts qui suivent...

[PRomu@ld]

En fait j'utiliserai la méthode pour calculer une bounding sphere (méthode donnée graphics gems) , je ne sais pas si c'est la plus précise et te donnera forcément le plus petit, mais c'est assez efficace.

En gros l'algo c'est ça : tu cherches la paire de point la plus éloignée, ça devient ton premier diamètre. Ensuite, tu passes tous les points et tu regardes s'ils sont dedans ou pas. S'ils sont dedans, OK, sinon, tu met à jour à la fois le centre et le diamètre.

Si tu veux le code :
http://www.acm.org/pubs/tog/Graphics.../BoundSphere.c

[Zavonen]

Voici une méthode simple qui donne une solution mais il ne s'agit pas d'une optimisation.
Déterminer l'isobarycentre G du système de points (centre de gravité). déterminer le point M qui se trouve le plus loin de G. Le cercle de rayon MG et de centre G contient tout le monde.
C'est sûr que pour 3 points c'est meilleur que le cercle circonscrit "classique", mais c'est moins bon que le cercle centré sur le plus grand côté.
J'ai cependant l'intuition qu'on n'est pas très loin de la solution.
Additif ....
Non finalement, ce n'est pas une bonne idée ... Quand tous les points sauf un sont concentrés le résultat est absurde.

[souviron34]

regarde dans Graphics Gems la première étape de la triangulation (Delaunay) (par exemple méthode incrémentale).

ça doit pouvoir être une bonne base...

[ToTo13]

Bonjour,

merci pour ces réponses, faisons en le tri :
- Zavonen: tu as trouvé toi même le contre exemple. J'y avais pensé et je pense que le centre du cercle que je cherche doit se trouver sur le segment MG.
- Promuald: mettre a jour oui, mais comment ? De plus, je vais devoir appliquer cet algorithme en 3D sur des volumes et j'ai un nombre de points de l'ordre du million très souvent. Je peux réduire le nombre de points en ne prenant que ceux qui font parti de mon enveloppe convexe.
- Souviron: pourrais tu me donner quelques explications supplémentaires ?

Merci à tous...