IFS

ITERATED FUNCTION SYSTEMS

Linear transformation: maps a straight line into a straight line.

Similarity transformation: A linear transformation that preserves angles.

Affine transformations: A linear transformation that might not preserve angles.

IFS are a set of affine transformations (or "rules"), that map points in the plane by randomly chosing which of the rules to apply at each stage of the iteration according to some predefined probability.

Each transformation has the general form:

X' = A * X + B * Y + E

Y' = C * X + D * Y + F

Giving the values of the 6 coefficients A, B, C, D, E, F specifies it completely.

The general form to calculate the coefficients is:

A	B	C	D	E	F
R*cos (ANG)	- R'*sin (ANG')	+R*sin (ANG)	R'*cos (ANG')	X'-X	Y'-Y

where

R: Reduction along X direction

ANG: Rotation angle respect to the +X axis (counterclockwise +)

R': Reduction along Y direction (usually R'=R)

ANG': Rotation angle respect to the +Y axis (usually ANG'=ANG)

E: (X'-X ) Translation along X direction

F: (Y'-Y ) Translation along Y direction

Involves in general a combination of:

-Scaling

-Rotation

-Shearing

-Reflection

-Translation

Special "simple" cases (in all cases, adding a constant E and/or F shifts (translates) the points to X'=X + E, Y'=Y + F)

1) SIMPLE REDUCTION (by a single factor R)

A	B	C	D	E	F
R	0	0	R	0	0

X' = R * X

Y' = R * Y

2) GENERAL REDUCTION (by different factors R (along X) and R' (along Y))

A	B	C	D	E	F
R	0	0	R'	0	0

X' = R * X

Y' = S * Y

3) SIMPLE ROTATION (by an angle ANG, according to trigonometric convention) after SIMPLE REDUCTION (by a single factor R)

A	B	C	D	E	F
R*cos (ANG)	- R*sin (ANG)	+R*sin (ANG)	R*cos (ANG)	0	0

X' = R * cos (ANG) * X  - R * sin (ANG) * Y

Y' = R * sin (ANG) * X + R * cos (ANG)* Y

Note that : A = D, B = -C

Also, to get the angle from the coefficients: ANG = arctan (C/A) = arctan (-B/D)

Also note that if ANG = 0 you recover case 2).

Also: (for R=1) ANG=PI produces a REFLECTION (X' = -X, Y' = -Y)

4) SIMPLE ROTATION (by an angle ANG) after GENERAL REDUCTION (by different factors R (along X) and R'(along Y))

A	B	C	D	E	F
R*cos (ANG)	- R'*sin (ANG)	+R*sin (ANG)	R'*cos (ANG)	0	0

X' = R * cos (ANG) * X  - R' * sin (ANG) * Y

Y' = R * sin (ANG) * X + R'* cos (ANG)* Y

Note that : A /D = R/S, B/C = -R'/R

Also, to get the angle from the coefficients: ANG = arctan (C/A) = arctan (-B/D)

5) GENERAL ROTATION (by differents angles ANG1 (respect X axis) and ANG2 (respect Y axis) after GENERAL REDUCTION (by different factors R (along X) and S(along Y))

A	B	C	D	E	F
R*cos (ANG1)	- R'*sin (ANG2)	+R*sin (ANG1)	R'*cos (ANG2)	0	0

X' = R * cos (ANG1) * X  - R' * sin (ANG2) * Y

Y' = R * sin (ANG1) * X + R' * cos (ANG2)* Y

Note that : A /D = R/S, B/C = -R'/R

Also, to get the angle from the coefficients: ANG = arctan (C/A) = arctan (-B/D)

EXAMPLES:

1) To generate the Koch Curve:

GENERATOR

Piece 1: 1/3 REDUCTION

Piece 2: 1/3 REDUCTION, 60 deg ROTATION, followed by a 1/3 TRANSLATION in the X direction.

Piece 3: 1/3 REDUCTION, -60 deg ROTATION, followed by a 1/2 TRANSLATION in the X direction plus a 0.287 TRANSLATION in the Y direction.

Piece 4: 1/3 REDUCTION, followed by a 2/3 TRANSLATION in the X direction.

Note that PROB (or "W" for Weigth) is calculated by the IFS program from the coefficients A, B, C, and D, by calculating DET (Rule i)= ABS(A*D-B*C) for each rule and normalizing PROB (Rule i) = DET (Rule i)/(SUM ALL DETs)

RULE No.	A	B	C	D	E	F	PROB(W)
1	1/3 =0.333	0	0	1/3=0.333	0	0	1/4
2	1/3*COS(60)=0.167	-1/3*SIN(60)=-0.287	1/3*SIN(60)=+0.287	1/3*COS(60)=0.167	1/3=0.333	0	1/4
3	1/3*COS(-60)=0.167	-1/3*SIN(-60)=0.287	1/3*SIN(-60)=-0.287	1/3*COS(-60)=0.167	1/2=0.500	1/3*SIN(60)=0.287	1/4
4	1/3=0.333	0	0	1/3=0.333	2/3=0.667	0	1/4

After runing the IFS program you get this:

KOCH CURVE

SIERPINSKI CARPET

RULE No.	A	B	C	D	E	F	PROB(W)
1	1/3 =0.333	0	0	1/3=0.333	0	0	1/8
2	1/3 =0.333	0	0	1/3 =0.333	1/3=0.333	0	1/8
3	1/3 =0.333	0	0	1/3 =0.333	2/3=0.666	0	1/8
4	1/3 =0.333	0	0	1/3 =0.333	0	1/3=0.333	1/8
5	1/3 =0.333	0	0	1/3 =0.333	0	2/3=0.666	1/8
6	1/3 =0.333	0	0	1/3 =0.333	1/3=0.333	2/3=0.666	1/8
7	1/3 =0.333	0	0	1/3 =0.333	2/3=0.666	1/3=0.333	1/8
8	1/3 =0.333	0	0	1/3 =0.333	2/3=0.666	2/3=0.666	1/8

After runing the IFS program you get this:

SIERPINSKI CARPET