Discussion :

[olibara]

Bonjour

Existe-t-il une methode connue pour determiner le centre et le reyon du plus grand cercle inscrit d'un polygone irregulier (considerant que le cercle ne DOIT PAS etre tangeant a tous les cotés)

?

Merci de votre aide

[FR119492]

Salut!
Ton polygone est-il nécessairement convexe? Si oui, ça ne doit pas être trop compliqué.
Jean-Marc Blanc

[olibara]

Bonjour

Merci de ta réponse

Non : il n'est pas forcément convexe ce sont des polygones representant des contours de commune et j'aimerais pouvoir y dessiner le cercle le plus grand possible sans deborder de la commune (exemple joint)

Et le centre de gravité n'est evidemment pas la bonne solution :

Prenons un cas extreme d'un polygone formé de deux losanges relies par la pointe le cercle se trouvera dans un des deux losange mais certainement pas au centre de gravité au milieu des deux

[souviron34]

Il suffit de faire le début d'une triangulation de Delaunay..

Trouver l'enveloppe convexe.

Et démarrer la triangulation en s'arrêtant à la première étape (polygone convexe découpé en triangles).

Déjà le problème se simplifie énormément.

Là, plusieurs possibilités..

[olibara]

Bonjour

Merci

Bon je vais relire ma litérature sur la triangulation de Delaunay !
Et peut etre Voronoi ? ou il n'a rien avoir ici ?

En tout cas je n'ai pas encore fait ca, je vois a quoi ca ressemble mais je n'en connais pas du tout l'algorithme. Je vais chercher de la doc et essayer de trouver des bouts de codes existant,

[ToTo13]

Bonjour,

si tu travailles sur des images, il te suffit de calculer une carte de distance.

[olibara]

si tu travailles sur des images, il te suffit de calculer une carte de distance.

Excuse moi mais ce que tu propose n'est pas tres claire ..
Quelle carte de distances ?
Les distances de quoi a quoi ?

Je rappele que le but est de determiner le centre et le rayon du plus grand cercle inscriptible d'un polygonie IRREGULIER

Pour illustrer a nouveau je joint 4 polygones representatifs de cas possibles

Merci de votre aide

[ToTo13]

Bonjour,

regarde dans le forum "Traitement d'images" et dans la rubrique "Contribuez". On parle dedans de :
- carte de distances.
- distances de Chamfrein.
Tu trouveras ainsi le point le plus éloigné de la frontière et donc le centre du plus grand disque inscrit.

[olibara]

Merci

J'ai trouvé ce lien

http://www.developpez.net/forums/d47...ances-chamfer/

Je ne sais pas si c'est celui auquel tu pensais mais je vait analyser

[Kangourou]

Salut,

Si je me souviens bien, le (ou les) centre du cercle inscrit d'un polygone se situent sur un des sommets du squelette, ou axe médian du polygone.

La carte des distances permet de retrouver ce squelette, mais nécessite de discrétiser l'espace, vu que la méthode marche sur des images. Mais bon, ça marche !

Il est normalement possible de sortir l'axe médian d'un polygone sous forme de graphe (sommets=points, arêtes=segments de droites ou arcs de parabole). L'avantage est que la réponse fournie est exacte. Il faut chercher du côté des axes médians et des squelettes de polygones.
http://fr.wikipedia.org/wiki/Squelettisation
http://www.cs.unc.edu/~snoeyink/papers/medaxis.ps.gz

bon courage...

[olibara]

Merci Kangourou

J'intègre tes suggestions dans mes recherches

[ToTo13]

Bonjour,

je suis d'accord sur le principe avec Kangourou, mais le problème c'est que l'on dispose généralement soit :
- d'une représentation des polygones dans un espace discret.
- d'une série de coordonnées de sommet.
Dans le deuxième cas, le calcul du squelette est vraiment pénible.

Pour l'axe médian, lis les travaux d'Eric Rémy.
Pour le squelette, je te conseille de lire ceux de Christophe Lohou.
Avec les cartes de distances, tu peux extraire l'axe médian ou des squelettes ;-).

[olibara]

d'une série de coordonnées de sommet.

Merci ToTo13

Effectivement c'est bien a partir d'une liste de coordonées ordonées que je peux representer mon polygone !

Et dans ce cas quelle est donc la meilleure approche selon toi avant que je ne plonge ?

[ToTo13]

Eurf... j'avoue que je ne connais pas trop ces algos, je fais plutôt de l'imagerie.
J'aurai tendance à regarder du coté de tout ce qui est Algorithme Géométrique.
Regarde donc la thèse dans le premier lien.

[Kangourou]

salut,

effectivement le calcul de l'axe median d'un polygone ne se code pas forcement en une apres-midi...

par contre il y a un bibliotheque de geometrie algorithmique assez connue, qui implemente beaucoup d'algos recents : CGAL
http://www.cgal.org/

Tu as un exemple de squelette de polygone ici:
http://www.cgal.org/Manual/last/doc_...htSkeleton.png

il y a du menage a faire dans les aretes resultat, mais ca peut peut-etre eviter de tout re-implementer...

A+

[FR119492]

Salut!

le centre et le reyon du plus grand cercle inscrit

Le plus grand rayon est certes unique. En revanche, le centre ne l'est peut-être pas. Que penses-tu faire en cas de solutions multiples?
Jean-Marc Blanc

[olibara]

Salut FR119492

Je concoit bien que je peux avoir des cas a plusieurs solutions

Voici quelques cas illustratif

Exemple Cas 1 : Mon polygone est un rectangle (1 plus grand rayon et un domaine de centre : un segment sur la mediane
Dans ce cas j'en prends un point au hazard, ce n'est pas important !

Exemple cas 2 : Mon polygone est formé de deux carrés egaux liés par un sommet j'ai deux centres : j'en prends UN

Exemple cas 3 : Mon polygone est formé de deux rectangle lies par un sommet ;-))

Le but est surtout de pouvoir determiner le plus grand rayon et un domaine de centre possibles.