Discussion :

[bebeours]

Bonjour,

Je recherche un algorithme me permettant de calculer le plus grand cercle possible inscrit dans un polygone (défini par l'ensemble de ses sommets x,y), c'est à dire les coordonnées de son centre et son rayon.

Si vous avez des pistes, un lien, une idée ...

Merci pour votre aide.

[alexrtz]

Salut,

Je dirais :
- calculer le barycentre du polygoone
- calculer les distances entre le barycentre et chacun des côtés
- prendre la plus petite
- ce qui fait que tu as le centre et le rayon du cercle

[Kangourou]

Salut,

Une premiere piste : tu pars d'un sommet, et tu suis la bissectrice. pour chaque point de la bissectrice, tu peux tracer un cercle tangent aux deux cotes. Il suffit ensuite de rechercher sur cette bissectrice quel est le plus grand rayon de cercle que l'on peut tracer sans couper un autre cote.

Mais ca ne gere pas tous les cas, par exemple si aucun des trois cotes que touche le plus grand cercle inscrit ne sont consecutifs.

A+

[Kangourou]

re salut

Le probleme est peut-etre beaucoup plus simple si on ne considere que des polygones convexes. Est-ce le cas ?

A+

[bebeours]

Salut,

Je dirais :
- calculer le barycentre du polygoone
- calculer les distances entre le barycentre et chacun des côtés
- prendre la plus petite
- ce qui fait que tu as le centre et le rayon du cercle

Ca ne fonctionnera pas car mes polygones peuvent être concaves, dans ce cas il est possible que le barycentre (appelé aussi centroid du polygone) soit à l'extérieur du polygone !

[bebeours]

re salut

Le probleme est peut-etre beaucoup plus simple si on ne considere que des polygones convexes. Est-ce le cas ?

A+

Hélas mes polygones peuvent être concaves, ils le sont d'ailleurs presque tous !

Les solutions que vous proposez me paraissent très couteuses en temps de calcul. Enfin il semble qu'il n'existe pas de méthode déterministe pour résoudre ce problème c'est pourquoi il faudrait que je trouve une méthode stochastique, afin de calculer une solution optimale. Le problème est en fait beaucoup plus complexe qu'il en a l'air.

Merci pour vos réflexions.

[Kangourou]

Salut,

il y a peut etre une solution 'propre", en passant par le diagramme de Voronoi du polygone.
Commencons par un ensemble de points : le diagramme de Voronoi est un ensemble de segments de droites (ou eventuellement de demi-droites) qui sont chacun equidistant a 2 points. la ou 3 aretes du diagramme, on a un cercle qui passe par 3 points, et le plus grand cercle passant par 3 points aura son centre sur un sommet du diagramme.

Maintenant, il est possible de tracer la meme chose pour des ensembles de points et de segments et donc on peut tracer le diagramme de Voronoi d'un polygone. A priori, en regardant tous les sommets du diagramme, on doit pouvoir trouver le plus grand cercle inscrit.

cf lien pour une implementation de Voronoi (a refaire, ca doit etre long...) :
http://www.cosy.sbg.ac.at/~held/proj...oni/vroni.html

A+, et bon courage ...

[bebeours]

Effectivement je pense que c'est une bonne piste. Merci pour le lien, je ne savais pas qu'on pouvait appliquer Voronoi sur des polygones.