Discussion :

[tevious]

Bonjour,

Je planche sur un problème de géométrie dans le cas d'une problématique industrielle (réelle).
Nous avons un tracé (contour fermé) à réaliser, ce tracé est modélisé par un ensemble de points, qui au final forment un polygone.

Dans le cadre d'une adaptation de ce tracé, je dois décaller l'ensemble à l'intérieur du polygone père, d'une distance x par rapport à chaque côté, prenons ici 1cm pour l'exemple.

J'ai déjà pas mal avancé sur la conception de l'algorithme, et je voudrais savoir si ma logique est bonne, ou si vous avez des solutions plus simples car cela me parait quand même être une usine à gaz...

J'obtiens mes points dans un tableau on ne peut plus normal avec des coordonnées par rapport à l'origine. Je parcours le tracé dans l'ordre où il m'arrive.

Tout d'abord, la fonction de décalage:
Pour chaque segment, connaissant le point de début et de fin, je peux le modéliser par une fonction affine (avec un traitement spécifique dans le cas où on est avec une droite parallèle à l'un des axes) en définissant correctement les bornes d'utilisation tout est correct. Ayant alors une équation cartésienne, je cherche à décaler ma droite d'une distance de 1cm ici.

Pour cela, je calcule le plus simple vecteur normal à ma droite, puis je le redimensionne pour qu'il ai une norme de 1. Ayant ses coordonnées, je peux calculer l'équation de ma nouvelle droite décalée: Droite d'origine -> Vecteur normal -> Vecteur normal de norme 1 -> Droite décalée.

Je souhaite faire cela avec l'ensemble de mes segments du polygone. A la fin je n'aurai qu'a résoudre les équations des nouvelles droites, ce qui me donne l'endroit où elles se coupent, pour avoir la position de mes nouveaux points donc du polygone incrusté. (PJ, rouge polygone incrusté, bleu portions des droites décalées)

On pourrait s'arrêter là, mais cela serait trop simple. En effet, pour chaque segment, on peut placer le nouveau segment décalé soit à sa droite, soit à sa gauche. Pour déterminer pour le segment courant dans quelle direction doit on se décaler, je souhaite utiliser le produit scalaire. Je détermine le vecteur associé à mes 2 points constituant le segment courant, et je fais de même avec le segment le précédent, ainsi en appliquant le produit scalaire, je peux déterminer l'angle formé entre ces 2 segments (Par exemple pour AB je regarde AB et AH). La le tour est simple, s'il est inférieur à 180° degrés je place mon décalage à droite, sinon à gauche.

Mon problème est que j'ai depuis toujours un problème avec les angles, je sais que mon logiciel travaille en radians, et que dans ce cas on compte positivement dans le sens anti-horaire (trigo). Je pense donc qu'il faut que je fasse attention aux signes dans mon interprétation des résultats.

Deuxièmement, j'ai peur que ma méthode avec le produit scalaire ne donne pas les résultats que j'espère.
Si on regarde en pièce jointe le cas pour le segment DE, où on calcule l'angle D (et de manière générale, ce sera la même chose partout où on tourne à gauche), ma règle ne fonctionne plus.

AveZ vous une idée sur comment déterminer la direction gauche/droite de décalage à partir des éléments donnés?

Si vous avez d'autres idées je suis aussi preneur, un redimensionnement via une homotéthie me parait trop complexe, et je n'ai pas d'autres idées.

Merci

[souviron34]

Ce que tu veux faire, c'est une homothétie , non ?

Un "dezoom"..

Dans ce cas, il faut calculer le vrai barycentre, le facteur de réduction, puis appliquer à chaque vecteur (barycentre, point) ce facteur..

[tevious]

Salut,

Merci de ta réponse, en effet, une homothétie est tout à fait envisageable et moins complexe que cela n'y parait:
http://www.ilemaths.net/forum-sujet-345406.html

La dernière question que je me pose concerne le calcul du facteur d'échelle pour maintenir un écart désiré entre l'ancien motif et le nouveau.
Je pense à calculer pour mon premier segment son segment décalé et après faire correspondre le facteur d'échelle avec le résultat. Mais à nouveau se pose le problème de direction du décalage...

Merci de ton aide

[Flodelarab]

Bonjour

J'ai un doute affreux sur l'homothétie. Imaginez un rectangle de 1km de longueur sur 3cm de largeur. Si on diminue d'une bordure de 1cm en largeur, on divise par 3 la largeur, alors que la longueur n'aura perdu que deux cent-millième. En plus, une similitude conserve les angles. Dans mon exemple, l'angle que forment les diagonales a clairement changé.

Contrairement aux apparences, ce n'est pas une similitude, donc pas une homothétie.

[tbc92]

Une homothétie ne convent pas du tout.
Prenons un cas extrême, à partir de la forme que tu as donnée en exemple, c'est que la distance entre F et G est inférieure à 2cm.
Dans ce cas, tu avais un U au début, et après transformation, tu obtiens un L.

Et même dans des cas moins extrêmes, si la distance FG est de 4cm, et la distance BC est de 8cm, alors dans ton résultat, tu vas avoir F'G' = 2cm, et B'C'=6cm.
Donc selon les endroits tu appliques un coefficient de 0.5, ou 0.75 ...

Autre point important, les angles 'sortants' (D et E dans ton exemple)
Si on applique au sens strict ta demande, les points D et E vont donner des portions de cercles, et non des angles D' et E'.
Tu peux faire des approximations, et remplacer les arcs de cercle par des successions de segments, ou bien, comme tu l'as dessiné, par un seul angle. Mais c'est différent de la demande initiale.

Précise donc ton besoin, par exemple (c'est un exemple, à toi de voir ce qui t'est demandé)
- La forme originale est polygonale, avec des traits qui sont tous soit verticaux, soit horizontaux
- Si dans la forme originale, on a des segments 'entrants' de moins de 2cm, alors on ne gère pas... abandon du traitement (dans l'exemple, si FG fait moins de 2cm, ça pose problème, mais si DE ou EF font moins de 2 cm, ça ne pose pas de problème !)
- En résultat, on veut aussi une forme polygonale, avec des traits verticaux ou horizontaux, et avec exactement autant de traits que l'original.

Une fois ces règles définies, on peut bosser.

[Flodelarab]

je peux le modéliser par une fonction affine (avec un traitement spécifique dans le cas où on est avec une droite parallèle à l'un des axes)

Comme c'est bizarre. On a l'impression que tu appliques une équation de la forme y=mx+p. Mais si tu utilises une équation de la forme ax+by+c=0, alors il n'y a plus de question d'axes et ton vecteur directeur de droite est u(-b;a) dans toutes les situations. Il ne reste plus qu'à trouver le point d'accroche à 1 cm de ton bord pour déterminer l'ordonnée-à-l'origine de ta droite interne et finir d'écrire son équation.

Si dans la forme originale, on a des segments 'entrants' de moins de 2cm,

Oui, il y a un problème de concavité. Si on séparait en 2 temps ? Un premier temps où on détermine la bordure interne de l'enveloppe convexe de la forme (facile). Puis on se demande ce qu'il se passe à l'intérieur de cette enveloppe.

[tevious]

Bonjour,

Merci pour vos réponses.
J'ai testé l'homothétie (ou similitudes, je ne sais plus qui est quoi, j'ai beau être ingénieur et rouler ma bille en traitement du signal, j'ai jamais été bon en géométrie, et le bac c'était il y a 9 ans ) Soit je me suis planté dans mes calculs, soit cela ne fonctionne pas, je trouve un barycentre hors du profil, à mi chemin entre D et E et 1/2 unité plus haut.
En appliquant un coeff de 0,8 à ma transformation (réduction de 20% de la figure) C' et D' sont hors du profil...

Je voudrais repartir sur mon idée de base. Concernant la notion des équations affines avec de savoir si on a soit toujours des segments parallèles aux axes: Dans mon cas on a effectivement des parallèles soit aux abscisses soit aux ordonnées, mais comme je veux quelque chose de général (Même si dans la pratique on retrouvera 90% du temps des successions de segments faisant 90° entre eux), je veux traiter tous les types possibles, d'où ces équations. Effectivement, pour modéliser mon segment j'ai d'abord la forme réduite y= mx + p car c'est ce qui est plus simple à avoir depuis 2 points. Comme il me faut du type ax + by + c = 0 pour trouver le vecteur normal (qui vaudra n(a,b) ou n(-a,-b) ) je transforme l'équation ce qui ne pose pas de problème.

A l'heure actuelle je bloque sur comment déterminer quand je calcule un décalage, si ce dernier doit être fait d'un côté ou de l'autre de mon segment. Je pensais utiliser le produit scalaire mais cela ne donne rien pour l'instant. Si on parcourt le tracé dans le sens a,b,c ...h,a je sais jusqu'au segment cd qu'on a "tourné à droite" depuis l'ancien segment et donc que mon décalage se fait à droite pour le nouveau segment. En revanche pour "de" et "ef" on a tourné à gauche et le décalage reste à faire sur la droite.
Au pire je calcule les 2 cas et à la fin je mesure le périmètre de mes nouveaux contours et prends le plus petit... mais ce n'est ni propre ni optimisé.

Concernant le problème de place avec les 2 cm, ce n'est dans le cas de l'application industrielle pas possible. Les données que l'on obtient par la CAO garantissent que ce manque d'espace ne peut pas arriver.

Merci

[souviron34]

Alors, pour bien préciser :

tu voudrais un algo qui, partant d'une forme polygonale, retire une distance fixe de chacun des côtés, c'est bien ça ?


J'ai bien un algo qui fait ça, mais il faut bien se rendre compte que dans ce cas, il arrive des moments où tu perds des points (suivant les angles, et la distance demandée, des côtés finissent pas se chevaucher, et des points disparaissent)

L'idée de base est de prendre une correspondance 1-1 pour les angles aigus "intérieurs" et une correspondance 1-3 pour les angles obtus "intérieurs" (et réciproquement) (prendre 3 points par sommet), comme dans la figure ci-dessous

(un exemple de point qui peut disparaître est l'angle aigu "intérieur" en bas (l'étoile blanche): si la distance est suffisamment grande, à un moment donné il disparaitra, lorsqu'il passera de l'autre côté de la ligne joignant le premier point de l'angle obtus à sa droite avec le dernier point à sa gauche (non visible sur le dessin))

[tbc92]

Bonjour,


.../...

A l'heure actuelle je bloque sur comment déterminer quand je calcule un décalage, si ce dernier doit être fait d'un côté ou de l'autre de mon segment. Je pensais utiliser le produit scalaire mais cela ne donne rien pour l'instant. Si on parcourt le tracé dans le sens a,b,c ...h,a je sais jusqu'au segment cd qu'on a "tourné à droite" depuis l'ancien segment et donc que mon décalage se fait à droite pour le nouveau segment. En revanche pour "de" et "ef" on a tourné à gauche et le décalage reste à faire sur la droite.
Au pire je calcule les 2 cas et à la fin je mesure le périmètre de mes nouveaux contours et prends le plus petit... mais ce n'est ni propre ni optimisé.

Concernant le problème de place avec les 2 cm, ce n'est dans le cas de l'application industrielle pas possible. Les données que l'on obtient par la CAO garantissent que ce manque d'espace ne peut pas arriver.

Merci

Ok, Tu as des formes "industrielles" relativement larges. Et donc avec des branches qui font toutes BEAUCOUP plus que 2 cm.

A partir d'un segment, pour déterminer quel est le coté intérieur et quel est le coté extérieur, le produit scalaire n'est pas adapté. Il faut passer par un produit vectoriel. Et donc passer en dimension 3.
Tu as ton plan, qui est le plan (x,y).
Tu dois visualiser ce plan dans l'espace ... donc un plan (x,y,0)... pour symboliser cela.
Et tu dois prendre un vecteur 'vertical' V (0,0,1).
Par ailleurs , tu dois imposer à ton 'utilisateur' de donner les coordonnées du polygone dans le sens des aiguilles d'une montre.
Dans ce cas, pour chaque segment MN du polygone, tu calcules le produit vectoriel entre MN et V, et ce produit vectoriel donne un vecteur 'horizontal', vers l'EXTERIEUR du polygone. ( j'ai une chance sur 2, donc à verifier. Mais ce que tu obtiendras sur le 1° segment su 1° exemple sera valable sur tous les autres cas)

A partir du moment où tu fais l'impasse sur les angles 'entrants' et sur les segments qui deviennent des points.... tu as tous les éléments pour résoudre ton problème.

[flamme34]

Bonjour,

désolé je m'incruste dans la discutions, mais je cherche également ce genre d’algorithme.
Actuellement ce que je fais c'est que je simplifie mon polygone afin d’alléger le calcule, puis je décale chaque segment d'un vecteur de translation calculé a partir du vecteur directeur et du sens de parcours de mon polygone de la manière suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
if (sensParcours == sensTrigo)  // le vecteur de translation dépend du sens de parcours du polygone! (horaire ou trigo)
     VecteurTranslation = Vecteur(currentVecteurDirecteur.y, -currentVecteurDirecteur.x);
 
else
      VecteurTranslation = Vecteur (-currentVecteurDirecteur.y, currentVecteurDirecteur.x);

Je parcours ensuite ma liste de segments décalés et je cherche les intersections entre les lignes confondus avec les segments obtenus précédement pour trouver mes nouveaux points ( c'est peut être un peut mal expliqué mais mon bout de code sera peut être plus parlant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
for (int i=0; i < nbSegments; i++)
{
	unsigned int firstIndice = (i == 0) ? nbSegments - 1 : i-1;
	unsigned int secondIndice = i;
 
	Line2f firstLine = lines[firstIndice];
	Line2f secondLine = lines[secondIndice];
	vector<Vector2f> intersections;
 
	if (firstLine.IntersectionWith (secondLine, intersections))
	{
		if ( intersections.size()>0)
		{
			droitesNouveauxSegments[firstIndice]->pointArrivee = intersections[0];
			droitesNouveauxSegments[secondIndice]->pointDepart = intersections[0];
		}
                else
                {
                        //les deux lignes sont identiques
                        droitesNouveauxSegments[firstIndice]->pointArrivee = droitesNouveauxSegments[secondIndice]->pointArrivee ;
                        droitesNouveauxSegments.erase(&droitesNouveauxSegments[secondIndice]);
                        lines.erase(&lines[secondIndice]);
                        i--;
                }
 
	}
}

Le résultat est pas trop mal pour des formes simple mais j'ai des problème lorsque la distance de décalage est trop grande est que du coup certains segments doivent être supprimé et c'est là que j'ai quelques soucis.



Auriez vous une autre manière de faire, ou une astuces pour éviter cela.

[souviron34]

Auriez vous une autre manière de faire, ou une astuces pour éviter cela.

Bonjour

Ce que j'ai exposé plus haut résout le problème..

[bretus]

Ce que j'ai exposé plus haut résout le problème..

Je plussoie souviron. Ta problématique me fait penser à la construction de "buffer" utilisés dans l'analyse spatiale (aussi connu sous le nom "offset" dans d'autres domaines).

Je t'invite à regarder ce qui se fait dans la bibliothèque JTS rubrique "BufferOp".

Si les arrondis ne sont pas adaptés à ton cas, tu pourras contrôler la forme de ces derniers.