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
je ne sais pas éditer mon message pour le compléter
>> je précise que je connais les coordonnées de chaque sommet.
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é
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.
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
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é
déterminer le maximum des distances des sommets à ce côté.
Le minimum des résultats précédents donne un côté AkAk+1.
Pour un polygone convexe on obtient la largeur minimale.
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
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
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.
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 ?
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :