Insertion d'un sommet au sein d'un polygone

Version imprimable

30/03/2020, 22h27
BioKore

Insertion d'un sommet au sein d'un polygone

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 !
31/03/2020, 16h14
Flodelarab
Bonjour :coucou:
- 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 ?
31/03/2020, 22h39
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 !
01/04/2020, 02h05
Flodelarab

3 pièce(s) jointe(s)

Un dessin vaut mieux qu'un long discours.

Pièce jointe 551496
Pièce jointe 551500
Pièce jointe 551502

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 ?
01/04/2020, 04h43
BioKore

1 pièce(s) jointe(s)

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.
Pièce jointe 551515

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.
01/04/2020, 16h19
Flodelarab

4 pièce(s) jointe(s)

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.

Pièce jointe 551690 Pièce jointe 551694 Pièce jointe 551696 Pièce jointe 551699
01/04/2020, 22h45
BioKore

Citation:

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.

Pas dans l'ordre selon l'algorithme fourni peut-être, mais dans l'ordre selon ce que l'utilisateur souhaites faire. Il est bien entendu que si je change la donnée d'entrée, j'arrive au résultat que tu proposes.
L'utilisateur peut nous donner à manger n'importe quel type de polygone (dont celui que j'ai donné en exemple ou d'autres plus ou moins complexes). Si, par exemple, dans un logiciel de CAO, les polygones que tu as réalisés sont fichus en l'air dès que tu souhaites trier ou ajouter des sommets, ça le fait pas trop.

Je vais essayer de trouver un meilleur exemple pour illustrer la chose ; je pense que certains aspects de la question méritent d'être développés.

Dans tous les cas, merci pour l'aide malgré tout !
02/04/2020, 01h09
Flodelarab

3 pièce(s) jointe(s)

Au départ, c'était un nuage de points en entrée. N'est-ce pas ?

Si tu veux traiter un polygone quelconque, tu n'as pas fini de t'arracher les cheveux. Car il faut faire des tests de croisements. Voici un exemple :

Pièce jointe 551996 Pièce jointe 552000 Pièce jointe 552002

Tu voudras naturellement intégrer le point au côté le plus proche. Et ce faisant, tu vas provoquer un croisement (interdit). Donc la méthode serait d'essayer d'intégrer le point à tous les côtés (pas forcément les plus proches) et d'éliminer les solutions qui croisent. Bonne chance.
02/04/2020, 16h49
BioKore

Effectivement, je suis plus dan le second cas (mon précédent post traitait d'un nuage de points quelconques, et, la méthode du tri que tu propose fonctionne très bien dans ce cas, mais pas présentement).

Donc si j'en crois ce que tu me dis, on rentre ici dans une vraie usine à gaz ? Étant donné que ça reste une fonctionnalité présente dans n'importe quel outil de CAO ou de dessin, j'aurais imaginé avoir plus de ressources sur le sujet, mais je t'avouerais ne pas trouver grands choses à ce sujet sur la toile.
Néanmoins, ce à quoi je pensais récement c'est, comme tu le dis, de faire des tests sur les segments à proximité directe du sommet à intégrer. Je n'ai pas encore vraiment réfléchi au sujet mais ou pourrait intégrer le sommet au sein du segment le plus proche...
Bref, je vais continuer à travailler la question.

Merci encore pour les coups de pouces.
02/04/2020, 18h58
tbc92

Si cette discussion est : 'comment procéder par itération pour répondre à la discussion de la semaine dernière ' ... il faut revenir sur la discussion de la seamine dernière : procéder par itération n'est pas la bonne méthode.

Mais partons du principe que c'est un besoin nouveau : on a un polygone fermé non-croisé. On veut ajouter un sommet, et on veut que le nouveau polygone soit toujours fermé non-croisé.

En insérant le point A à n'importe quel endroit dans la séquence (P1,P2,P3...,Pn), on obtient toujours un polygone fermé. Mais le risque est qu'il soit croisé.

Il y a des formules pas trop compliquées pour vérifier si 2 segments se croisent. Tu peux donc essayer tous les cas possibles (A,P1,P2,P3... Pn), (P1,A,P2,P3,...Pn) , (P1,P2,A,P3,...Pn) et retenir le premier qui respecte la contrainte 'non-croisé'.
Mais ça peut être assez long en traitement, et donner une forme pas très esthétique.

Par exemple, sur le 1er dessin que tu as proposé, il y a 3 ou 4 emplacements possibles pour insérer notre point vert. Comment choisir le plus pertinent ?
Pour chacune des droites (Pi,Pj), on peut calculer la distance entre le point A et cette droite.

On va donc calculer la distance entre le point A et chacune des n droites (Pi, Pi+1) ; On va trier ces nombres du plus petit au plus grand. Et c'est le segment (Pi, Pi+1) qui correspond à la plus faible distance qui devrait être retenu ; en général, ce segment là générera un polygone non-croisé.
Plus précisément, on regarde chacun des segments, selon l'ordre qu'on vient de définir. Pour chacun d'eux, on regarde si le polygone obtenu sera croisé ou non. Et dès qu'un segment convient, ç'est lui qu'on découpe en 2, en y insérant le point A.
02/04/2020, 19h35
foetus
Citation:

Envoyé par tbc92

Il y a des formules pas trop compliquées pour vérifier si 2 segments se croisent. Tu peux donc essayer tous les cas possibles (A,P1,P2,P3... Pn), (P1,A,P2,P3,...Pn) , (P1,P2,A,P3,...Pn) et retenir le premier qui respecte la contrainte 'non-croisé'.
Mais ça peut être assez long en traitement, et donner une forme pas très esthétique.

:mrgreen: je pense que BioKore s'en fiche si le chemin fermé soit une enveloppe convexe ou une enveloppe concave. J'ai l'impression qu'il veut un graphe fermé :
- qui a N points avec exactement N arêtes
- que chaque point appartient à 2 arêtes distinctes.
- qu'aucune arête ne se croise
Et à partir de là :koi: :koi:, je ne vois qu'un algo de combinaison/ arrangements de N points. Et
- faire les tests d'intersection afin d'abonner une branche le + rapidement pour ne pas avoir une complexité de N! :aie:
- Sûrement trier les points pour éviter les croisements Comment :koi: ? avec le X croissant/ décroissant et/ ou les Y croissant/ décroissant. À tester (<- je vois un tri en sens horaire/ anti-horraire en alternant le tri des X (jusqu'au max/ min) et le tri des Y (jusqu'au max/ min))
Je ne suis pas expert :wow:, mais à la fin tu vas avoir 1 ensemble de chemins fermés (*), mais je soupçonne qu'il va y avoir beaucoup de redondance. Donc avoir un test de comparaison entre 2 graphes/ chemins fermés.
Ou alors utiliser un graphe orienté. Comment - Quel sens :koi: ? avec le X croissant/ décroissant et/ ou les Y croissant/ décroissant. À réfléchir.

Citation:

Envoyé par tbc92

Par exemple, sur le 1er dessin que tu as proposé, il y a 3 ou 4 emplacements possibles pour insérer notre point vert. Comment choisir le plus pertinent ?

:mrgreen: je pense que BioKore a des critères visuels pour choisir ... autre que convexe ou concave. Donc, on ne peut rien faire :whistle:

C'est à lui, sur l'ensemble des chemins fermés (*), d'appliquer ces critères : si tel point et tel point sont reliés ou pas, si tel angle est <=, <, =, >, >= à telle valeur, ...
02/04/2020, 21h14
tbc92

@foetus
De ce que j'ai compris, Biokore part d'un polygone fermé (pas forcément convexe) non croisé, à n sommets.
Il a un nouveau point.
Il veut former un nouveau polygone, toujours fermé et non-croisé, avec (n+1) sommets.
Mais il veut modifier un seul segment. Il veut insérer le nouveau point entre 2 points qui étaient adjacents dans le polygone initial.

Donc de toutes façons, on sera pas sur un algo en n! , mais en n.
02/04/2020, 21h38
foetus
Citation:

Envoyé par tbc92

Il veut former un nouveau polygone, toujours fermé et non-croisé, avec (n+1) sommets.
Mais il veut modifier un seul segment. Il veut insérer le nouveau point entre 2 points qui étaient adjacents dans le polygone initial.

Donc de toutes façons, on sera pas sur un algo en n! , mais en n.

Oui c'est ce que je dis :mrgreen: si tu as (N+1) points, tu dois avoir (N+1) arêtes qui ne se croisent pas.

Si tu reprends son post #5, personne n'a parlé de mettre ce point entre 3 et 5.
Mais pour pouvoir le faire, il faut mettre
- 4 entre 0 et 1 : 0, 4, 1, 2, 3, X, 5, 6, 7, 0
- 4 entre 2 et 3 : 0, 1, 2, 4, 3, X, 5, 6, 7, 0
Est-ce que tu peux faire cela en temps N ? :wow:
02/04/2020, 22h20
tbc92

Extrait de ce message n°5 : "ajouter un sommet à un polygone quelconque existant naturellement tracé dans le sens trigonométrique".

On a un polygone existant. On a un point A, qui n'est pas un des sommets du polygone.
On veut couper un des segments XY pour le remplacer par les 2 segments XA et AY. Tous les autres segments du polygone restant inchangés.

C'est comme ça que je comprends la question.
03/04/2020, 02h54
Flodelarab

1 pièce(s) jointe(s)

Citation:

Envoyé par BioKore

Étant donné que ça reste une fonctionnalité présente dans n'importe quel outil de CAO ou de dessin

Je n'ai pas dans l'idée que les logiciels de CAO ou de dessin aient le moindre problème avec les chemins ou les polygones croisés. Exemple ci-dessous avec The Gimp.

Pièce jointe 552516
03/04/2020, 04h54
BioKore

Bonjour à tous. Je vois qu'il y a eu pas mal d'échanges sur le sujet aujourd'hui 8O

Je ne vais pas cité chacun d'entre vous, mais globalement vous avez réussi à comprendre mes explications quelque peu alambiquées.
Cependant, tbc92 a fourni une réponse qui semble convenir.

Citation:

Par exemple, sur le 1er dessin que tu as proposé, il y a 3 ou 4 emplacements possibles pour insérer notre point vert. Comment choisir le plus pertinent ?
Pour chacune des droites (Pi,Pj), on peut calculer la distance entre le point A et cette droite.

Finalement, peu-importe sur quel segment est inséré le sommet tant que :

Citation:

En insérant le point A à n'importe quel endroit dans la séquence (P1,P2,P3...,Pn), on obtient toujours un polygone fermé

et non croisé.

Il s'avère finalement que l'on soit obligé de vérifier s'il y a croisement ou non.

Citation:

De ce que j'ai compris, Biokore part d'un polygone fermé (pas forcément convexe) non croisé, à n sommets.
Il a un nouveau point.
Il veut former un nouveau polygone, toujours fermé et non-croisé, avec (n+1) sommets.
Mais il veut modifier un seul segment. Il veut insérer le nouveau point entre 2 points qui étaient adjacents dans le polygone initial.

C'est exactement ça.

Je vais donc essayer de tester sur l'ensemble des segments pour trouver les paires qui croisent ou non.

@Flodelarab :

Citation:

Je n'ai pas dans l'idée que les logiciels de CAO ou de dessin aient le moindre problème avec les chemins ou les polygones croisés. Exemple ci-dessous avec The Gimp.

Effectivement, peut-être pas tous les logiciels de dessin, je donnais une généralité. Mais presque tous, en tout cas ceux que je connais du monde de la CAO/DAO (Freecad, Autocad, Catia, SolidWorks, ProEng etc...) et même de 3D pure (3DSMax, blender, etc...) permettent d'ajouter des sommets à un polygone sans que ce dernier ne soit croisé (même s'ils doivent aussi permettre de créer des polygones croisés, mais ce n'est pas l'objet ici).

@Fœtus:

Citation:

Si tu reprends son post #5, personne n'a parlé de mettre ce point entre 3 et 5.
Mais pour pouvoir le faire, il faut mettre

4 entre 0 et 1 : 0, 4, 1, 2, 3, X, 5, 6, 7, 0
4 entre 2 et 3 : 0, 1, 2, 4, 3, X, 5, 6, 7, 0

Non, mais je souhaite conserver un ordre logique et unidirectionnel du tracé et surtout ne faire que 'insérer' un sommet, et non réorganiser l'ensemble.

Quoi qu'il en soit, encore une fois, je pense me pencher sur la solution de tbc92. Je vous dirait ce qu'il en est une fois le tout implémenté.

Encore merci à vous de vous être penché sur le problème !
06/04/2020, 05h06
BioKore

Ok, après avoir remis un peu au propre mon code et réalisé quelques essais simple, il semble que la solution "insérer le sommet au segment le plus proche de ce dernier" fonctionne. Aussi, même si ce n'est pas la meilleure solution au problème, il n'en reste pas moins que cela m'a permis de mettre en place une méthode permettant de vérifier si un point appartient à une surface donnée ou non. Dit comme ça c'est logique, mais maintenant j'arrive à coder la chose.

Je vais tâcher de faire quelques applications graphiques pour illustrer la chose mais comme ça, ça marche.

Merci à vous !