[Java] Flocon de Von koch

[ToTo13]

Bonjour,

voilà une petite classe qui effectue la construction du flocon de Von Koch.
Sans doute la fractale la plus connue qui lorsque le nombre d'itération tend vers l'infinie, a un périmètre infini mais une aire finie.

Code java :

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
 
import java.util.List;
import java.util.Vector;
 
import mathematiques.primitives.pointstiti.Point;
import mathematiques.primitives.pointstiti.Point3DF;
import mathematiques.primitives.pointstiti.PointI;
 
/**
 * <p>Description : Cette classe effectue le calcul du flocon de Von Koch pour un nombre d'itérations donnees.</p>
 * <p>Package necessaires : affichage, mathematiques.</p>
 * <p>Dernieres modifications :<br>
 * 23 Avril 2009 => Un petit lifting pour effacer les erreurs de jeunesse.<br>
 * Durant mes debuts en Java => Creation.</p>
 * <p>Copyright : Copyright (c) 2007.</p>
 * <p>Laboratoire : LSIS.</p>
 * <p>Equipe : Image et Modele, I&M (ex LXAO).</p>
 * 
 * @author Guillaume THIBAULT
 * @version 1.0
 */
 
public class VonKoch implements Affichable
{
 
/** Est ce que le calcul a deja ete fait ?*/
protected boolean Effectue = false ;
/** La liste des points formant le flocon.*/
protected List<Point> Liste = new Vector<Point>() ;
 
 
public VonKoch()
	{
	}
 
 
/** Methode qui lance le calcul.
 * @param ListeIn La liste des trois premiers points. Le sens des points determine la forme du flocon.
 * @param nbIterations Le nombre d'iteration a effectuer.*/
public void Compute(List<Point> ListeIn, int nbIterations)
	{
	int i ;
	if ( Effectue ) return ;
	for (i=0 ; i < ListeIn.size() ; i++)
		Liste.add(new Point3DF(ListeIn.get(i))) ;
	Calculs(nbIterations) ;
	}
 
 
/** Methode qui lance le calcul a partir d'une liste contenant des points en coordonnees entieres.
 * @param ListeIn La liste des trois premiers points. Le sens des points determine la forme du flocon.
 * @param nbIterations Le nombre d'iteration a effectuer.*/
public void ComputeI(List<PointI> ListeIn, int nbIterations)
	{
	if ( Effectue ) return ;
 
	for (int i=0 ; i < ListeIn.size() ; i++)
		Liste.add(new Point3DF(ListeIn.get(i).getX(), ListeIn.get(i).getY())) ;
 
	Calculs(nbIterations) ;
	}
 
 
/** Methode qui effectue les calculs.
 * @param nbIterations Le nombre d'iteration a effectuer.*/
protected void Calculs(int nbIterations)
	{
	int i, n ;
	Point p1, p2, p3 ;
	Point Inter = new Point3DF() ;
 
	for (n=0 ; n < nbIterations ; n++)
		for (i=0 ; i < Liste.size()-1 ; )
			{
			p1 = new Point3DF() ;
			p2 = new Point3DF() ;
			p3 = new Point3DF() ;
 
			p1.setX( Liste.get(i).getX() + (Liste.get(i+1).getX()-Liste.get(i).getX()) / 3.0 ) ;
			p1.setY( Liste.get(i).getY() + (Liste.get(i+1).getY()-Liste.get(i).getY()) / 3.0 ) ;
			p3.setX( Liste.get(i).getX() + 2.0*(Liste.get(i+1).getX()-Liste.get(i).getX()) / 3.0 ) ;
			p3.setY( Liste.get(i).getY() + 2.0*(Liste.get(i+1).getY()-Liste.get(i).getY()) / 3.0 ) ;
			Inter.setX(p3.getX()-p1.getX()) ;
			Inter.setY(p3.getY()-p1.getY()) ;
			p2.setX(Inter.getX()*Math.cos(Math.PI/3.0) + Inter.getY()*Math.sin(Math.PI/3.0)) ;
			p2.setY(-Inter.getX()*Math.sin(Math.PI/3.0) + Inter.getY()*Math.cos(Math.PI/3.0)) ;
			p2.setX(p1.getX()+p2.getX()) ;
			p2.setY(p1.getY()+p2.getY()) ;
 
			Liste.add(i+1, p1) ;
			Liste.add(i+2, p2) ;
			Liste.add(i+3, p3) ;
			i += 4 ;
			}
 
	Effectue = true ;
	}
 
 
 
 
 
 
 
 
 
 
/* ----------------------------------------------------- Les getters & autres ----------------------------------------------------- */
/** Methode qui retourne la liste des points formant le flocon.
 * @return Une List contenant les points.*/
public List<Point> getListe()
	{
	return Liste ;
	}
 
/** Methode qui vide la liste.*/
public void Reset()
	{
	Liste.clear() ;
	Effectue = false ;
	}
 
}

Un petit exemple d'utilisation :

Code java :

1
2
3
4
5
6
 
	List<Point> liste = new Vector<Point>() ;
	liste.add(new Point3DF(600,200)) ;
	liste.add(new Point3DF(100,200)) ;
	VonKoch vk5 = new VonKoch() ;
	vk5.Compute(liste, 5) ;

[ToTo13]

Et voilà mon interface Point. A vous de créer une classe de votre convenance qui l'implémente afin d'utiliser la classe VonKoch.

Code java :

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
 
package mathematiques.primitives.pointstiti;
 
/**
 * <p>Description : Interface qui permet de definir un point dans un espace de dimension N.</p>
 * <p>Packages necessaires :</p>
 * <p>Dernieres modifications :<br>
 * 11 Janvier 2009 => Creation.</p>
 * <p>Copyright : Copyright (c) 2007.</p>
 * <p>Laboratoire : LSIS.</p>
 * <p>Equipe : Image et Modele, I&M (ex LXAO).</p>
 * 
 * @author Guillaume THIBAULT
 * @version 1.0
 */
 
public interface Point extends Cloneable
{
 
/** Retourne la composante d'indice 0 du point.
 * @return La composante d'indice 0.*/
public double getX() ;
 
/** Retourne la composante d'indice 1 du point.
 * @return La composante d'indice 1.*/
public double getY() ;
 
/** Retourne la composante d'indice 2 du point.
 * @return La composante d'indice 2.*/
public double getZ() ;
 
/** Retourne tout le point (le tableau).
 * @return Le tableau representant le point.*/
public double[] get() ;
 
/** Retourne la Xieme composante du point.
 * @param x L'indice de la composante a retourner.
 * @return La valeur de la composante demandee.*/
public double get(int x) ;
 
/** Methode qui permet d'affecter tout le point par un tableau.
 * @param composantes Le tableau a copier dans le point.*/
public void set(double[] composantes) ;
 
/** Affecte les Xieme composante du point.
 * @param x L'indice de la composante a affecter.
 * @param composantes La valeur a affecter.*/
public void set(int x, double composantes) ;
 
/** Affecte la valeur passee en argument a la premiere coordonnee du point.
 * @param X La valeur a affecter.*/
public void setX(double X) ;
 
/** Affecte la valeur passee en argument a la deuxieme coordonnee du point.
 * @param Y La valeur a affecter.*/
public void setY(double Y) ;
 
/** Affecte la valeur passee en argument a la troisieme coordonnee du point.
 * @param Z La valeur a affecter.*/
public void setZ(double Z) ;
 
/** Affecte les composante en X et Y au point.
 * @param X Valeur a affecter a la composante en X du point.
 * @param Y Valeur a affecter a la composante en Y du point.*/
public void setXY(double X, double Y) ;
 
/** Affecte les composante en X, Y et Z au point.
 * @param X Valeur a affecter a la composante en X du point.
 * @param Y Valeur a affecter a la composante en Y du point.
 * @param Z Valeur a affecter a la composante en Z du point.*/
public void setXYZ(double X, double Y, double Z) ;
 
/** Methode qui retourne la taille (dimension) du point.
 * @return La dimension.*/
public int Size() ;
 
/** Retourne la dimension du point.
 * @return Dimension du point.*/
public int Dimension() ;
 
/** Methode qui determine si le point passe en argument est egal au point de cette classe.
 * @param p Le point qui doit etre compare au point de la classe.
 * @param Epsilon L'ecart maximum qu'il doit y avoir entre deux variables pour considerer qu'elles sont identiques. 
 * @return true si les deux point sont identiques, false sinon.*/
public boolean Equal(Point p, double Epsilon) ;
 
}

[pseudocode]

Exactement le même calcul avec une orientation plus "vectorielle" du problème:

Code java :

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
public class VonKochSnowflake {
 
	public List<Point2D> points = new ArrayList<Point2D>();
 
	// relative coordinates of the 3 intermediary points in an horizontal segment
	private final Point2D[] coords = new Point2D[]{ 
		new Point2D(1.0/3, 0.0), new Point2D(1.0/2, Math.sqrt(3)/6), new Point2D(2.0/3, 0.0),
	};
 
	public VonKochSnowflake(int n) {
		// initial triangle (clockwise)
		points.add( new Point2D(0.0,0.0) );
		points.add( new Point2D(0.5,Math.sqrt(3)/2) );
		points.add( new Point2D(1.0,0.0) );
 
		// for each generation
		for(int loop=0;loop<n;loop++) {
			// for each segment 
			for(int i=0;i<points.size();i++) {
				Point2D A = points.get(i);
				Point2D B = points.get((i+1)%points.size());
 
				// build a local orthogonal basis
				Point2D  o = A;
				Vector2D u = new Vector2D(B.x-A.x,B.y-A.y);
				Vector2D v = new Vector2D(-u.y,u.x);
 
				// add the 3 new points to the list
				points.add(i+1, absolute(coords[0],o,u,v) );
				points.add(i+2, absolute(coords[1],o,u,v) );
				points.add(i+3, absolute(coords[2],o,u,v) );
				i+=3;
			}
		}
	}
 
	// return the absolute coordinates of point P in basis (o,u,v) 
	private Point2D absolute(Point2D p, Point2D o, Vector2D u, Vector2D v) {
		Point2D pabs = new Point2D(0,0);
		pabs.x = o.x + p.x*u.x + p.y*v.x;
		pabs.y = o.y + p.x*u.y + p.y*v.y;
		return pabs;
	}
 
}

[Zavonen]

Bon, puisqu'il faut s'y mettre.
Pas de rotations, pas de trigo, pas de vecteurs:

Code python :

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
from math import sqrt
import Tkinter as tk 
 
class Point(object):
    """l'objet point"""
    def __init__(self,p,q):
        self.x=float(p)
        self.y=float(q)
    def __str__(self):
        return str([self.x,self.y])
 
def milieu (P1,P2):
    """milieu de deux points"""
    return Point ((P1.x+P2.x)/2,(P1.y+P2.y)/2)
 
def distance(P1,P2):
    """Distance de deux points"""
    return sqrt((P2.x-P1.x)*(P2.x-P1.x)+(P2.y-P1.y)*(P2.y-P1.y))
 
def SommetPic(P1,P2):
    """Coordonées du sommet du pic"""
    U,V=P2.x-P1.x,P2.y-P1.y
    H=milieu(P1,P2)
    d=distance(P1,P2)
    d=d*d
    X=-(V*d/sqrt(6))/(U*U+V*V)
    Y=(U*d/sqrt(6))/(U*U+V*V)
    return Point(X+H.x,Y+H.y)
 
def Fragmente(S):
    """Transformation d'un segment en 4 segments"""
    A,B=S[0],S[1]
    U=B.x-A.x
    V=B.y-A.y 
    D=SommetPic(A,B)
    xC=A.x+(1.0/3)*U
    yC=A.y+(1.0/3)*V
    C=Point(xC,yC)
    xE=A.x+(2.0/3)*U
    yE=A.y+(2.0/3)*V
    E=Point(xE,yE) 
    return [[A,C],[C,D],[D,E],[E,B]]
 
def Koch(A,B,C):
    """Le générateur"""
    L=[[A,B],[B,C],[C,A]]
    yield L
    while True:
        M=[Fragmente(S) for S in L]
        L=[]
        for X in M:
            L+=X
        yield L
 
def DessineSegment(S,c,c_width,c_height):
    scale=200
    x1,x2=int(scale*S[0].x)+c_width/2,int(scale*S[1].x)+c_width/2
    y1,y2=c_height/2-int(scale*S[0].y),c_height/2-int(scale*S[1].y)    
    c.create_line(x1,y1,x2,y2)
 
def DessineFlocon(F,c,c_width,c_height):
    for S in F:
        DessineSegment(S,c,c_width,c_height)
 
 
 
def main():
    """Programme principal"""
    root = tk.Tk()
    root.title("SnowFlake")
    c_width = 600
    c_height = 600
    c = tk.Canvas(root, width=c_width, height=c_height, bg= 'white')
    c.pack()    
    #points cycliques 1,j, j^2 racines cubiques de l'unité
    A=Point(1,0)
    B=Point(-0.5,sqrt(3)/2)
    C=Point(-0.5,-sqrt(3)/2)
    SnowFlake=Koch(C,B,A)
    for i in range(0,5):
        Flocon=SnowFlake.next()
    DessineFlocon(Flocon,c,c_width,c_height)
    root.mainloop()
    root.destroy()
 
if __name__=='__main__':
    main()

[xsheng07]

En fait, comment faire une manière récursive en créant des fonctions pour ce problème?

[ToTo13]

Bonjour,

tu remplaces ma boucle "for (n=0 ; n < nbIterations ; n++)" par un appel de la fonction avec un compteur sur nbIterations.