Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

longueur et largeur polygone

Posté par
ericire
27-10-10 à 19:52

bonjour
je voudrais créer ou reprendre un algorithme qui calculerait la plus grande largeur et longueur d'un polygone.
comment faire ce calcul SVP

Posté par
ericire
re : longueur et largeur polygone 27-10-10 à 20:00

je ne sais pas éditer mon message pour le compléter
>> je précise que je connais les coordonnées de chaque sommet.

Posté par
verdurin
re : longueur et largeur polygone 27-10-10 à 22:20

Bonsoir,
ce que tu veux faire n'est pas vraiment clair.
le polygone est-il  convexe ?

Si il s'agit d'inscrire le polygone convexe dans un rectangle :
- pour chaque côté
\quad -déterminer  le minimum des distances des sommets à ce côté.
- Le minimum des résultats précédents donne un côté AkAk+1.
-on projette les sommets sur la droite AkAk+1 munie de ce repère et on prend le max et l'inf des abscisses.

Si le polygone n'est pas convexe, on utilise l'enveloppe convexe des sommets.

On obtient ainsi le rectangle de longueur maximale et de largeur minimale contenant le polygone.
Mais ce n'est peut-être pas ce que tu veux.

Posté par
ericire
re : longueur et largeur polygone 02-11-10 à 09:16

bonjour,
merci verdurin pour ton attention
j'ai des polygones convexes ou pas.

Donc 1
je dois chercher une méthode pour ne sélectionner que les points de l'enveloppe convexe à partir de leurs coordonnées.

ensuite 2

je ne comprends pas ta méthode :

Si il s'agit d'inscrire le polygone convexe dans un rectangle :
- pour chaque côté
-1 déterminer  le minimum des distances des sommets à ce côté.

est-ce à dire choisir le point le plus proche à distance orthogonale ?
- Le minimum des résultats précédents donne un côté AkAk+1.
cela veut-il dire sélectionner le coté correspondant à la plus petite des distances relevées précédemment ?
-2 on projette les sommets sur la droite AkAk+1 munie de ce repère et on prend le max et l'inf des abscisses.
ça ce serait pour calculer l'autre dimension du rectangle ?

pour le point 1, moi j'aurais pris la plus grande distance par rapport à ce coté, de sorte à inclure tous les autres
pour le point 2 ok
le choix final étant le rectangle dont le rapport longueur/largeur est le plus grand

maintenant il me reste à savoir comment concrètement, à partir des coordonnées, j'écris un algorithme pour :

1 sélectionner les points de l'enveloppe convexe
2 déterminer la liste des rectangles correspondant à chaque coté pour calculer le rapport longueur/largeur
3 faire un tri dans ces rapports pour prendre le plus grand

Posté par
verdurin
re : longueur et largeur polygone 03-11-10 à 00:22


J'aimerais dire qu'il s'agit d'une faute de frappe, mais c'est un trou dans la pensée.

- pour chaque côté
\quad - déterminer  le maximum des distances des sommets à ce côté.
\quad - Le minimum des résultats précédents donne un côté AkAk+1.
Pour un polygone convexe on obtient la largeur minimale.

Posté par
ericire
re : longueur et largeur polygone 03-11-10 à 20:42

salut verdurin et merci

comme dit plus haut je dois en faire un algorithme, autrement dit,
donner des instructions précises à la machine.
donc comment faire concrètement pour
sélectionner les points de l'enveloppe convexe (certaine formes ne le sont pas)
déterminer  le maximum des distances des sommets à ce côté.
déterminer Le minimum des résultats précédents donne un côté AkAk+1.
et la longueur ?
merci

Posté par
verdurin
re : longueur et largeur polygone 04-11-10 à 21:59

Pour déterminer l'enveloppe convexe d'un ensemble fini de points du plan.

Pour chaque paire de points (Ai;Aj) :
\ - déterminer si tous les points Ak avec ki et kj sont dans le même demi-plan définie par la droite AiAj
\;\quad -- si c'est le cas le segment AiAj fait partie de l'enveloppe convexe (les points Ai et Aj aussi).

On obtient ainsi la liste des segments et des sommets de l'enveloppe convexe, mais cet algorithme n'est pas vraiment optimal.

Soit (B1... Bk) le polygone convexe obtenu.
Pour chaque côté on cherche le point le plus loin.
La plus petite distance maximum est la <<largeur>> et la plus grande distance maximum est la <<longueur>>.

Ce n'est certes pas le meilleur algorithme possible,  mais j'espère qu'il te serat utile.

Posté par
ericire
re : longueur et largeur polygone 08-11-10 à 19:23

ok je comprends le principe
mais j'en reviens à comment ?
pour le point 1 comment déduire l'appartenance des autres points à un demi plan ou à l'autre.
avec les angles ?
et idem pour le point 2, comment obtenir les distances puis les comparer entre-elles ?

Posté par
verdurin
re : longueur et largeur polygone 08-11-10 à 20:53

Pour le point 1
étant donné deux points distincts Ai et Aj dont on connait les coordonnées on sait trouver une équation de la droite sous la forme ax+by+c=0.
Elle définie deux demi-plans (ouverts) l'un caractérisé par ax+by+c>0 l'autre par ax+by+c<0.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !