Discussion :

[Patata3]

Bonjour,

Voici les exos :

http://img11.hostingpics.net/pics/840227Exos.jpg


Voici mon code :

Code :

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
	//Question 1
	static boolean contientPoint(Rectangle R, int x1, int y1) {
		if ( x1>= R.x && x1<= R.x+R.longueur && y1>= R.y && y1<= R.y+R.hauteur ) {
			return true;
		}
		return false;
	}
 
	//Question 2
	static boolean intersecte(Rectangle R1, Rectangle R2) {
		boolean inter = false;
		if (R1.x == R2.x && R1.y == R2.y && R1.longueur == R2.longueur && R1.hauteur == R2.hauteur) {
			return inter;
		} else if (contientPoint(R1, R2.x, R2.y) || contientPoint(R1, R2.x+R2.longueur, R2.y) || contientPoint(R1, R2.x, R2.y+R2.hauteur) || contientPoint(R1, R2.x+R2.longueur, R2.y+R2.hauteur)) {
			inter = true;
		} 
		return inter;
	}

Est-ce que mon code est correct ?

Pour la question 3 je vois pas trop ce qu'il faut faire...

Cordialement.

[TIFéç]

Bonjour,

Oui, le code semble correct. Il peut encore être un peu simplifié, par ex :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
	//Question 1
	static boolean contientPoint(Rectangle R, int x1, int y1) {
		return ( x1>= R.x && x1<= R.x+R.longueur && y1>= R.y && y1<= R.y+R.hauteur ) ;
	}
 
	//Question 2
	static boolean intersecte(Rectangle R1, Rectangle R2) {
		return (contientPoint(R1, R2.x, R2.y) 
                                   || contientPoint(R1, R2.x+R2.longueur, R2.y) 
                                   || contientPoint(R1, R2.x, R2.y+R2.hauteur) 
                                   || contientPoint(R1, R2.x+R2.longueur, R2.y+R2.hauteur));
	}

Pour la 3e question, tu peux parcourir le tableau de rectangle pour identifier les 2 points les plus excentrés, donc 4 valeurs : x et y min (en bas à gauche) et x+longueur et y+hauteur max (en haut à droite). Une fois les 4 valeurs déterminées, soit 2 points, il faut en déduire le rectangle de façon à ce qu'il ne se superpose pas à un point trouvé (donc soustraire 1 aux x et y min trouvés, et ajouter 1 aux coordonnées de l'autre point).

Bon courage

[Patata3]

Bonjour,

Oui, le code semble correct. Il peut encore être un peu simplifié, par ex :

Code :

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

1
2
3
4
	//Question 1
	static boolean contientPoint(Rectangle R, int x1, int y1) {
		return ( x1>= R.x && x1<= R.x+R.longueur && y1>= R.y && y1<= R.y+R.hauteur ) ;
	}

D'accord.

Code :

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

1
2
3
4
5
6
7
	//Question 2
	static boolean intersecte(Rectangle R1, Rectangle R2) {
		return (contientPoint(R1, R2.x, R2.y) 
                                   || contientPoint(R1, R2.x+R2.longueur, R2.y) 
                                   || contientPoint(R1, R2.x, R2.y+R2.hauteur) 
                                   || contientPoint(R1, R2.x+R2.longueur, R2.y+R2.hauteur));
	}

Tu es sûr que c'est bon ? Parce que dans le cas où les deux rectangles se superposent, la fonction doit renvoyer faux or là elle va renvoyer vrai, non ?

Pour la question 3, je n'arrive pas à visualiser le tableau en fait.
Est-ce un tableau avec un seul rectangle dans chaque case du tableau ? Si oui, le tableau a juste trois cases pour les trois rectangles ou bien on ne connait pas le nombre de rectangles et donc ni la longueur du tableau ?

Code :

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

1
2
3
4
5
6
7
	//Question 3
	static Rectangle unionRectangles(Rectangle[] Rects) {
		Rectangle englobant = new Rectangle();
		for (int i = 0; i < Rects.length; i++) {
			//je bloque
		}	
	 }

[TIFéç]

Oui, pardon, il faut effectivement gérer aussi le cas particulier...

Code :

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

1
2
3
4
5
6
7
static boolean intersecte(Rectangle R1, Rectangle R2) {
		return (! (R1.x == R2.x && R1.y == R2.y && R1.longueur == R2.longueur && R1.hauteur == R2.hauteur)
                                   && (contientPoint(R1, R2.x, R2.y) 
                                   || contientPoint(R1, R2.x+R2.longueur, R2.y) 
                                   || contientPoint(R1, R2.x, R2.y+R2.hauteur) 
                                   || contientPoint(R1, R2.x+R2.longueur, R2.y+R2.hauteur)));
	}

Pour la question 3, oui il semble s'agir d'un tableau de rectangles dont le nombre n'est pas forcément connu par avance. Ça donnerait quelque chose du genre :

Code :

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
static Rectangle unionRectangles(Rectangle[] Rects) {
		int xMin = Rects[0].x;
		int yMin = Rects[0].y;
		int xMax = Rects[0].x + Rects[0].longueur;
		int yMax = Rects[0].y + Rects[0].hauteur;
		Rectangle tempRec;
		for (int i = 0; i < Rects.length; i++) {
			tempRec = Rects[i];
			if (tempRec.x < xMin) { xMin = tempRec.x;} 
			if (tempRec.y < yMin) { yMin = tempRec.y;} 
			if (tempRec.x + tempRec.longueur > xMax) { xMax= tempRec.x + tempRec.longueur;} 
			if (tempRec.y + tempRec.hauteur > yMax) { yMax= tempRec.y + tempRec.hauteur;} 
		}
 
		// creation du rectangle englobant
		Rectangle englobant = new Rectangle();
		englobant.x = xMin - 1;
		englobant.y = yMin - 1;
		englobant.longueur = xMax - xMin + 1;
		englobant.hauteur = yMax - yMin + 1;
 
		return englobant;
	 }

A vérifier... Il me semble qu'il faut les -1 et +1 pour que le rectangle englobant ne repose pas sur l'un des points extrêmes trouvés?
Tu a fais une petite classe de test pour vérifier?

Bon courage

[Patata3]

D'accord merci ! Ca m'a l'air pas mal du tout sauf une petite erreur dans le for qui commence à 1 vu que juste avant on initialise déjà à 0 :

Code :

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
static Rectangle unionRectangles(Rectangle[] Rects) {
		int xMin = Rects[0].x;
		int yMin = Rects[0].y;
		int xMax = Rects[0].x + Rects[0].longueur;
		int yMax = Rects[0].y + Rects[0].hauteur;
		Rectangle tempRec;
		for (int i = 1; i < Rects.length; i++) {
			tempRec = Rects[i];
			if (tempRec.x < xMin) { xMin = tempRec.x;} 
			if (tempRec.y < yMin) { yMin = tempRec.y;} 
			if (tempRec.x + tempRec.longueur > xMax) { xMax= tempRec.x + tempRec.longueur;} 
			if (tempRec.y + tempRec.hauteur > yMax) { yMax= tempRec.y + tempRec.hauteur;} 
		}
 
		// creation du rectangle englobant
		Rectangle englobant = new Rectangle();
		englobant.x = xMin - 1;
		englobant.y = yMin - 1;
		englobant.longueur = xMax - xMin + 1;
		englobant.hauteur = yMax - yMin + 1;
 
		return englobant;
	 }

J'ai fait mes tests et ça fonctionne pour les deux premières mais apparemment il y a quelques soucis pour unionRectangle:

Code :

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
	public static void main(String[] args) {
        Rectangle rect1 = new Rectangle(); 
        rect1.x = 0; 
        rect1.y = 0; 
        rect1.longueur = 3; 
        rect1.hauteur = 2; 
 
        Rectangle rect2 = new Rectangle(); 
        rect2.x = 1; 
        rect2.y = 1; 
        rect2.longueur = 3; 
        rect2.hauteur = 2; 
        boolean result = contientPoint(rect1, 0, 0); 
        if (result) {  
        	System.out.println("The point is inside"); 
        } else {
        	System.out.println("The point is outsdide"); 
        }
 
        boolean result2 = intersecte(rect1, rect2); 
        if (result2) {  
        	System.out.println("Intersecte"); 
        } else {
        	System.out.println("Intersecte pas"); 
        }
 
        Rectangle[] test = {rect1, rect2};
        Rectangle result3 = new Rectangle();
        result3 = unionRectangles(test);
        System.out.println(result3.x);
        System.out.println(result3.y);
        System.out.println(result3.longueur);
        System.out.println(result3.hauteur);
 
	}

Ca retourne ça :

The point is inside
Intersecte
-1
-1
5
4

C'est censé retourner :

0
0
4
3

Du coup il faut écrire ça plutôt dans la fonction ?

Code :

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

1
2
3
4
5
6
7
8
		// creation du rectangle englobant
		Rectangle englobant = new Rectangle();
		englobant.x = xMin;
		englobant.y = yMin;
		englobant.longueur = xMax - xMin;
		englobant.hauteur = yMax - yMin;
 
		return englobant;

[thelvin]

Pour la question 2 :

Code :

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

1
2
3
4
5
6
7
8
9
 
  +++
  + +
++++++++
+ + +  +
+ + +  +
++++++++
  + +
  +++

[Patata3]

Pour la question 2 :

Code :

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

1
2
3
4
5
6
7
8
9
 
  +++
  + +
++++++++
+ + +  +
+ + +  +
++++++++
  + +
  +++

Merci mais c'est censé représenté deux rectangles ?

[thelvin]

Oui. deux rectangles qui ont une intersection, et dont aucun des deux ne contient un coin de l'autre.

[joel.drigo]

Salut,

Excusez-moi si mes mathématiques sont un peu rouillées, mais depuis quand deux rectangles égaux (même coordonnées du point haut-gauche, même largeur et même hauteur) n'ont pas d'intersection ? (cf condition R1.x == R2.x && R1.y == R2.y && R1.longueur == R2.longueur && R1.hauteur == R2.hauteur))

[TIFéç]

@thelvin : bien vu! Ça va compliquer un peu la fonction puisque du coup il ne suffit pas de tester les 4 angles mais l'ensemble des points des 4 cotés...

Pour la question 3, le résultat -1, -1, 5, 4, proviens de ce que je notais :

Il me semble qu'il faut les -1 et +1 pour que le rectangle englobant ne repose pas sur l'un des points extrêmes trouvés

D'après l'énoncé, c'est pas forcément très clair, est ce que "englobant" signifie que les rectangles peuvent être superposés par endroit ou est ce que cela ne doit jamais être le cas?
A noter que modifier la boucle pour qu'elle initialise "i = 1" nécessite de vérifier avant l'appel à la méthode que le tableau passé en paramètre contient au moins 2 éléments. Alors qu'avec "i = 0", il suffisait de tester la non nullité, mais sinon ça gagne un tour de boucle...

Bon courage

[sebagot]

Tu n'es pas obligé de regarder tous les points et je dirai même que c'est déconseillé pcq si tu as de grand rectangle ça peut prendre beaucoup de temps, par contre tu peux regarder les 4 points d'un rectangle par rapport à des intervalles.

Tu prends les 4 coins des deux rectangles et tu regardes si ça se croisent avec des tests.

Si les hauteurs deux coins gauche du rectangle verticales sont tous les deux plus grandes ou tous les deux plus petites que les deux hauteurs du coins gauche du rectangle horizontale ils ne peuvent pas se croiser. Sinon tu vérifies les largeurs des deux coins sup du rectangles verticales s'ils sont tous les deux plus grandes ou plus petites que les largeurs des deux coins sup du rectangles horizontale ils ne peuvent pas se croiser.

Je pense que ce test reprend toutes les possibilités

[Patata3]

Oui. deux rectangles qui ont une intersection, et dont aucun des deux ne contient un coin de l'autre.

Oh non j'avais oublié ce cas là... J'ai essayé autre chose mais ça ne marche pas non plus je commence à écrire n'importe quoi, je vais exploser si je ne réussi pas à trouver :

Code :

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
	static boolean intersecte(Rectangle R1, Rectangle R2) {
 
		/*Quand le rectangle est entièrement inclus dans l'autre rectangle*/
		boolean rectToutInclus = ((contientPoint(R1, R2.x, R2.y) 
                && contientPoint(R1, R2.x+R2.longueur, R2.y) 
                && contientPoint(R1, R2.x, R2.y+R2.hauteur) 
                && contientPoint(R1, R2.x+R2.longueur, R2.y+R2.hauteur)));
 
		/*ou quand le rectangle est entièrement exlus de l'autre rectangle*/
		boolean rectToutExclu = ((!contientPoint(R1, R2.x, R2.y) 
                && !contientPoint(R1, R2.x+R2.longueur, R2.y) 
                && !contientPoint(R1, R2.x, R2.y+R2.hauteur) 
                && !contientPoint(R1, R2.x+R2.longueur, R2.y+R2.hauteur)));
 
		/*inter est faux donc pour tous les autres cas, les deux rectangles s'intersectent*/
		return (!(rectToutInclus || rectToutExclu));
 
	}

J'ai vraiment écrit n'importe quoi là

@joel.drigo Oui, c'est vrai mais l'énoncé veut qu'on fasse comme ça, rien que pour nous embêter...

La je sèche pour ces deux fonctions, je risque d'avoir un exercice du même style en examen en plus.

Sinon j'ai fait un exo quasi identique en TD :

http://img15.hostingpics.net/pics/344290Enveloppe.jpg

Sauf qu'avant on donne deux structures :

Code :

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
	public static class Point {
		public double x0;// abcisse du point
		public double y0;// ordonnée du point
		public String toString (){
			return "("+x0+", "+y0+")";
		}
	}
 
	public static class Rectangle {
		public Point hg;// coin supérieur gauche
		public double l;// largeur
		public double h;// hauteur
		public String toString (){
			return "<"+hg+", "+l+" \u00d7 "+h+">";
		}
	}

Même avec ça je n'y arrive pas.

[joel.drigo]

@joel.drigo Oui, c'est vrai mais l'énoncé veut qu'on fasse comme ça, rien que pour nous embêter...

Ah oui, effectivement, je n'avais lu l'énoncé. Bizarre d'appeler la méthode intersecte alors. Toutefois, pour répondre à cette condition, il suffit de s'appuyer sur la méthode contientPoint dans ce cas : si un rectangle contient les 4 sommets de l'autre, la méthode renvoie false : pas besoin de la condition spécifique que j'ai citée.

[TIFéç]

A vérifier, mais il me semble que ça le fait...

Code :

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
static boolean intersecte(Rectangle R1, Rectangle R2) {
	return (
		// Exclusion du cas de rectangles superposes
		! (R1.x == R2.x && R1.y == R2.y && R1.longueur == R2.longueur && R1.hauteur == R2.hauteur)
 
		&& (
			// 1 coin de rectangle dans un autre
			contientPoint(R1, R2.x, R2.y) 
			|| contientPoint(R1, R2.x+R2.longueur, R2.y) 
			|| contientPoint(R1, R2.x, R2.y+R2.hauteur) 
			|| contientPoint(R1, R2.x+R2.longueur, R2.y+R2.hauteur)
 
			// Cas de rectangles croises
			// La longueur d'un rectangle est comprise dans celle de l'autre
			// et la hauteur de l'autre est encadree par celle du premier
			|| (
				R1.x < R2.x && R2.x + R2.longueur > R1.x + R1.longueur
				&& R2.y < R1.y && R1.y + R1.hauteur > R2.y + R2.hauteur
			)
			|| (
				R2.x < R1.x && R1.x + R1.longueur > R2.x + R2.longueur
				&& R1.y < R2.y && R2.y + R2.hauteur > R1.y + R1.hauteur
			)
		)
	);
}

Par contre c'est peut être plus hyper lisible de laisser ça dans le return...

Bon courage

[Nico02]

Salut,

Dans ce genre de cas il est plus facile de raisonner à l'inverse pour dire si il y a intersection. Plutôt que se savoir si il y a intersection, on va plutôt chercher à savoir si on est sur qu'il n'y en a pas.

Code :

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
 
        1     2
	++++++++
	+      +
	+      +
	+      +
	+      +
	++++++++
         3    4	     5     6
			++++++++
			+      +
		        +      +
			+      +
			+      +
			++++++++
			7      8

On va chercher à savoir si la distance entre les abscisses min et max ainsi que la distance entre les ordonnées min et max des 2 rectangles, ne sont pas positive.

Pour ça on va comparer
- la distance sur X entre ( le point le plus a droite du premier et celui le plus gauche du deuxième ). On utilisera ici la distance (4,5)
- la distance sur Y entre ( le point le bas du premier et celui le plus haut du deuxième ). On utilisera ici la distance (3,5)

On sait que si l'une de ces deux distance est positive, alors les 2 rectangles ne peuvent pas avoir d'intersection. Ce qui est intéressant c'est que le contraire est vrai aussi !

Il faudra par contre gérer le cas où l'un et inclue dans l'autre. Mais pour ça on peut utiliser la fonction contientPoint() du premier éxo.

Ce qui donne :

Code :

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
 
public boolean intersect( Rectangle r1, Rectangle r2 ){
 
	// On élimine le cas où l'un est inclue dans l'autre
	if ( ( contientPoint( r1.x ,r2 ) && contientPoint( r1.y ,r2 ) && contientPoint( r1.x + r1.longueur ,r2 ) && contientPoint( r1.x + r1.hauter ,r2 ) ) ||
	     ( contientPoint( r2.x ,r1 ) && contientPoint( r2.y ,r1 ) && contientPoint( r2.x + r2.longueur ,r1 ) && contientPoint( r2.x + r2.hauter ,r1 ) ) )
			 return false;
 
	// On récupère les points bas-droit
	int r1x2 = r1.x + r1.longueur;
	int r2x2 = r2.x + r2.longueur;
 
	// Et les points haut gauche
	int r1y2 = r1.y - r1.hauter;
	int r2y2 = r2.y - r2.hauter;
 
	// Vu qu'on ne sait pas dans quel autre sont les rectangles, on va utiliser les fonctions min et max pour le determiner.
	int dxGauche = Math.max( r1.x, r2.x );
	int dxDroite = Math.min( r1x2, r2x2 );
	// Pour l'axe des abscisses 
	if ( dxGauche - dxDroite  >= 0 ) // Si la distance est positive
		return false;
	else { 
		// On fait pareil avec l'axe des ordonnées
		int dyTop = Math.max( r1.y, r2.y );
		int dyBot = Math.min( r1y2, r2y2 );
 
		if ( dyBot - dyTop  >= 0 )
			return false;
	}
	return true;
}

A voir pour ton exo pour le signe >= si tu ne dois pas utiliser > à la place.

Cdt.

[Patata3]

Je crois qu'on se fatigue pour rien, il y a bien plus simple :

http://leetcode.com/2011/05/determin...s-overlap.html

Ce qui donne sauf erreur de ma part :

Code :

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
	static boolean intersecte(Rectangle R1, Rectangle R2) {	
 
		boolean inter = false;
		//Si R2 est inclus dans R1
		if ((contientPoint(R1, R2.x, R2.y) 
                && contientPoint(R1, R2.x+R2.longueur, R2.y) 
                && contientPoint(R1, R2.x, R2.y+R2.hauteur) 
                && contientPoint(R1, R2.x+R2.longueur, R2.y+R2.hauteur)) || 
               //ou si R1 est inclus dans R2 
                ((contientPoint(R2, R1.x, R1.y) 
                        && contientPoint(R2, R1.x+R1.longueur, R1.y) 
                        && contientPoint(R2, R1.x, R1.y+R1.hauteur) 
                        && contientPoint(R2, R1.x+R1.longueur, R1.y+R1.hauteur)))) {
			inter = false;
		} else if (R1.y <= R2.y + R2.hauteur && R1.y + R1.hauteur >= R2.y && 
				   R1.x + R1.longueur >= R2.x && R1.x <= R2.x + R2.longueur) {
			inter = true;
		}
		return inter;
	}

C'est bien ça ? Bizarrement quand je test cette fonction, ça ne marche pas... c'est peut-être ma fonction de test qui est fausse, non ?