Intersection de deux rectangles

Version imprimable

Bonjour,

Voici les exos :

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

Voici mon code :

Code:

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.

Bonjour,

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

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

Citation:
Envoyé par TIFéç
Bonjour,

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

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.
Citation:
Envoyé par TIFéç
Code:

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:

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 } }

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

Code:

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:

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

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:

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:

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:

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;

Pour la question 2 :
Code:

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

14/04/2014, 10h25
Patata3
Citation:
Envoyé par thelvin

Pour la question 2 :

Code:

1 2 3 4 5 6 7 8 9 +++ + + ++++++++ + + + + + + + + ++++++++ + + +++
Merci mais c'est censé représenté deux rectangles ?
14/04/2014, 10h34
thelvin

Oui. deux rectangles qui ont une intersection, et dont aucun des deux ne contient un coin de l'autre.
14/04/2014, 11h36
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))
14/04/2014, 11h41
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 :

Citation:

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
14/04/2014, 12h05
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

Citation:

Envoyé par thelvin

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à... :aie: 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:

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à :mrgreen:

@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:

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. :(

14/04/2014, 12h23
joel.drigo

Citation:

Envoyé par Patata3

@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.

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

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
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

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:

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:

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.

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:

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 ?