Discussion :

[diam's]

Bonjour.

Presque tout est dans le titre. Jusque là c'est simple.

Ca le devient moins dans mon cas :
- le décalage doit être automatique (pas d'action humaine)
- il est toujours dans le même sens (vers l'extérieur du polygone)

là , ça va toujours....
- le polygone peut être concave ou convexe : et c'est là qu'est le problème. Comment faire pour savoir qu'on décale bien vers l'extérieur du polygone ?

je pensais "décaler" les sommets 1 par 1, puis, à chaque fois, vérifier que la surface du polygone s'est agrandie, si ce n'est pas le cas, on décale de l'autre coté. Mais cela me semble relativement long, même si il n'y a jamais plus de 100 ou 120 sommets.

La question est donc : avez-vous une meilleure solution ? plus rapide, plus élégante, plus ...

Nota : je sais que ce sujet relève plus de l'algo que de Delphi, mais comme en forum 'Algo' on répond souvent en termes mathématiques (que je ne comprends pas toujours) ou en pseudo-code matiné de C (je comprends le pseudo-code, mais pas le C, snif), les modos, espérons-le, voudrons bien m'excuser

Cordialement,

Diam's

[bubulemaster]

Je veux bien essayer de t'aider mais ça correspond à quoi la fonction décalé.

Un petit graphique pour illustrer

[diam's]

voici donc un petit exemple ICI

A gauche, la forme initiale
A droite, la forme "décalée" vers l'extérieur
Le petit cercle représente le "centre de masse" de la forme. J'avais en effet penser à utiliser cela pour savoir si on décalait vers l'extérieur (la distance entre le centre de masse et chaque point de ma forme augmentant, mais GROSSE ERREUR : ce n'est vrai que dans le cas d'une forme concave OU dans le cas d'une forme convexe dont le centre de masse est à l'intérieur de la forme... je sais pas si je suis clair là )

La forme représentée dans l'exemple est relativement simple (moins d'une dizaine de segment), mais dans la réalité, la forme peut aller du carré à la patatoïde croisé avec un peigne taille XXL

Ce n'est pas le "décalage" qui me pose problème (un simple problème de coefficient de droite ax+b), mais bel et bien le sens du décalage (je veux décaler vers l'extérieur de la forme générale). La seule soluce que j'ai actuellement c'est :
- Décaler un point
- vérifier si la surface générale de la forme augmente
- si "oui", passer au point suivant
- si "non", décaler dans l'autre sens

Dans un cas simple, ça va vite (le carré) mis dans d'autres, ça risque de devenir d'une insupportable lenteur (le rejeton de la pomme de terre et du peigne). Même si cette procédure n'est faite qu'une fois (les valeurs obtenues seront alors stockées), rester 2 minutes à regarder les mouches, ç'est long (surtout si y'a pas de mouches)

Vouli voilou

[philnext]

Ce que je ne comprends pas c'est que ta solution de 'décaler' les sommets me semblait bonne. Il suffit de regarde le sens de décalage puis de parcourir tous les sommets. Même si il y en a 200 ça ne doit pas prendre 2 mn !!

[diam's]

C'est vrai qu'en disant 2 minutes, j'ai grossi le trait, quoique ça dépend aussi du pc qui fera tourner le programme. En fait, j'ai certainement mal exposé le problème.

A chaque fois je "décale" un sommet, je recalcule la surface de l'ensemble du polygone (méthode des triangles, voir un de mes anciens posts). Cela ne me pose pas de soucis puisque ça fonctionne (en théorie), mais je souhaitais optimiser un peu la procédure, d'ou l'idée (pas bonne...) d'utiliser le centre de masse du polygone (valable que dans certains cas, malheureusement).

Mais si personne n'a de meilleure idée, je ferais avec ma méthode

[philnext]

Mais pourquoi donc ne pas décaler tous tes sommets et ENSUITE calculer la surface ? Là ça doit être relativement rapide !

[diam's]

par ce que cela me garanti que je décale dans le bon sens.

Si on regarde l'exemple fourni en post #3, tu verras que la forme peut avoir une forme de peigne. L'espace entre les 2 branches peut être extrêmement mince (plus faible que la valeur de décalage). Si je calcule tous les points d'abord, il y a risque que deux sommets s'inversent (le sommet S1 devient le sommet S2 et vice-versa) voir que la surface globale diminue (je sais, c'est pas clair pour moi non plus). en calculant la surface à CHAQUE décalage, je pensais limiter le risque de me tromper de coté.

Par contre, en y repensant, je reviens sur ton post (#4) qui dit de "regarder le sens de décalage". Cela ramène à la première question : comment sait-on qu'on décale chaque sommet dans le bon sens, sachant que mon polygone est fermé, concave ou convexe, de forme régulière ou franchement tarabiscoté, et que je comptes le reduire, pour cette manip, à une succession de segments de droite ? ma soluce (en calculant la surface à chaque fois) est longue, mais je n'en vois pas d'autre.

Petit PS : c'est l'utilisateur qui défini à la souris la forme du polygone (et tout le monde sait qu'il va forcément y en avoir un pour faire ce qui n'est prévu)

[tourlourou]

si c'est tracé à la souris, tu as donc les coordonnées des sommets
tu dois pouvoir calculer le barycentre
le prendre pour origine d'un nouveau repère en coordonnées polaires
multiplier la coordonnée longueur dans ce repère par le facteur voulu
et hop !

[philnext]

Pour toute forme 'fermée' concave et/ou convexe dont tous les sommets sont identifiés si tu choisis un sommet de départ et un 'sens' de parcours :
Si tu identifies, pour ce sens de parcours, la direction (droite ou gauche) de déplacement du premier sommet qui permet d'augmenter la surface alors cette direction augmentera la surface pour TOUS les autres sommets rencontrés sur le parcours.

[diam's]

tu dois pouvoir calculer le barycentre
le prendre pour origine d'un nouveau repère en coordonnées polaires
multiplier la coordonnée longueur dans ce repère par le facteur voulu
et hop !

Barycentre = centre de masse ? Ca introduit en plus des calculs d'angles, non ? Et si le barycentre est à l'extérieur de la forme, ne vais-je pas avoir un problème (voir mon deuxième post) ?

Si tu identifies, pour ce sens de parcours, la direction (droite ou gauche) de déplacement du premier sommet qui permet d'augmenter la surface alors cette direction augmentera la surface pour TOUS les autres sommets rencontrés sur le parcours.

Ben, oui, c'est si simple en fait Y'a vraiment des fois où on se complique la vie pour rien ...

Merci à tous

[tourlourou]

centre de masse = Barycentre particulier , en effet

on doit trouver les coordonnées du barycentre en le calculant pour 2 points, puis celui du barycentre trouvé et du point suivant, etc.
je n'ai pas la formule en tête, mais elle ne doit pas être très difficile à trouver

peu importe que ce point soit en dehors de la fiche (ce qui ne me semble pas possible, d'ailleurs) : on s'en sert juste comme origine, pas pour le tracer => même si ces valeurs étaient négatives, pas de souci