Discussion :

[BioKore]

Bonjour à tous,


Afin de réaliser quelques tests géométriques en 2D, je cherche un moyen de pouvoir insérer un sommet A à la liste des sommets S définissant le polygone P, initialement tracé dans un ordre unique et particulier (12345...), tel que le nouveau polygone P', alors défini par une liste de sommets S':=(S inclu A), respecte les quelques règles simples ci-dessous :
- le polygone initial et ou final peut être convexe ou concave mais non croisé
- le polygone final est tracé dans le même ordre que le polygone initial
- la liste des sommets initiale n'est modifiée que par l'insertion d'un nouveau sommet ; l'ordre n'est pas modifié (ex : {1,2,3,4} --> {1,2,A,3,4})
- le polygone initial et final sont fermés (le premier sommet est aussi le dernier)
- le polygone est composé à minima de 3 sommets mais peut en contenir bien plus.
- les sommets sont exprimés dans une base 2D (type x y)

Aussi, je souhaite réaliser la manipulation sans avoir à tester si le nouveau sommet est inclu ou exclu de la surface du polygone initial (pas de "tests d'intersection")

J'ai déjà tenté de réaliser cet exercice en testant le signe du produit vectoriel OI^OA (où O = barycentre du poly, I un sommet existant et A le nouveau sommet) pour chaque sommet 'I' du poly. Cependant, il est tout à fait possible que, selon la position du barycentre et la forme du polygone, on se retrouve avec plusieurs solutions dont certaines ne respectent pas les règles ci-dessus.
J'ai alors essayé de raisonner autour des angles IÔA pour chaque sommet 'I', mais je me retrouve confronté à la même problématique.

Pour info, le bout de code qui s'appuiera sur cet "algorithme" me servira justement à valider (ou non) une idée que j'ai afin de tester si un point est présent ou non au sein d'un polygone. Je sais qu'il existe d'autres méthodes que celle que je souhaite faire, mais là n'est pas la question.

Merci d'avance !

[Flodelarab]

Bonjour

• D'abord, ton message ne comporte pas de point d'interrogation. Ce qui est souvent le signe simple que tu n'as pas de question, ou que la question est mal définie.
• Ensuite, tu poses des calculs avant même de savoir ce que tu cherches.
• En tout cas, même en relisant ton message, je ne sais pas ce qui pose problème.
  Quelle est la question ?
• Enfin, cette discussion est-elle la suite de ta discussion précédente ? Si oui, alors les sommets sont dans l'ordre des arguments croissants et modules croissant; et tout nouveau point trouve sa place naturelle dans la suite. N'est-ce pas ?

[BioKore]

Bonjour,

Effectivement, à mon habitude, je formule mes questions en parallèle de divers essais et implémentations. Ca n'a pas loupé, j'ai du ré-écrire mon problème 5 fois sans en être certains sur la fin.

Ma question est : "comment intégrer un sommet au sein d'un polygone quelconque existant sans dénaturer ce dernier (sans modifier l'ensemble des sommets), et sans croiser le polygone ?"

Effectivement, c'est plus ou moins lié à la précédente discussion. Je n'ai jamais trop fricoté avec les notations complexes, mais je vais m'y plonger et essayer ça.


Merci !

[Flodelarab]

Un dessin vaut mieux qu'un long discours.





Le point vert est ajouté au contour à sa place naturelle en fonction de l'angle entre l'horizontale et la droite reliant l'origine et le point. Puis, par la distance à l'origine en cas d'ex-aequo. (comme ont pu l'être les 3 points à la droite du point vert puisqu'ils sont alignés avec l'origine).

Est-ce plus clair sur la méthode ?

[BioKore]

Oui, le schéma représente, me semble-il, ce que je souhaite faire. Cependant, je ne vois pas comment un tri "[...] dans l'ordre des arguments croissants et modules croissant[...]" permet d'en arriver à un tel résultat pour tout type de polygone. Selon moi, et si j'en crois quelques essais rapides à la main, le cas suivant expose un contre-exemple.


Sur le dessin ci-dessus, où le point M représente le barycentre (qui servira d'origine) et le point 'x' celui à insérer au polygone, le tri me semble moins trivial. En effet, à première vue, la position 'naturelle' du point x semble être située entre les sommets 3 et 4 voire entre les sommets 4 et 5. Et même, je pourrais accepter qu'il se situe entre les sommets 5 et 6 car cela ne croise pas le polygone. Cependant, si je tente de le trier par argument / norme croissant, il sera situé entre les sommets 1 et 2 ( arg(Mx) < arg(M2) && |mx| < |M2| ).

Cependant, et ce cas est tout a fait probable, il est possible que j'ai mal saisi un aspect important des réponses données ou que je me soit mal fait comprendre sur la problématique initiale : "ajouter un sommet à un polygone quelconque existant naturellement tracé dans le sens trigonométrique".
Néanmoins, je vais continuer mes essais dans ce sens ; je finirais par saisir la solution.

Merci.

[Flodelarab]

Oui mais ton polygone n'est pas construit dans l'ordre. À partir des points que tu présentes, plutôt que le polygone jaune, utilisons le polygone bleu. Les demi-droites du dernier dessin sont là pour prouver que l'ordre de tes sommets aurait dû être 0, 1, 4, 2, 3, 6, 5, 7. Et x est donc intégré après 4 et avant 2.