Contraction d'un polygone

**Luigicube** · 04/12/2009, 09h24

Bonjour,

J'essaye depuis quelque jours de réaliser la contraction d'un polygone qui peut être concave, mais ne présente pas de trous et n'est pas croisé. La contraction comme je l'entend fait que si on prend le projeté orthogonal de n'importe quelle point du périmètre du nouveau polygone sur l'ancien polygone, on a une distance d'au moins shift (i).

J'ai pensé à plusieurs solutions, dont une est la réduction (dans le sens géométrique, réduction des dimensions) du polygone, en déterminant le centroïde et en réduisant la distance centroïde-sommet sur chaque point de manière proportionnelle (la proportion étant calculée préalablement telle qu'on respecte (i).
Malheureusement, cette solution ne semble marcher que sur des polygones convexes, avec comme contre-exemple si deux points sont dans le même axe par rapport au centroïde, il n'y aura pas "contraction" du segment reliant ces deux points.

Une autre solution possible est de procéder segment par segment, en translatant les deux points par un vecteur d'angle perpendiculaire à celui du segment et de module shift. Seulement je ne vois pas comment déterminer l'angle + ou - 90° tel que le nouveau segment soit vers l'intérieur du polygone. Il faut aussi penser à faire l'intersection des deux points ainsi créés pour un sommet du polygone initial.

Je suis un peu bloqué sur la direction à prendre et compte sur tout point de vue nouveau sur le sujet :-)

(Si vous ne comprenez pas certaines de mes explications, n'hésitez pas non plus à demander je suis pas forcément très clair).

Edit : ah bah j'avais point vu, on parle de l'exterieur juste en dessous. Suffit que je sache dans quel sens mon polygone tourne et la solution est ici

Subject 2.07: How do I find the orientation of a simple polygon?

Compute the signed area (Subject 2.01). The orientation is counter-clockwise if this area is positive.

Maintenant il faudrait savoir si l'intersection est facile à faire et si la solution est optimale.

**pseudocode** · 04/12/2009, 10h36

Ton problème ressemble beaucoup a celui là : http://www.developpez.net/forums/d75...trigonometrie/

**Luigicube** · 04/12/2009, 10h43

Effectivement, merci pour le lien.

D'ailleurs ta remarque est pertinente, est-ce qu'en connaissant la bissectrice, on a à coup sur la droite sur lequel est le point (extérieur/)intérieur ?

Après, calculer la longueur n'est qu'une question de trigo.

**souviron34** · 04/12/2009, 11h04

le problème de fond est :

ton problème est-il correctement posé ??

Soit tu veux "shrinker" ton polygone
Soit tu veux le diminuer d'une certaine distance

Dans le cas 1, ta première méthode marche parfaitement.. Je suppose que si elle ne marche pas, c'est que tu t'es trompé dans la détermination du facteur de zoom ou du centroide...

**Luigicube** · 04/12/2009, 11h29

Number two.

Je pensais que ça revenait au même, mais en effet, un "shrink" ou "contraction" comme je l'avais appelé ne fait pas ce que je veux, c'est à dire une translation intérieure.

Par contre, le problème posé dans les deux liens correspond plus, je vais voir ce que ça peut donner.

**souviron34** · 04/12/2009, 11h33

OK

Envoyé par Luigicube

D'ailleurs ta remarque est pertinente, est-ce qu'en connaissant la bissectrice, on a à coup sur la droite sur lequel est le point (extérieur/)intérieur ?

oui

Sauf dans le cas où ce point disparait car les points/côtés des sommets précédents/suivants le font disparaître..

**Nemerle** · 04/12/2009, 11h45

Je n'ai peut-être pas compris le problème, mais pourquoi

- ne pas appliquer une homothétie de rapport <1 de centre l'origine sur ton polygone P0 pour obtenir P1, les polygones sont alors semblables
- calculer les centroïdes C0 et C1 de P0 et P1, et translater P1 de vecteur C1C0

?

**Luigicube** · 04/12/2009, 14h12

Je pense que ce que tu proposes ramène à faire la solution 1, qui est une contraction/shrink.

Dans ce que je veux faire, au final, les polygones pourront ne plus être semblables. Dans certains cas (p.ex. polygones convexes), ça revient à faire un shrink, mais pas dans tous.

Je finis d'essayer la solution 2. avec les bissectrices et je mets résolu

**souviron34** · 05/12/2009, 15h16

Envoyé par henderson

Salut !
..
A plus !

C'est ce qu'on a tous dit, mais c'est pour l'hypothèse 1 mentionnée plus haut ("zoom" ou "dezoom" d'un polygone)..

Pour le fait d'ajouter/retrancher une distance, qui est ce que veux faire le PO, la discussion citée en référence indique les écueils, et l'approche n'est (malheureusement) pas aussi simple...