Discussion :

[thefrog]

Bonjour,

Je bute devant le problème suivant.

Je trace un mur intérieur suivant les points A,B,C,D,E,F,G
Et je voudrais calculer automatiquement le mur exterieur en indiquant une epaisseur fixe.
Il faut donc trouvé les points A2,B2,C2,D2,E2,F2,G2

Voir image ci dessous


Auriez vous une idée comment faire ca ?
Est-ce possible ?

Merci d'avance pour votre aide

[bretus]

Bonsoir,

Il manque une information pour être rigoureux. Sur ton dessin, implicitement, l'extérieur du mur est à gauche de chaque segment.

Tu dois t'en sortir en translatant les points suivant les normales aux segments.

Pour A2 tu translates A de "epaisseur mur" suivant la normale unitaire à AB
Pour G2 tu translates G de "epaisseur mur" suivant la normale unitaire à FG

Pour les points intermédiaires, tu fais combinaison des translations suivant la normale du segment précédent, et la normale du segment suivant.

C'est la détermination de la normale (par rotation du vecteur directeur du segment de +/- 90°) qui dépend du choix : intérieur à droite / intérieur à gauche.

Bye, en espérant que ça t'aide.

ps : Si tu as besoin de plus de détails, fait signe. Sans plus d'infos sur ton niveau en math, c'est pas facile d'aller plus loin.

[thefrog]

Merci pour ta réponse.
Mon niveau en math est trés mauvais.(genre seconde)

J'avais pensé à la translation.

Pour moi la translation veut dire :
Dé-rotaté la ligne AB pour la remettre a l'horizontale
Tracé la ligne A2B2, au dessus de la ligne AB
re-rotaté la ligne AB
re-rotaté la ligne A2B2

Mais le probleme dans ce cas, est que la ligne A2B2 doit etre plus longue que la ligne AB. Et la translation ne suffit pas non ?

[Zavonen]

Voici une méthode possible:
Elle est fondée sur les équations de droites et la distance d'un point à une droite.
Si une droite D a une équation ax+by+c=0 et si M(u,v) la distance de M à D est
|au+bv+c|/racine(a²+b²)
Donc tu détermines les équations de (A1B1) et de (B1C1) tu appliques la propriété ci-dessus pour trouver les coordonnées de B2 avec
d(B2,(A1B1)=d(B2,(B1C1))=e (épaisseur dur mur).
Tu trouves QUATRE candidats et tu gardes le bon en fonction de la configuration.
Pour les extrémités A2 et G2 tu exprimes que le vecteur A1A2 est orthogonal à A1B1 et que d(A2,(A1B1))=e ce qui te donne DEUX candidats. Là encore tu gardes le bon en fonction du contexte.

[bretus]

Pour moi la translation veut dire :
Dé-rotaté la ligne AB pour la remettre a l'horizontale
Tracé la ligne A2B2, au dessus de la ligne AB
re-rotaté la ligne AB
re-rotaté la ligne A2B2

Heu, non je parle de la translation, non pas de la droite, mais de A pour former A2 suivant la normale à la droite AB.

D'une "somme" de translation de B suivant la normale à AB et la normale à BC? Tu vois l'idée?

++ demande si tu ne vois pas comment réaliser les calculs

(correction : heu pardon raisonnement trop rapide. Lien vers horrible schéma supprimé)

[Zavonen]

D'une "somme" de translation de B suivant la normale à AB et la normale à BC? Tu vois l'idée?

très mauvaise idée, l'extrémité de la somme des deux vecteurs normaux n'a aucune raison d'être dans le prolongement des parallèles.
La méthode que je suggère ne fait intervenir aucune transformation géométrique pas de rotaté -derotatés, etc... pas de trigo. juste des systèmes linéaires de deux équations à deux inconnues.

[cedriku]

très mauvaise idée, l'extrémité de la somme des deux vecteurs normaux n'a aucune raison d'être dans le prolongement des parallèles.
La méthode que je suggère ne fait intervenir aucune transformation géométrique pas de rotaté -derotatés, etc... pas de trigo. juste des systèmes linéaires de deux équations à deux inconnues.

+1
pour une fois (ou plutot les rares fois) qu'un probleme de la "realite" est suffisament simple pour etre mis sous forme de systemes lineaire et qui plus est avec seulement deux inconnues... pourquoi s'embeter ?

[bretus]

Merci pour la correction Zavonen, très vilaine intuition... J'ai enlevé mon schéma scandaleux!

C'est vrai qu'en prenant un dessin plus tordu, il faut partir sur des translations suivant les vecteurs directeurs des segments entourants pour les points intermédiaires.

J'ai insisté puisque le "contexte" que tu évoques pour l'élimination des candidats se perd dans les équations que tu proposes.

Quand tu procèdes en raisonnant sur des vecteurs, tu dois pouvoir utiliser le contexte :
- Extérieur sur la gauche
- Extérieur sur la droite.

Tu ne crois pas?

[Zavonen]

Quand tu procèdes en raisonnant sur des vecteurs, tu dois pouvoir utiliser le contexte :
- Extérieur sur la gauche
- Extérieur sur la droite.

Je crois que cela n'a rien à voir. Le problème de l'orientation se pose quelle que soit la méthode utilisée.
Il y a deux possibilités:
Soit tu veux raisonner sur une figure particulière comme celle que tu as dessinée, soit tu veux un algo qui fonctionne dans tous les cas de figure possibles.
Dans le premier cas, il n'y a de mon point de vue aucun problème, il suffit de comparer les coordonnées des points.
Dans le second il y a problème car ta ligne brisée n'est pas fermée. Si tu la fermes en rejoignant l'origine la surface enserrée n'est pas convexe. Et on oublie encore le cas où elle pourrait être croisée.
Tu peux faire ainsi:
Pour chaque segment [AB] tu détermines le point M(A,B) de coordonnées ((xA+xB+yA-YB)/2, yA+yB+xB-xA)/2).
Ainsi B2 est déterminé parmi les 4 candidats par:
B2 est du même côté de A1B1 que M(A1,B1) et est du même côté de B1C1 que M(B1,C1).
Je rappelle que si ux+vy+w=0 est l'équation d'une droite la position d'un point M de coordonnées (X,Y) par rapport à cette droite est donnée par le signe de uX+vY+w.
Comme dans la méthode que je suggère tu disposes des équations, la vérification est immédiate.
J'ai utilisé ce 'truc' dans mon programme de démo pour le flocon de Von Koch (voir contributions).

[bretus]

Bonsoir,

Je ne suis pas adepte des algorithmes mono-cas, j'y suis allergique Je ne vois pas pourquoi il faudrait que la ligne brisée soit fermée... J'ai réfléchi un peu et fait quelques dessins et départs d'algos.

N'étant point butté, l'idée des intersections de droites de ta méthode semble plus efficace (il y a beaucoup trop de cas particuliers à traiter avec l'idée que je proposais en version corrigée : angle obtus, angle aigu, bref, un cauchemar)

Par contre, tu peux (et tu dois je crois) te passer d'avoir à discriminer des solutions en utilisant la notion d'orientation des segments (mur extérieur à gauche ou à droite). Tu prends directement les droites du "bon coté" du mur pour l'intersection.

Si l'utilisateur ne donne pas à l'algorithme l'orientation de la ligne brisée, il y a géométriquement deux solutions possibles : une à gauche de la ligne brisée, une à droite de la ligne brisée... Il y a une convention derrière qu'il doit te transmettre.

C'est une relation topologique que tu ne peux deviner avec la géométrie donc inutile de chercher une discrimination géométrique pour les points. Prendre en compte tous les cas, c'est prendre en compte cette relation topologique en paramètre de l'algorithme... Ce qui peut se traduire par un signe sur l'épaisseur du mur au passage.

Pour donner une idée de la convention d'orientation :


(je laisse volontairement le fait que la ligne brisée bleu résultante s'auto-intersecte. Ceci ne perturbera pas l'algorithme, par contre, il sera utile de signaler l'incohérence géométrique)

Il reste quand même à traiter à part :

- Les extrémités (car on ne peut pas procéder par intersection, il suffit de procéder par translation suivant la "bonne" normale ici)

- Les cas où on a un point Pi tel que [Pi-1 Pi] et [Pi Pi+1] sont parallèles (il faut signaler une erreur car le mur souhaité n'est pas défini)

bye!
En espérant que ça aide le posteur initial dans ses recherches.

J'essayerai de me faire ça. Je pense paramétrer mes droites à intersecter par un vecteur directeur (celui correspondant aux segments initiaux) et un point qui est facile à obtenir à l'aide de "la bonne normale" et de l'épaisseur de mur.

[Zavonen]

Les cas où on a un point Pi tel que [Pi-1 Pi] et [Pi Pi+1] sont parallèles (il faut signaler une erreur car le mur souhaité n'est pas défini)

ou plutôt éliminer purement et simplement le point Pi

[thefrog]

Merci pour vos réponses, mais je ne comprends pas tout...

Voici ce que j'ai réussi a faire pour l'instant en faisant simplement des translations et des rotations.

Comme vous voyez, les longueurs des droites exterieur ne sont pas correctes.



Y-a-t-il un moyen simple de les trouver ?
Merci

[Zavonen]

Ce script doit faire l'affaire

Code Python :

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import math
 
def Vecteur(A,B):
    """ Vecteur joignant deux points"""
    return B[0]-A[0],B[1]-A[1]
 
def Norme(V):
    """Norme d'un vecteur"""
    return math.sqrt(V[0]*V[0]+V[1]*V[1])
 
def Div (V,k):
    """Division du vecteur V par le scalaire lambda"""
    return V[0]/float(k),V[1]/float(k)
 
def Normal(A,B):
    """Vecteur n unitaire normal à (AB) tel que AB,n soit direct"""
    V=Vecteur(A,B)
    W=-V[1],V[0]
    N=Div(W,Norme(W))
    return N
 
def PointM(A,B,e):
    """Point M tel que M est à distance e de (AB) et AM orthogonal à (AB) et AB,AM direct"""
    N=Normal(A,B)
    W=Div(N,1.0/e)
    return A[0]+W[0],A[1]+W[1]
 
def Droite(A,B,e):
    """Equation de la droite parallèle à (AB) et à distance e de (AB) du côté 'gauche'"""
    V=Vecteur(A,B)
    u,v=-V[1],V[0]
    P=PointM(A,B,e)
    w=-u*P[0]-v*P[1]
    return u,v,w
 
def Intersection(D1,D2):
    """Intersection de deux droites (formules de Cramer)"""
    u1,v1,w1=D1[0],D1[1],D1[2]
    u2,v2,w2=D2[0],D2[1],D2[2]
    det=u1*v2-u2*v1
    num1=-w1*v2+w2*v1
    num2=-u1*w2+u2*w1
    return num1/det,num2/det
 
def Translate(L,e):
    """ Décalage du mur de la distance e vers la gauche """
    Resultat=[]
    Resultat.append(PointM(L[0],L[1],e)) # premier point
    for i in range(1,len(L)-1):
        A,B,C=L[i-1],L[i],L[i+1]
        D1=Droite(A,B,e)
        D2=Droite(B,C,e)
        I=Intersection(D1,D2)
        Resultat.append(I)
    P=PointM(L[-2],L[-1],e)
    Z=Vecteur(L[-2],L[-1])
    Q=P[0]+Z[0],P[1]+Z[1]
    Resultat.append(Q) #dernier point
    return Resultat
 
Mur=[ (1,1), (2,1), (3,0) ]
 
print Translate(Mur,1)

[Zavonen]

Voilà le résultat avec GUI Tkinter

Code Python :

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
import math
import Tkinter as tk 
 
def Vecteur(A,B):
    """ Vecteur joignant deux points"""
    return B[0]-A[0],B[1]-A[1]
 
def Norme(V):
    """Norme d'un vecteur"""
    return math.sqrt(V[0]*V[0]+V[1]*V[1])
 
def Div (V,k):
    """Division du vecteur V par le scalaire lambda"""
    return V[0]/float(k),V[1]/float(k)
 
def Normal(A,B):
    """Vecteur n unitaire normal à (AB) tel que AB,n soit direct"""
    V=Vecteur(A,B)
    W=-V[1],V[0]
    N=Div(W,Norme(W))
    return N
 
def PointM(A,B,e):
    """Point M tel que M est à distance e de (AB) et AM orthogonal à (AB) et AB,AM direct"""
    N=Normal(A,B)
    W=Div(N,1.0/e)
    return A[0]+W[0],A[1]+W[1]
 
def Droite(A,B,e):
    """Equation de la droite parallèle à (AB) et à distance e de (AB) du côté 'gauche'"""
    V=Vecteur(A,B)
    u,v=-V[1],V[0]
    P=PointM(A,B,e)
    w=-u*P[0]-v*P[1]
    return u,v,w
 
def Intersection(D1,D2):
    """Intersection de deux droites (formules de Cramer)"""
    u1,v1,w1=D1[0],D1[1],D1[2]
    u2,v2,w2=D2[0],D2[1],D2[2]
    det=u1*v2-u2*v1
    num1=-w1*v2+w2*v1
    num2=-u1*w2+u2*w1
    return num1/det,num2/det
 
def Translate(L,e):
    """ Décalage du mur de la distance e vers la gauche """
    Resultat=[]
    Resultat.append(PointM(L[0],L[1],e)) # premier point
    for i in range(1,len(L)-1):
        A,B,C=L[i-1],L[i],L[i+1]
        D1=Droite(A,B,e)
        D2=Droite(B,C,e)
        print D1
        print D2
        I=Intersection(D1,D2)
        Resultat.append(I)
    P=PointM(L[-2],L[-1],e)
    Z=Vecteur(L[-2],L[-1])
    Q=P[0]+Z[0],P[1]+Z[1]
    Resultat.append(Q) #dernier point
    return Resultat 
 
def DessineSegment(S,c,c_width,c_height):
    scale=100
    x1,x2=int(scale*S[0][0])+c_width/2,int(scale*S[1][0])+c_width/2
    y1,y2=c_height/2-int(scale*S[0][1]),c_height/2-int(scale*S[1][1])    
    c.create_line(x1,y1,x2,y2)
 
def DessineLigne(L,c,c_width,c_height):
    for i in range(0,len(L)-1):
        S=L[i],L[i+1]
        DessineSegment(S,c,c_width,c_height)
 
 
def main():
    """Programme principal"""
    root = tk.Tk()
    root.title("Murs")
    c_width = 600
    c_height = 600
    c = tk.Canvas(root, width=c_width, height=c_height, bg= 'white')
    c.pack()    
    Mur1=[ (-2,1), (-1,1), (1,0) , (1,-1), (-1,-2)]
    Mur2=Translate(Mur1,1)
    DessineLigne(Mur1,c,c_width,c_height)
    DessineLigne(Mur2,c,c_width,c_height)
    root.mainloop()
 
 
if __name__=='__main__':
    main()

[thefrog]

Ok merci beaucoup,
je vais tester ca...

[pseudocode]

Juste une question qui me taraude : est-ce que le point "exterieur" ne serait pas sur la bissectrice de l'angle ?

[Zavonen]

Juste une question qui me taraude : est-ce que le point "exterieur" ne serait pas sur la bissectrice de l'angle ?

Il l'est pour des raisons de symétrie.

[souviron34]

Voilà le résultat avec GUI Tkinter

ton algo marche-t-il dans l'autre sens (en diminuant) ? Comment tient-il compte de la disparition d'angles ?

J'avais fait un algo en C ajoutant (ou retranchant) une distance à une ligne brisée.

Le problème est que justement suivant les angles il peut y avoir des "overlap" de segment ou des angles qui disparaissent (angles aigus se transformant en bosses).

Parce que là tu as pris des angles convexes. Mais si il y a de la concavité ?

[Zavonen]

Mon algo fonctionne même en cas de concavité.
Voici un exemple

Code :

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

1
2
    c.pack()    
    Mur1=[ (-2,1), (-1,1), (-2,0) , (1,-1), (-1,-2)]

Voir l'image résultante.
Mais comme l'a fait justement remarquer bretus
http://www.developpez.net/forums/d75...e/#post4391820
Il peut y avoir des recouvrements et là, pas de solution (voir sa figure).

[souviron34]

ok, moi j'avais fait un algo qui ajoutait une distance (symétrique) des 2 côtés d'une ligne brisée.. Et cela tenait compte de la disparition d'angles et des recouvrements...

Je vais voir si je peux facilement séparer l'addiion d'un seul côté (il me semble que oui).

En fait, l'idée de départ était d'avoir 3 points à chaque sommets : 1 se projette sur la médiatrice, les autres sont les projections perpendiculaires sur les directions des segments adjacents.. En regardant les inversions (échange) entre ces 2 points, on élimine les croisements dûs à un angle trop aigu pour la distance..