vecteurs exterieurs unitaires aux sommets d'un polygone

**Nemerle** · 03/12/2009, 11h35

Salut,

j'ai une soluce au problème suivant, mais j'aimerais connaître votre point de vue, car je recherche l'algo le plus rapide possible, et n'étant pas infographiste

J'ai un polygone quelconque défini par une suite de sommets consécutifs Si. En chaque sommet Si j'aimerais déterminer son vecteur extérieur unitaire, à savoir le point extérieur au polygone sur la bissectrice de S(i-1)SiSi+1, à distance 1 de Si.

Quelqu'un à déjà eu ce problème? Sur que oui

**pseudocode** · 03/12/2009, 14h53

Une solution est de calculer un vecteur de la bissectrice et de le normer. Mais je ne sais pas si c'est le plus rapide.

**FR119492** · 03/12/2009, 16h32

Salut!

J'ai un polygone quelconque

Ton polygone est-il vraiment quelconque, c'est-à-dire que tu exclus le cas de polygones non convexes et le cas où deux côtés se croisent?
Jean-Marc Blanc

**Nemerle** · 03/12/2009, 16h37

Pas de convexité assurée, mais pas de croisement possible...

Pseudo: si tu veux, mais rapidement?

**Jean Dumoncel** · 03/12/2009, 16h53

Salut,

Un début de reflexion :
Tu normes tes 2 vecteurs SiS(i-1) et SiSi+1, tu fais la somme des vecteurs normés, tu obtiens un vecteur directeur de ta bissectrice, il ne reste plus qu'à le normer à nouveau. Ensuite pour savoir si ce vecteur est dirigé vers l'intérieur ou l'extérieur, ça dépend de la façon dont sont orientés les sommets et de l'angle entre les deux côtés (supérieur ou inférieur à 180).

C'est sûrement à approfondir...

**Nemerle** · 03/12/2009, 17h02

Ok, ça c'est la partie simple, t'as obtenu un vecteur directeur normé v

Le problème est de trouver le sens "vers" l'extérieur.

Pour ce faire, je compte le nombre de points d'intersection des segments SiSi+1 sur R+.v et sur R-.v (avec qq règles si le segment ou un bord est sur la bissectrice). La demi-droite qui a un nombre pair d'intersections pointe vers l'extérieur...

Y-a-t-il plus rapide??

**Jean Dumoncel** · 03/12/2009, 17h11

Tu aurais pu préciser que l'obtention du vecteur ne posait pas de problème...

Pour l'orientation du vecteur : ma question :
est-ce que tes sommets sont orientés? en gros est ce que l'on tourne toujours dans le même sens pour chaque suite de sommets de tes polygones?

Si non, je ne connais pas de méthode plus rapide que la tienne...

**Nemerle** · 03/12/2009, 17h51

Non, on ne tourne pas tj dans le même sens, mais si tel était le cas, tu as qq chose?

**Jean Dumoncel** · 03/12/2009, 21h08

Imaginons que l'on tourne toujours dans le sens anti-horaire, par exemple :

Alors pour B :
l'angle définit par les vecteurs (BC,BA) est inférieur à 180°, donc dans ce cas on utilise les vecteurs -BC et -BA pour calculer le vecteur directeur de la bissectrice (qui du coup sera dirigé vers l'extérieur)

Pour C :
l'angle définit par les vecteurs (CD,CB) est supérieur à 180°, donc dans ce cas on utilise les vecteurs CD et CB pour calculer le vecteur directeur de la bissectrice (qui du coup sera dirigé vers l'extérieur)

**pseudocode** · 04/12/2009, 09h39

Envoyé par Nemerle

Non, on ne tourne pas tj dans le même sens, mais si tel était le cas, tu as qq chose?

Bah là, y a pas de miracles. Avec seulement 2 segments consécutifs et sans connaitre le sens de parcours, c'est du de différencier l'intérieur/extérieur du polygone.

Si tu connais le sens de parcours, tu peux determiner l'orientation de la normale N avec le signe du produit scalaire (BA,BC) ou du produit vectoriel (AB,N)

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

Envoyé par pseudocode

Si tu connais le sens de parcours, tu peux determiner l'orientation de la normale N avec le signe du produit scalaire (BA,BC) ou du produit vectoriel (AB,N)

On peut le connaître, si les segments ne se croisent pas:

Envoyé par Exaflop.org - citant O'Rourke

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.

Ce problème m'intéresse aussi au même moment :-).

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

Envoyé par Luigicube

On peut le connaître, si les segments ne se croisent pas

Oui, ma remarque ne fonctionne que pour un polygone non croisé. Sinon il faut utiliser des algos plus complexe pour déterminer l'orientation de la normale extérieure.

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

Envoyé par Nemerle

Salut,

j'ai une soluce au problème suivant, mais j'aimerais connaître votre point de vue, car je recherche l'algo le plus rapide possible, et n'étant pas infographiste

J'ai un polygone quelconque défini par une suite de sommets consécutifs Si. En chaque sommet Si j'aimerais déterminer son vecteur extérieur unitaire, à savoir le point extérieur au polygone sur la bissectrice de S(i-1)SiSi+1, à distance 1 de Si.

Quelqu'un à déjà eu ce problème? Sur que oui

Une solution rapide que je ferais est : (en O(N))

Pour chaque sommet :

calculer l'angle Si-1,Si,Si+1
calculer le point milieu de Si-1,Si+1
Calculer bêtement le point par l'équation de la droite (Si, ce point)

Non ?

**Jean Dumoncel** · 04/12/2009, 11h48

Envoyé par souviron34

[*]calculer le point milieu de Si-1,Si+1

Juste une remarque : mathématiquement le milieu de Si-1,Si+1 n'est pas sur la bissectrice de S(i-1)SiSi+1 dans le cas général.

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

ok, tu as raison...

Je peux préciser alors : le milieu du segment si-1, pt, où pt est le point de Si-Si+1 à la même distance de Si que l'est Si-1..

Ou bien la rotation de Si-1 par un angle alpha/2 autour de Si ..

Bref, un calcul simple, quand même, non ?

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

Souviron: ok , mais tout le problème est de savoir dans quelle direction se trouve l'extérieur...

Magelan & LuigiCube: je n'avait pas pensé à orienté le polygone, c'est une bonne idée, car comme Magelan l'a montré avec son dessin il suffit de 4 règles pour construire directement la normale extérieure en fct du sens d'orientation et de angle<180° ou pas. Z'aime pas calculer des angles car c'est couteux, mais ça doit quand même ici être plus rapide qu'une intersection de segments...

**Jean Dumoncel** · 04/12/2009, 11h58

Envoyé par souviron34

Je peux préciser alors : le milieu du segment si-1, pt, où pt est le point de Si-Si+1 à la même distance de Si que l'est Si-1..

Donc ça revient à ce que j'ai marqué plus haut (en normant les vecteurs)

Mais on en revient toujours au fait que les sommets doivent être orientés ce qui apparemment peut-être fait par le calcul de l'aire signé dans le lien donné par Luigicube.

**souviron34** · 04/12/2009, 12h00

Envoyé par Nemerle

Souviron: ok , mais tout le problème est de savoir dans quelle direction se trouve l'extérieur...

D'après les routines de maths simples comme CounterClockWise ou le calcul exposé dans les Faqs algos de comp.graphics.algo, il suffit de faire le test

counterclockwise (i-1,i,pt) et comparer à counterclockwise (i-1,i,i+1). Le point intérieur aura le même , le point extérieur aura le signe contraire..

**Nemerle** · 04/12/2009, 12h32

Magelan & LuigiCube: ça marche, ça suffit à mes besoins!

Merci à tous!

vecteurs exterieurs unitaires aux sommets d'un polygone

Algorithmes et structures de données

Discussions similaires

Partager

Partager