[Fractales 1/5] L-System ou système de Lindenmayer

1 pièce(s) jointe(s)

:salut:

je me suis un peu amusé (si si :mrgreen:) hier soir avec un outil que je ne connaissais pas...

Citation:

Envoyé par Wikipédia

Un L-System (ou système de Lindenmayer) est une grammaire formelle, permettant un procédé algorithmique, inventé en 1968 par le biologiste hongrois Aristid Lindenmayer qui consiste à modéliser le processus de développement et de prolifération de plantes ou de bactéries.

N'étant pas un spécialiste de ce domaine, je me suis référé (pour l'instant) à cet exemple http://en.wikipedia.org/wiki/L-system#Example_1:_Algae

Voici le code permettant de générer un L-System à partir d'une grammaire donnée et pour N itérations :

Code:

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
function str = Lsystem(grammar,N)
%LSYSTEM
%
%
 
% Author : Jerome Briot (Dut)
% Contact : dutmatlab#yahoo#fr -or- briot#cict#fr
% Profil : www.mathworks.com/matlabcentral/newsreader/author/94805
%        : www.developpez.net/forums/u125006/dut/
%
% Version : 1.0 - 02 Sep 2009
%
 
% MATLAB : 7.6.0.324 (R2008a)
% System : Linux 2.6.24-24-generic
%
 
error(nargchk(2,2,nargin));
 
str = grammar.start;
temp = cellstr(str(:));
for n = 1:N
    for krules = 1:size(grammar.rules,1)
        idx = strfind(str,grammar.rules{krules,1});
        for u = 1:numel(idx)
            temp{idx(u)} = grammar.rules{krules,2};
        end
    end
    str = [temp{:}];
    temp = cellstr(str(:));
end

La structure grammar contient les champs suivant :

grammar.name
grammar.variables
grammar.constants
grammar.start
grammar.rules

Par exemple, pour l'exemple http://en.wikipedia.org/wiki/L-system#Example_1:_Algae la grammaire associée sera :

grammar.name = 'algae';
grammar.variables = {'A' 'B'};
grammar.constants = {};
grammar.start = 'A';
grammar.rules = {'A' 'AB' ; 'B' 'A'};

Voici une première fonction permettant de tracer un L-system à parti de sa grammaire :

Code:

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
function h = drawLsystem(grammar,N,ax)
%DRAWLSYSTEM
%
%
 
% Author : Jerome Briot (Dut)
% Contact : dutmatlab#yahoo#fr -or- briot#cict#fr
% Profil : www.mathworks.com/matlabcentral/newsreader/author/94805
%        : www.developpez.net/forums/u125006/dut/
%
% Version : 1.0 - 02 Sep 2009
%
 
% MATLAB : 7.6.0.324 (R2008a)
% System : Linux 2.6.24-24-generic
%
 
error(nargchk(2,3,nargin));
 
str = Lsystem(grammar,N);
 
str = strrep(str,'A','F');
str = strrep(str,'B','F');
str = strrep(str,'G','F');
 
x = 0;
y = 0;
a = 0;
 
for n=1:numel(str)
    if str(n) == 'F'
        x(end+1) = x(end)+cos(a);
        y(end+1) = y(end)+sin(a);
    elseif str(n) == '+'
        a = a+grammar.angle;
    elseif str(n) == '-'
        a = a-grammar.angle;
    elseif str(n) == '&'
        a = -grammar.angle;
    elseif str(n) == '^'
        a = grammar.angle;
    elseif str(n) == '<'
        x(end+1) = nan;
        y(end+1) = nan;
        x(end+1) = x(end-1)+cos(pi-grammar.angle);
        y(end+1) = y(end-1)+sin(pi-grammar.angle);
    elseif str(n) == '>'
        x(end+1) = nan;
        y(end+1) = nan;
        x(end+1) = x(end-1)+cos(grammar.angle);
        y(end+1) = y(end-1)+sin(grammar.angle);
    elseif str(n) == '|'
        a = a+pi;
    elseif str(n) == '['
        posx = x(end);
        posy = y(end);
    elseif str(n) == '['
        x(end+1) = posx;
        y(end+1) = posy;
    end
 
end
 
if nargin == 2
    figure
    ax = axes;
end
axes(ax)
h = plot(x,y,'b-');
axis equal

Voici une fonction permettant de sélectionner quelques grammaires trouvées sur internet :

Code:

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
function [grammar,N] = selectLsystem(n)
%SELECTLSYSTEM
%
%
 
% Author : Jerome Briot (Dut)
% Contact : dutmatlab#yahoo#fr -or- briot#cict#fr
% Profil : www.mathworks.com/matlabcentral/newsreader/author/94805
%        : www.developpez.net/forums/u125006/dut/
%
% Version : 1.0 - 02 Sep 2009
%
 
% MATLAB : 7.6.0.324 (R2008a)
% System : Linux 2.6.24-24-generic
%
 
error(nargchk(1,1,nargin));
 
av = {'algae'
    'Fibonacci'
    'Koch curve'
    'Sierpinski triangle'
    'Sierpinski triangle 2'
    'SierpinskiCarpet'
    'Pentigree'
    'Dragon'
    'Hilbert curve'
    'Gosper curve'
    'Peano curve'
    'Quadratic Koch island'
    'Square curve'};
 
ex = av{n};
 
switch ex
 
    case 'algae'
        grammar.name = 'algae';
        grammar.variables = {'A' 'B'};
        grammar.constants = [];
        grammar.start = 'A';
        grammar.rules = {'A' 'AB' ; 'B' 'A'};
        N = 7;
    case 'Fibonacci'
        grammar.name = 'Fibonacci';
        grammar.variables = {'A' 'B'};
        grammar.constants = [];
        grammar.start = 'A';
        grammar.rules = {'A' 'B' ; 'B' 'AB'};
        N = 7;
    case 'Koch curve'
        grammar.name = 'Koch curve';
        grammar.variables = {'F'};
        grammar.constants = {'+' '-'};
        grammar.start = 'F';
        grammar.rules = {'F' 'F+F-F-F+F'};
        grammar.angle = pi/2;
        N = 6;
    case 'Sierpinski triangle'
        grammar.name = 'Sierpinski triangle';
        grammar.variables = {'A' 'B'};
        grammar.constants = {'+' '-'};
        grammar.start = 'A';
        grammar.rules = {'A' 'B-A-B' ; 'B' 'A+B+A'};
        grammar.angle = pi/3;
        N = 8;
    case 'Sierpinski triangle 2'
        grammar.name = 'Sierpinski triangle 2';
        grammar.variables = {'A' 'B'};
        grammar.constants = {'+' '-'};
        grammar.start = 'A-B-B';
        grammar.rules = {'A' 'A-B+A+B-A' ; 'B' 'BB'};
        grammar.angle = 2*pi/3;
        N = 6;
    case 'SierpinskiCarpet'
        grammar.name = 'SierpinskiCarpet';
        grammar.variables = {'F' 'G'};
        grammar.constants = {'+' '-'};
        grammar.start = 'F';
        grammar.rules = {'F' 'F+F-F-F-G+F+F+F-F' ; 'G' 'GGG'};
        grammar.angle = pi/2;
        N = 4;
    case 'Pentigree'
        grammar.name = 'Pentigree';
        grammar.variables = {'F'};
        grammar.constants = {'+' '-'};
        grammar.start = 'F-F-F-F-F';
        grammar.rules = {'F' 'F-F++F+F-F-F' };
        grammar.angle = 2*pi/5;
        N = 4;
    case 'Dragon'
        grammar.name = 'Dragon';
        grammar.variables = {'X' 'Y'};
        grammar.constants = {'F' '+' '-'};
        grammar.start = 'FX';
        grammar.rules = {'X' 'X+YF' ; 'Y' 'FX-Y'};
        grammar.angle = pi/2;
        N = 10;
    case 'Hilbert curve'
        grammar.name = 'Hilbert Curve';
        grammar.variables = {'L' 'R'};
        grammar.constants = {'F' '+' '-'};
        grammar.start = 'L';
        grammar.rules = {'L' '+RF-LFL-FR+' ; 'R' '-LF+RFR+FL-'};
        grammar.angle = pi/2;
        N = 5;
    case 'Gosper curve'
        grammar.name = 'Gosper curve';
        grammar.variables = {'X' 'Y'};
        grammar.constants = {'F' '+' '-'};
        grammar.start = 'X';
        grammar.rules = {'X' 'X+YF++YF-FX--FXFX-YF+' ; 'Y' '-FX+YFYF++YF+FX--FX-Y'};
        grammar.angle = pi/3;
        N = 4;
    case 'Peano curve'
        grammar.name = 'Peano curve';
        grammar.variables = {'F'};
        grammar.constants = {'F' '+' '-'};
        grammar.start = 'F';
        grammar.rules = {'F' 'F+F-F-F-F+F+F+F-F'};
        grammar.angle = pi/2;
        N = 4;
    case 'Quadratic Koch island'
        grammar.name = 'Quadratic Koch island';
        grammar.variables = {'F'};
        grammar.constants = {'F' '+' '-'};
        grammar.start = 'F+F+F+F';
        grammar.rules = {'F' 'F-F+F+FFF-F-F+F'};
        grammar.angle = pi/2;
        N = 3;
    case 'Square curve'
        grammar.name = 'Square curve';
        grammar.variables = {'X'};
        grammar.constants = {'F' '+' '-'};
        grammar.start = 'F+XF+F+XF';
        grammar.rules = {'X' 'XF-F+F-XF+F+XF-F+F-X'};
        grammar.angle = pi/2;
        N = 5;
end

Et le code pour la démo :

Code:

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
function demoLsystem
%DEMOLSYSTEM
%
%
 
% Author : Jerome Briot (Dut)
% Contact : dutmatlab#yahoo#fr -or- briot#cict#fr
% Profil : www.mathworks.com/matlabcentral/newsreader/author/94805
%        : www.developpez.net/forums/u125006/dut/
%
% Version : 1.0 - 02 Sep 2009
%
 
% MATLAB : 7.6.0.324 (R2008a)
% System : Linux 2.6.24-24-generic
%
 
error(nargchk(0,0,nargin));
 
figure('numbertitle','off','name','Démo L-systems  ');
 
for n = 3:9
    [grammar,N] = selectLsystem(n);
    s(n-2) = subplot(3,2,n-2);
    drawLsystem(grammar,N,s(n-2));
    title(sprintf('%s (%d itérations)',grammar.name,N))
    drawnow
 
end

Voila... si vous avez des remarques, des questions ou des suggestions, n'hésitez pas :ccool:

Mais rappelez-vous que je ne suis pas un spécialiste dans ce domaine :aie:

3 pièce(s) jointe(s)

Quelques images valent mieux qu'un long discours ;)

3 pièce(s) jointe(s)

Encore quelques aperçus

Sources :

Wikipedia : L-system (en) / L-system (fr)
L-Systems in Matlab (Cornell University)
Mathematical Figures Using Mathematica by Robert M. Dickau

à compléter...

Petite modification dans le code :

Code:

temp = cellstr(str.');

est remplacé par

Code:

temp = cellstr(str(:));

Les images sont également incluse dans l'archive lsystem.zip ;)

Citation:

Envoyé par Dut

Quelques images valent mieux qu'un long discours ;)

L'image de gauche est l'ensemble de Cantor en 2 dimensions.
Je crois bien que l'image de droite est un ensemble de Julia (même si pour ce paramètre particulier on l'appelle courbe du dragon).

On doit pouvoir faire la même chose avec des IFS (Iterative Function System) sauf que :

les IFS sont continus alors que les L-systems sont discrets
il existe des algos de coloration pour les IFS, on parle alors de flammes (voir www.apophysis.org/), alors que les L-systems sont monochromes

1 pièce(s) jointe(s)

Ajout de la courbe d'Hilbert dans SELECTLSYSTEM ;)

4 pièce(s) jointe(s)

Ajout dans SELECTLSYSTEM ;)

Gosper curve
Peano curve
Quadratic Koch island
Square curve

Mise à jour des sources issues du web

Citation:

Envoyé par SpiceGuid

On doit pouvoir faire la même chose avec des IFS (Iterative Function System) sauf que :

les IFS sont continus alors que les L-systems sont discrets
il existe des algos de coloration pour les IFS, on parle alors de flammes (voir www.apophysis.org/), alors que les L-systems sont monochromes

=> Système de fonctions itérées - IFS - Iterated function system ;)