Algorithme de Bresenham en Java

Version imprimable

Bonjour,

j'ai un petit problème je m'explique, j'effectue actuellement une application android ou j'effectue une simulation grace à l'algorithme suivant :
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 pixelsSquare = 4; for (b = getPosY_Zone(); b < getHeight_Zone()-1; b = b + pixelsSquare) { for (a = getPosX_Zone(); a < getPosX_Zone() + getWidth_Zone()-1; a = a + pixelsSquare) { bestpower = -100; power = 0; for (Source s : sources) { if (s.isONSource()) { power = s.powerAtPosition( (int) (a,b) - getTotalAttenuation( s, (int) (a ,b)); if (power > bestpower) bestpower = power; } } for (int j = b; j < b + pixelsSquare; j++) { for (int i = a; i < a + pixelsSquare; i++) { simu.setPixel(i - getPosX_Zone(), j - getPosY_Zone(), PowerScale .getPowerFromValue(bestpower).getColor()); } } }
Cet algorithme me permet de parcourir l'ensemble de mon plan et d'attribuer une puissance qui est liée à une couleur et donc colorer pixel par pixel, l'ensemble des pixels de mon plan. Le calcul de la puissance s'effectue en fonction du placement de ma source sur le plan et des différents obstacles. Cette algorithme marche parfaitement mais le calcul n'est pas très rapide.
Afin d'aller plus vite j'ai décidé d'utiliser l'algorithme de Bresenham, qui va me permettre de colorer les pixels du quadrillage de mon plan en traçant des lignes de ma source jusqu'au pixel se trouvant au extrémité de mon plan. j'arrive à tracer mes différentes lignes avec le code suivant :
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 public void BresenhamAlgorithm(int x1, int y1, int x2, int y2, double power) { int x, y; int dx, dy; int xincr, yincr; int erreur; int i; int coordX, coordY; int sizePixel = 7; Canvas c = new Canvas(simu); Paint paint = new Paint(); paint.setColor(PowerScale.getPowerFromValue(power).getColor()); dx = Math.abs(x2 - x1); dy = Math.abs(y2 - y1); if (x1 < x2) { xincr = 1; } else { xincr = -1; } if (y1 < y2) { yincr = 1; } else { yincr = -1; } x = x1; y = y1; if (dx > dy) { erreur = dx / 2; for (i = 0; i < dx; i++) { x = x + xincr; erreur = erreur + dy; if (erreur > dx) { erreur = erreur - dx; y = y + yincr; } paint.setColor(PowerScale.getPowerFromValue(power).getColor()); c.drawRect(x, y, (int) (x + sizePixel), (int) (y + sizePixel), paint); } } else { erreur = dy / 2; for (i = 0; i < dy; i++) { y = y + yincr; erreur = erreur + dx; if (erreur > dy) { erreur = erreur - dy; x = x + xincr; } paint.setColor(PowerScale.getPowerFromValue(power).getColor()); c.drawRect(x, y, (int) (x + sizePixel), (int) (y + sizePixel), paint); } } }
Seulement mon problème c'est que pour le moment je met en parametre power, j'aimerai pouvoir faire modifier power a chaque fois que je trace un pixel (rectangle dans mon cas) car pour le moment ma ligne se trace mais elle est toujours de la même couleur, normal. Je ne vois pas trop comment résoudre ce problème

Je vous remercie

24/04/2015, 10h46
Arislas

Ton code te permet de dessiner une ligne entière en 1 coup non ? Si c'est le cas , je ne pense pas que ce soit possible de modifier la couleur pour chaque pixels de la lignes.

Il faudrait rester sur ton ancien algorithme.
24/04/2015, 10h50
lass7
exactement il me permet de tracer une ligne du centre de ma source jusqu'au pixel se trouvant au extremité de mon plan par exemple (0,0) pour le premier pixel. Ben il faudrait que j'arrive a récupérer a chaque fois la valeur de power et que je puisse l'intégrer dans ma methode BresenhamAlgorithme en faisant :
Code:

1 2 3 paint.setColor(PowerScale.getPowerFromValue(power) .getColor());
ce qui permettrait de dessiner un pixel a chaque fois d'une couleur différente
24/04/2015, 10h58
Arislas

Explique-moi, tu veux que ton power change de valeur à chaque pixel mais par rapport à quoi ?
24/04/2015, 11h01
lass7

En faite oui, dans l'algorithme de depart la valeur du power change à chaque fois, elle est calculer en fonction de la position de la source plus on est près de la source plus les pixels sont de couleur rouge et plus on est loin plus la couleur va vers le mauve
24/04/2015, 11h06
Arislas
Du coup, dans ton deuxième code : la ligne

Code:

paint.setColor(PowerScale.getPowerFromValue(power).getColor());

Elle récupère une nouvelle couleur, et vu que tu le fait à chaque fois que tu va dessiné la couleur devrait changer, non ?

Le truc c'est que tu ne change jamais la valeur de ton power, tu devrais essayer un truc du genre :
Code:

1 2 3 power = // fonction qui récupère la valeur de power paint.setColor(PowerScale.getPowerFromValue(power).getColor()); ...
Mais comme je ne connais pas la parti du programme qui récupère la valeur je ne peu pas trop t'aider.
24/04/2015, 11h12
lass7

ben dans mon deuxième code en faite la valeur de power change lorsque je bouge ma source, mais comme je l'ai en paramètre et ben çà me trace une ligne entière avec tous les pixels de la même couleur. Du coup j'essaye d'enlever ce paramètre la et j'aimerai faire le calcul du power directement dans ma méthode BresenhamAlgorithm pour que je puisse attribuer ma valeur de power seulement a mon pixel et non pas a ma ligne, mais je ne vois pas trop comment faire...
24/04/2015, 11h17
Arislas

Tu calcul comment la valeur de Power, n'hésite pas à mettre le code qui va avec.

Parce que si c'est un calcul simple par rapport à une valeur ça sera facile mais si il faut récupérer des valeur d'une autre classe, il me faut le code de cette classe.

Power il est dans mon algo, il est effectué comme cela :

Code:

1
2
3
 
power = s.powerAtPosition(coordX, coordY)
										- getTotalAttenuation(s, coordX, coordY);

getTotalAttenuation est obtenu avec ce code :

Code:

1
2
3
4
5
6
7
 
public double getTotalAttenuation(Source s, int x, int y) {
		attenuation = 0;
		for (Mur mur : murs)
			attenuation += mur.getAttenuationIfIntersect(s, x, y);
		return attenuation;
	}

et powerAtPosition avec celui la :

Code:

1
2
3
4
5
6
7
8
9
10
11
 
	public double powerAtPosition(int x, int y) {
		double alpha, distance;
		alpha = 300 / (double) frequenceSource;
 
		distance = Math.sqrt(Math.pow((double) (x - center.x) / 3, 2)
				+ Math.pow((double) (y - center.y) / 3, 2));
		return eirpSource
				- ((10 * Math.pow(Math.log10((4 * Math.PI) / alpha), 2)) + facteurExponentiation
						* 10 * Math.log10(distance));
	}

et sinon pour avoir la couleur je l'ai grace à cette classe :

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
 
public enum PowerScale {
 
	A(-45, Color.argb(150, 255, 51, 51)), B(-50, Color.argb(150, 255, 153, 51)), C(
			-55, Color.argb(150, 255, 255, 51)), D(-60, Color.argb(150, 153,
			255, 51)), E(-65, Color.argb(150, 51, 255, 51)), F(-70, Color.argb(
			150, 51, 255, 153)), G(-75, Color.argb(150, 51, 255, 255)), H(-80,
			Color.argb(150, 51, 153, 255)), I(-85, Color.argb(150, 51, 51, 255)), J(
			-90, Color.argb(150, 153, 51, 255)), K(-120, Color.argb(150, 255,
			255, 255));
 
 
	private double value;
	private int color;
 
 
	private PowerScale(double value, int color) {
		this.value = value;
		this.color = color;
	}
 
	public static PowerScale getPowerFromValue(double value) {
		for (PowerScale scale : PowerScale.values()) {
			if (scale.value <= value)
				return (scale);
		}
		return null;
	}
}

24/04/2015, 11h37
Arislas

J'ai eu une idée qui pourrait fonctionner mais il me manque certaines informations :

Toutes les fonctions que tu as donné, elles viennent d'une seule Class ?

Si non, donne moi le code intégrale des différentes Class
et Si oui , donne celle de la classe en entier.

Ca me permettra de mieux te guider vers la solution.

Non elles ne viennent pas d'une seule classe, je t'ai donnée la classe PowerScale, celle la tu l'a deja, ensuite getPowerAtPosition vient de la classe Source qui est la suivante :

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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
 
 
public class Source {
 
	private Point center;
	private Bitmap bitmap;
	private Canvas canvas;
	private Paint paint;
	private int frequenceSource = 2500;
	private double posX_Source, posY_Source, posZ_Source = 1.5;
	private double facteurExponentiation = 3.5;
	private static final int beam_Source = 7;
 
	/**
         * Variable indiquant si la box est allumée ou non
         */
	private boolean onSource = true;
	/**
         * booléen permettant de savoir si la Source est sélectionnée
         */
	private boolean selectedSource = false;
 
	/**
         * Puissance du signal en mW
         */
	private int powerSource = 2000;
	/**
         * Puissance Isotrope Rayonnée Equivalente
         */
	private double eirpSource = 36.0;
 
 
	/**
         * Nom de la source
         */
	private String nameSource;
 
 
	public Source() {
		center = new Point();
 
	}
 
	/**
         * Représentation d'un point d'accès WIFI
         * 
         * @param x
         *            : Abscisse de la source
         * @param y
         *            : Ordonnée de la source
         * @param puissance
         *            en mW
         */
 
	public Source(double x, double y, int frequence, double eirp) {
		this();
		center = new Point((int) x, (int) y);
		setEirpSource(eirp);
		setFrequenceSource(frequence);
	}
 
	/**
         * Représentation d'un point d'accès WI-FI
         * 
         * @param name
         * @param x
         * @param y
         * @param z
         * @param frequence
         * @param eirp
         */
	public Source(String name, double x, double y, double z, int frequence,
			double eirp) {
		this();
		center = new Point((int) x, (int) y);
		setNameSource(name);
		setFrequenceSource(frequence);
		setEirpSource(eirp);
	}
 
	/**
         * Méthode retournant vraie si le point aux coordonées (x,y) est à
         * l'intérieur de la Source.
         * 
         * @param x
         *            : Abscisse du point
         * @param y
         *            : Ordonnée du point
         * @return
         */
	public boolean containsPoint(int x, int y) {
		return center.x - 2 * beam_Source <= x
				&& x <= center.x + 2 * beam_Source
				&& center.y - 2 * beam_Source <= y
				&& y <= center.y + 2 * beam_Source;
	}
 
 
	public void doBitmap(int Thickness, int length) {
 
		/**
                 * Variables
                 */
		double nbPixelPar2 = (2 * Mur.getNbMetre_Par_Pixel());
		double scaleModif = (Plan.getScale() / Plan.getScaleStd());
 
		if (isSelectedSource()) {
			bitmap = Bitmap.createBitmap(Thickness + beam_Source, length
					+ beam_Source, Config.ARGB_8888);
			canvas = new Canvas(bitmap);
			paint = new Paint();
			paint.setColor(Color.RED);
 
			/**
                         * Dessine un cercle au lieu d'un disque
                         */
			paint.setStyle(Style.STROKE);
 
			/**
                         * Définir une épaisseur de trait
                         */
			paint.setStrokeWidth(5);
 
			canvas.drawCircle((int) ((center.x / nbPixelPar2) * scaleModif),
					(int) ((center.y / nbPixelPar2) * scaleModif), beam_Source
							/ (float) (nbPixelPar2), paint);
			canvas.drawRect((int) ((center.x / nbPixelPar2) * scaleModif) - 2
					* beam_Source,
					(int) ((center.y / nbPixelPar2) * scaleModif) - 2
							* beam_Source,
					(int) ((center.x / nbPixelPar2) * scaleModif) + 2
							* beam_Source,
					(int) ((center.y / nbPixelPar2) * scaleModif) + 2
							* beam_Source, paint);
		} else {
			bitmap = Bitmap.createBitmap(Thickness, length, Config.ARGB_8888);
			canvas = new Canvas(bitmap);
			paint = new Paint();
			paint.setColor(Color.RED);
 
			/**
                         * Dessine un cercle au lieu d'un disque
                         */
			paint.setStyle(Style.STROKE);
 
			/**
                         * Définir une épaisseur de trait
                         */
			paint.setStrokeWidth(5);
 
			canvas.drawCircle((int) ((center.x / nbPixelPar2) * scaleModif),
					(int) ((center.y / nbPixelPar2) * scaleModif), beam_Source
							/ (float) (nbPixelPar2), paint);
		}
	}
 
	/*************************/
	/** Getter && Setter **/
	/*************************/
 
 
	public double powerAtPosition(int x, int y) {
		double alpha, distance;
		alpha = 300 / (double) frequenceSource;
 
		distance = Math.sqrt(Math.pow((double) (x - center.x) / 3, 2)
				+ Math.pow((double) (y - center.y) / 3, 2));
		return eirpSource
				- ((10 * Math.pow(Math.log10((4 * Math.PI) / alpha), 2)) + facteurExponentiation
						* 10 * Math.log10(distance));
	}
 
	public void setPositionSource(double v5, double v6) {
		center.x = (int) v5;
		center.y = (int) v6;
	}
 
	public void setPuissanceSource(int puissance) {
		this.powerSource = puissance;
		setEirpSource(getPowerSource());
	}
 
 
}

et le reste se trouve dans la classe Zone :

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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
 
 
public class Zone extends Thread {
 
	private int posX_Zone, posY_Zone, width_Zone, height_Zone;
	private int a, b, pixelsSquare;
	private ArrayList<Source> sources;
	public Bitmap simu;
	private ArrayList<Mur> murs;
	private double attenuation;
 
	/**
         * Deux modes de calcul algorithmique
         */
 
	/** Mode COST231 **/
	static boolean MODE_COST231 = false;
 
	/** Mode Bresenham **/
	static boolean MODE_BRESENHAM = true;
 
	public double sizePixel = 7;
 
	public Zone(int x, int y, int width, int height, ArrayList<Source> sources,
			Bitmap simu, ArrayList<Mur> murs, int pixelsSquare) {
		this.posX_Zone = x;
		this.posY_Zone = y;
		this.width_Zone = width;
		this.height_Zone = height;
		this.sources = sources;
		this.simu = simu;
		this.murs = murs;
		this.pixelsSquare = pixelsSquare;
	}
 
	public void BresenhamAlgorithm(int x1, int y1, int x2, int y2, double power) {
		int x, y;
		int dx, dy;
		int xincr, yincr;
		int erreur;
		int i;
 
		Canvas c = new Canvas(simu);
		Paint paint = new Paint();
 
		paint.setColor(PowerScale.getPowerFromValue(power).getColor());
 
		dx = Math.abs(x2 - x1);
		dy = Math.abs(y2 - y1);
 
		if (x1 < x2) {
			xincr = 1;
		} else {
			xincr = -1;
		}
 
		if (y1 < y2) {
			yincr = 1;
		} else {
			yincr = -1;
		}
 
		x = x1;
		y = y1;
 
		if (dx > dy) {
			erreur = dx / 2;
			for (i = 0; i < dx; i++) {
				x = x + xincr;
				erreur = erreur + dy;
				if (erreur > dx) {
					erreur = erreur - dx;
					y = y + yincr;
				}
 
 
				paint.setColor(PowerScale.getPowerFromValue(power)
						.getColor());
				c.drawRect(x, y, (int) (x + sizePixel),
						(int) (y + sizePixel), paint);
 
			}
		} else {
			erreur = dy / 2;
			for (i = 0; i < dy; i++) {
				y = y + yincr;
				erreur = erreur + dx;
 
				if (erreur > dy) {
					erreur = erreur - dy;
					x = x + xincr;
				}
 
 
				paint.setColor(PowerScale.getPowerFromValue(power)
						.getColor());
				c.drawRect(x, y, (int) (x + sizePixel),
						(int) (y + sizePixel), paint);
			}
 
		}
	}
 
	public void run() {
 
		/**
                 * Variables
                 */
		double bestpower, power;
 
		if (isCostMode()) {
			for (b = getPosY_Zone(); b < getPosY_Zone() + getHeight_Zone()-1
					; b = b + pixelsSquare) {
				for (a = getPosX_Zone(); a < getPosX_Zone() + getWidth_Zone()
						- 1; a = a + pixelsSquare) {
					bestpower = -100;
					power = 0;
					for (Source s : sources) {
						if (s.isONSource()) {
							power = s.powerAtPosition(
									(int) (a,b)
									- getTotalAttenuation(
											s,
											(int) (a,b);
							if (power > bestpower)
								bestpower = power;
 
						}
					}
					for (int j = b; j < b + pixelsSquare; j++) {
						for (int i = a; i < a + pixelsSquare; i++) {
							simu.setPixel(i - getPosX_Zone(), j
									- getPosY_Zone(), PowerScale
									.getPowerFromValue(bestpower).getColor());
 
						}
 
					}
 
				}
			}
		} else {
			if (isBresenhamMode()) {
 
 
				// -------------------------------------------------------- //
				/**
                                 * Partie Gauche
                                 */
				// -------------------------------------------------------- //
				for (b = 0; b < getHeight_Zone(); b++) {
					for (a = 0; a < 1; a++) {
 
						bestpower = -100;
						power = 0;
 
						for (Source s : sources) {
							if (s.isONSource()) {
 
								int coordX_Source = (int) (s
										.getPositionSource().x );
								int coordY_Source = (int) (s
										.getPositionSource().y);
								int coordX_Zone = (int) getPosX_Zone();
								int coordY_Zone = (int) getPosY_Zone();
 
								power = s.powerAtPosition(a, b)
										- getTotalAttenuation(s, a, b);
 
								if (power > bestpower)
									bestpower = power;
 
								// val_power = bestpower;
								BresenhamAlgorithm(coordX_Source,
										coordY_Source, (a - coordX_Zone),
										(b - coordY_Zone));
 
							}
 
						}
 
					}
				}
 
			}
		}
	}
 
 
	public double getTotalAttenuation(Source s, int x, int y) {
		attenuation = 0;
		for (Mur mur : murs)
			attenuation += mur.getAttenuationIfIntersect(s, x, y);
		return attenuation;
	}
 
	public boolean isCostMode() {
		return MODE_COST231;
	}
 
	public boolean isBresenhamMode() {
		return MODE_BRESENHAM;
	}
 
}

Pour ma part, j’essaierais ça :

Code:

1
2
3
4
5
6
7
8
9
10
        public void BresenhamAlgorithm(int x1, int y1, int x2, int y2, Source s){
             int x, y;
             int dx, dy;
             int xincr, yincr;
             int erreur;                         
             int i;
             Double Power;

Et pour le calcul du nouveau Power :

Code:

1
2
3
4
 
           Power = s.powerAtPosition(coordX, coordY) - getTotalAttenuation(s,coordX, coordY);
           paint.setColor(PowerScale.getPowerFromValue(power).getColor());
           c.drawRect(x, y, (int) (x + sizePixel),(int)(y + sizePixel), paint);

Voilà, voilà. En passant en paramèter de ta fonction une source tu peu aller récupérer le méthode de calcul du PowerAtPosition();

J'espère que ça t'aide ^^

24/04/2015, 14h25
lass7

Du coup tu passes en paramètre une source et tu fais le calcul du power dans la méthode BresenhamAlgorithme c'est çà ? je vais essayer mais du coup coordX ... sont à recalculer je pense,

merci ;)
24/04/2015, 14h27
Arislas

Je ne savais pas ce qu'il fallait recalculer ou non , je vais pas tous faire non plus, mais je pense que je t'ai donner un grosse piste ^^
24/04/2015, 14h38
lass7

En faite je crois qu'on en reviens au même car oui on a la source mais lorsqu'on fait appel a la méthode qui permet de tracer elle va encore tracer un trait avec la même couleur, dans la méthode de Bresenham on ne fait pas modifier Power, je me demande si c'est vraiment possible...

Citation:
Envoyé par Arislas
Pour ma part, j’essaierais ça :

Et pour le calcul du nouveau Power :
Code:

1 2 3 4 Power = s.powerAtPosition(coordX, coordY) - getTotalAttenuation(s,coordX, coordY); paint.setColor(PowerScale.getPowerFromValue(power).getColor()); c.drawRect(x, y, (int) (x + sizePixel),(int)(y + sizePixel), paint);
Cette partie de code doit se trouver dans la méthode Bresenham pour te permettre de recalculer à chaque fois.

Je me suis peu-être mal exprimer mais cette ligne :

Code:

Power = s.powerAtPosition(coordX, coordY) - getTotalAttenuation(s,coordX, coordY);

Devrait te permettre de recalculer Power, il te suffit alors de mettre une nouvelle couleur par rapport à ce nouveau Power, non ?

24/04/2015, 14h54
lass7

J'ai résolu mon problème, j'ai effectué dans un premier temps dans une méthode à part, le calcul de mon Power en fonction de la position x,y de la source et ensuite j'ai effectuer ce calcul dans ma méthode de Bresenham a chaque fois que je devait dessiner un pixel.

Je vous remercie de votre aide