Algorithme de dessin d'un contour de polygone

Bonjour

Je voudrais dessiner le contour d'un polygone qui soit à une distance donnée (Dist) de chacun de ses côtés.

Je trace donc les parallèles et je les raccorde par des arcs de cercle de rayon Dist.
Cette méthode ne fonctionne pas sur les portions concaves du polygone.
Je cherche à résoudre la question mais chaque fois que je crois avoir trouvé une solution, j'ai un cas particulier qui n'est pas résolu.

Mon programme est écrit en Delphi.
Deux polygones exemplatifs sont en pièce jointe.

Merci d'avance

Et si tu détectes toutes les arrêtes qui sont dans une concavité et que lorsque tu traces les parallèles de ces arrêtes tu les place à -dist au lieu de les tracer à dist, ça donne quoi ?

Cela ne peut pas marcher.
Observe mon dessin de gauche;
Si je suis ta suggestion, mes parallèles seront à l'intérieur du polygone.
Dans certains cas, le contour doit être déterminé par l'intersection de deux cercles sans que les parallèles doivent être tracées.
Dans d'autres cas, les parallèles se croisent et seules les portions extérieures doivent être tracées. Mais je n'arrive pas à en tirer des règles générales.

Oui, laisse tomber, c'est absurde comme idée :aie:. Mais comme alors fais tu pour tracer les parallèles ? Dans le dessin de droite pourquoi les parallèles sont tracées de l'autre coté du polygone ?

Pour le dessin de droite, je suis tout à fait perplexe.
Je suis sûr de moi pour les 2 parallèles supérieures et inférieures reliées par un arc de cercle à droite mais je ne vois pas du tout comment tracer la partie gauche.
En fait, il s'agit d'une application cartographique qui doit faire apparaitre tous les terrains se trouvant dans un rayon (Dist) d'une parcelle donnée.

Citation:

---

Envoyé par PRomu@ld

Mais comme alors fais tu pour tracer les parallèles ? Dans le dessin de droite pourquoi les parallèles sont tracées de l'autre coté du polygone ?

---

+1. Tu as mis le doigt dessus.

Dans le dessin n°2 les paralleles ne sont pas du bon coté. Il faut toujours qu'elles soient a l'exterieur du polygone.

Voilà elles sont tracées de l'autre côté.
Quant à savoir ce que j'en fais ...

Bonsoir,

et si on faisait une méthode toute simple :
- Tu calcules le centre de gravité de ton polygône.
- Tu fais une homothétie de centre le barycentre.

Pour un convexe pas de soucis, pour le reste on va surement avoir les mêmes problèmes.

De plus, si le centre de gravité n'est pas dans la figure, j'ai peur que ça risque poser des problèmes.

Pourquoi ne pas prendre l'application que tu nous donnes :

Citation:

---

En fait, il s'agit d'une application cartographique qui doit faire apparaitre tous les terrains se trouvant dans un rayon (Dist) d'une parcelle donnée.

---

Tu places des cercles de rayon dist sur chacun des points du polygone. Tu traces ensuite tes segments tels qu'ils soient tangents sur deux cercles consécutifs et à l'extérieur de ton polygone.

Bonjour,

C'est effectivement le même problème que dans mon post http://www.developpez.net/forums/sho...d.php?t=175905

Pour le tracé, je l'ai résolu en découpant toutes les parralléles et les cercles en petits segments et en éliminant les segments situés dans le contour du polygone ou à une distance inférieure à Dist.

Citation:

---

Envoyé par defluc

Voilà elles sont tracées de l'autre côté.
Quant à savoir ce que j'en fais ...

---

Dans ce cas precis tu n'en fais rien car les segments de raccords sont inclus dans un cercle.

http://xray.club.fr/dvpimg/contour.png

Citation:

---

Envoyé par ToTo13

Bonsoir,

et si on faisait une méthode toute simple :
- Tu calcules le centre de gravité de ton polygône.
- Tu fais une homothétie de centre le barycentre.

---

Ca donnerait pas la bonne réponse puisque par exemple pour un carré, ou obtiendrait un carré alors qu'il faut que les angles soient des arcs de cercles.

Je pense qu'il faut simplement savoir pour chaque coté où est l'intérieur et l'extérieur et faire la translation vers l'extérieur et non vers l'intérieur comme c'est le cas pour le dessin de gauche. Sinon le reste me semble bon !

Citation:

---

Ca donnerait pas la bonne réponse puisque par exemple pour un carré, ou obtiendrait un carré alors qu'il faut que les angles soient des arcs de cercles.

---

Exact.

Citation:

---

Sinon le reste me semble bon !

---

Encore heureux ! :aie:

J'ai un peu corrigé le dessin pour faire apparaître le tracé que l'on a avant découpage et élimination.

Merci les gars
Sans vouloir trop demander, je crains qu'il y ait bien d'autre cas particuliers de polygones convexes et je vous joins une version modifiée de mon dessin 1 pour lesquels la solution du dessin 2 où les deux segments parallèles situés à l'intérieur de cercles centrés sur des sommets consécutifs sont à éliminer parce qu'ils sont à l'intérieur de ceux-ci.

Dans le dessin 1, ce sont les cercles centrés sur des sommets non consécutifs qui forment le contour à retenir.

La parallèle au segment 3 est entièrement à l'intérieur du cercle construit sur le sommet D alors que la parallèle au segment 2 ne l'est que partiellement.

Quant aux parallèles aux segments non consécutifs 10 et 12, c'est leur intersection qui est à prendre en considération.

Et il y a peut-être d'autres cas

Voilà qui ne simplifie pas une généralisation débouchant sur un algorithme.

Citation:

---

La parallèle au segment 3 est entièrement à l'intérieur du cercle construit sur le sommet D

---

C'est le cas que montrait pseudocode, celui ci, tu n'en fais rien.

Pour ceux qui le sont partiellement, le cas est assez simple à gérer. Tu as un segment, donc deux sommets, tu dois prendre en compte l'intersection si l'un des deux sommets est inclus dans un cercle et pas l'autre.

@defluc: Est-ce que l'image est discrétisée ? Est-ce qu'il te faut l'equation du contour (droite + arcs de cercle) ?

Dans le cas contraire tu peux calculer la distance entre chaque pixel de l'image et la forme, puis marquer tous les pixels dont la distance est entre 0 et D.

J'ai les coordonnées géographiques de chaque sommet.
A partir de l'équation de chaque arête, je déduis les extrémités des perpendiculaires élevées aux extrémités de chaque arête d'une longueur Dist.
Je relie ces points 2 à 2 pour obtenir les parallèles.
L'équation du cercle de rayon Dist centré sur un sommet et tangent aux parallèles à 2 segments consécutifs est ensuite tracé entre les 2 points de tangence.

Citation:

---

Envoyé par defluc

L'équation du cercle de rayon Dist centré sur un sommet et tangent aux parallèles à 2 segments consécutifs est ensuite tracé entre les 2 points de tangence.

---

En fait, il faut raisonner individuellement sur chaque segment. Le "contour" d'un segment est une zone ovale qui englobe le segment (fugure du haut, en gris)

On superpose les "contours" de chaque segment composant le polygone (figure du bas).

On construit finalement le "contour" du polygone en suivant les contours les plus externes (i.e. on change de ligne de contour a chaque intersection)

http://xray.club.fr/dvpimg/contour2.png