le point est dans un rectangle ou non

**AnozerOne** · 28/09/2007, 18h40

ok
J'ai eu une idée d'amélioration de la technique de rotation.
Les coordonnées des points sont rentrées dans un ordre quelquonque, enfin par X/Y quand même

(souplesse d'utilisation)
1) on identifie les valeurs max et min de X et de Y
2) si Xmin<X<xmax et Ymin<Y<Ymax alors le point est dans le rectangle => fini
si 2 points ont les même caractéristiques (X/Y/min/max) on arrête la vérification car le rectangle est de type 1 ou 2, et donc le point est en dehors du rectangle => fini
3)on calcule la valeur de l'angle entre le point ayant pour coordonnée Xmin et le point ayant pour coordonnée Ymin (angle D)
On effectue une rotation de -D avec pour point de rotation le point Xmin, pour le point Xmax et le point à vérifier.
Avec le point Xmin on a aussi Ymin, avec le nouveau point Xmax ayant subit une rotation on obtient Xmax et Ymax.
On refait la vérification de l'étape 2)
=> fini.

Ps : il est bien évident qu'un point ne se résume pas à une seule coordonnée X ou Y, mais bien des deux, c'est juste un raccourci de ma part.
C'est beaucoup plus clair avec un dessin

**Zavonen** · 28/09/2007, 19h19

Ca n'empeche pas que, d'apres moi, la formule est a l'envers...
Dans le code java que j'ai donné j'ai pris le meme formalisme que toi, et si je prend ta formule (X1=M[0]*X1+M[1]*Y1) ca ne marche pas. il faut prendre X1=M[0]*X1+M[2]*Y1.

Deux jeux à rien pour Pseudocode:

**pseudocode** · 28/09/2007, 19h26

Envoyé par VB_ca_rox

C'est beaucoup plus clair avec un dessin

j'espere...

Envoyé par Zavonen

Deux jeux à rien pour Pseudocode

yes... je maitrise trop bien la multiplication de matrice 2x2.

**AnozerOne** · 28/09/2007, 22h04

Bon trés bien vous l'aurez voulu je fais péter le dessin

On détermine le point ayant pour abscsisse X=Xmin
Ici le point A, on s'en sert comme centre de rotation.
Ses coordonnées ne changeront donc pas.
On repère aussi le point ayant pour ordonée Y=Ymin, ici le point B.
on repère le point ayant pour abscisse X=Xmax, ici C
On calcule l'angle entre A et B et on fait la rotation pour le point C et le point que l'on doit vérifier.
(D'ailleurs pour l'angle on pourrait plutot calculer la pente du segment AD non ?)

**pseudocode** · 28/09/2007, 23h41

Envoyé par VB_ca_rox

Bon trés bien vous l'aurez voulu je fais péter le dessin

Ah... c'est tout de suite plus clair. Effectivement ta methode fonctionne.

Mais franchement, si tu veux juste tester si un point est dans un rectangle orienté, prend l'algo du Winding Number que j'ai écrit au post #10. C'est le plus rapide, le plus simple et celui qui donne les meilleurs résultats (robuste a la discretisation).

**AnozerOne** · 29/09/2007, 15h13

C'est peut être le plus rapide dans un "vrai" langage mais je crois qu'en jass2 une suite de if/then avec des calculs simples est tout de même plus lent que des calculs un peu plus complexes et moins de if/then
Je vais tester et je vous dit quoi
PS: C'est quoi la discrétisation ?
J'ai fait une brève recherche sur wikipedia et je n'ai pas trouvé

**pseudocode** · 29/09/2007, 15h29

Envoyé par VB_ca_rox

PS: C'est quoi la discrétisation ?

par "robuste a la discretisation", je veux dire que cet algo n'a pas besoin d'utiliser des double/float si tes points ont tous des coordonnées entieres.

Si tu utlises un algo a base de trigonometrie, il y a de grandes chances que tu doivent faire un passage par les double/float.

**AnozerOne** · 29/09/2007, 15h47

Envoyé par pseudocode

par "robuste a la discretisation", je veux dire que cet algo n'a pas besoin d'utiliser des double/float si tes points ont tous des coordonnées entieres.

Si tu utlises un algo a base de trigonometrie, il y a de grandes chances que tu doivent faire un passage par les double/float.

Raté c'est des réels

Pseudocode je ne comprends pas ton code, pourquoi calcule tu le centre du rectangle. (post 18)
(Désolé pour le double post mais je ne sais pas si les edits sont considérés comme de nouveaux posts sur ce forum)

**pseudocode** · 30/09/2007, 00h49

Envoyé par VB_ca_rox

Pseudocode je ne comprends pas ton code, pourquoi calcule tu le centre du rectangle. (post 18)

sans raisons particulieres... c'est vieille habitude en 3d de recentrer les primitives. Mais c'est vrai que pour ton cas, tu peux utiliser un des coins du rectangle (cf. ton dessin du post #27)

(Désolé pour le double post mais je ne sais pas si les edits sont considérés comme de nouveaux posts sur ce forum)

quel double post ??

Gf6HqmTW · 01/10/2007, 11h47

Salut tout le monde ! Je proposerais bien une methode assez simple et rapide bien qu'à coder elle prenne un peu de place.

Il s'agit de définir les equation directrices des droite dont sont issues les cotés du rectangle (soit des segments) et une fois ces equations définies il est tres simples de savoir si un point est dessus ou dessous

Pour eviter les divisions par 0 (ce qui est mal) n'employer ce code que dans les cas d'un rectangle de type 3...

Maintenant la preuve par le code que j'ai voulu le plus clair et le plus optimisé en temps d'execution possible si toutefois qui que ce soit souhaite une precision ou une explication je suis disposé à tout reformuler tant je sais que ce qui est clair dans ma tete est souvent bordelique quand ca en sort...

Code de déclaration des variables :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Dedans : Booleen; //Le resultat qu'on recherche et qui est vrai si notre point est dans le rectangle de type 3
As     : Réel; //Coefficient directeur des droites "montantes"
Ai     : Réel; //Coefficient directeur des droites "déscendantes"
Bss    : Réel; //Constante de la droite "montante haute"
Bsi    : Réel; //Constante de la droite "montante basse"
Bis    : Réel; //Constante de la droite "déscendantes haute"
Bii    : Réel; //Constante de la droite "déscendantes basse"
Pg     : TypePoint; //Point le plus à gauche
Pd     : TypePoint; //Point le plus à droite
Ph     : TypePoint; //Point le plus haut
//Il n'est pas nécassaire de déclarer le point le plus bas (mais pas interdit non plus)
P      : TypePoint; //Mon point dont je veux définir l'apartenance à mon rectangle
Bs     : Réel;
Bi     : Réel; //Deux petites variables qui permettent de gagner du temps à l'execution (vous verez)

Code de définition des fonctions (si toutefois on peut les déclarer en ligne) :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
Fonction DefA(p1, p2 : TypePoint) Réel
Debut //DefA
| Retourne (p2.x-p1.x)/(p2.y-p1.y);
Fin //DefA
//Pour cette fonction, si le langage permet un "Inline"
//L'emploi du "Inline" permet de gagner du temps à l'execution
//Si toutefois ce mot clé n'est pas reconnu remlpacer les appels de fonction dans le code par le code de fonction directement.

Fonction DefB(p : TypePoint; a : Réel) Réel
Debut //DefB
| Retourne p.y-(a*p.x); //le parentesage est là pour plus de lisibilité uniquement
Fin //DefB
//Pour cette fonction aussi, utiliser le "Inline" si possible (sinon plan B tout ca...).

Code d'affectation des valeurs :

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

1
2
3
4
5
6
As  := DefA(Pg,Ph);
Bss := DefB(Pg,As);
Bsi := DefB(Pd,As);
Ai  := DefA(Ph,Pd);
Bis := DefB(Pd,Ai);
Bii := DefB(Pg,Ai);

And Now Lady's & Gentlmens : Last BUT NOT Least:

Code de l'expression du resultat :

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

1
2
3
4
Bs := DefB(P,As);
Bi := DefB(P,Ai);
Dedans := (Bs<Bss) ET (Bs>Bsi) ET (Bi<Bis) ET (Bi>Bii);

**AnozerOne** · 01/10/2007, 13h04

En effet c'est simple, mais c'est limité au rectangle de type 3
Je vais donc garder ma bonne vielle rotation.
Par contre je ne posterais surement pas le code avant plusieurs semaines car je pars en déplacement. (non ne pleurez pas s'il vous plaît)

à tous

**Zavonen** · 01/10/2007, 16h40

Il s'agit de définir les equation directrices des droite dont sont issues les cotés du rectangle (soit des segments) et une fois ces equations définies il est tres simples de savoir si un point est dessus ou dessous

Pour eviter les divisions par 0 (ce qui est mal) n'employer ce code que dans les cas d'un rectangle de type 3...

La méthode n'est limitée à aucun type:
Si les équations résolubles en y: y=ax+b n'existent pas toujours, les équations
ux+vy+w=0 existent toujours et sont 'presque' uniques
Avec une telle équation il est toujours possible de savoir si 2 points sont du même côté de la droite, il suffit de remplacer les variables par les les coordonnées des points et comparer les signes.
Donc M dans ABCD, se traduit par M du même côté de AB que C
et M du même côté de BC que D et M du même côté de CD que A
et M du même côté de AD que B (par exemple)
Cela dit je ne trouve pas cete méthode plus simple que celle que j'ai proposée revue et corrigée par Pseudocode.

Gf6HqmTW · 01/10/2007, 17h40

"Plus simple" etait en effet un abus de langage de ma part voulant dire que cette methode m'apparaissait plus intuitive.
Au temps pour moi !

Qui plus est lorsque je dis d'utiliser ma methode uniquement dans un cas de T3 je parle exactement de ma methode tel que je l'ai "codé" et qui ne supporte pas DivBy0

**pseudocode** · 01/10/2007, 18h29

Ca commence a nous faire un bon bestiaire de methodes:

Code java :

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
 
	/** @author=Pseudocode */
	public boolean isInsideOrientedRectangleWindingNumber(Point p) {
		// identifie de quel coté on est par rapport a chaque bord
		if (p.x<=bottom.x && p.y<=left.y) {
			if ( (p.y-bottom.y)*(bottom.x-left.x) < (left.y-bottom.y)*(bottom.x-p.x) ) return false;
		}
		if (p.x>=bottom.x && p.y<=right.y) {
			if ( (p.y-bottom.y)*(right.x-bottom.x) < (right.y-bottom.y)*(p.x-bottom.x) ) return false;
		}
		if (p.x>=top.x && p.y>=right.y) {
			if ( (top.y-p.y)*(right.x-top.x) < (top.y-right.y)*(p.x-top.x) ) return false;
		}
		if (p.x<=top.x && p.y>=left.y) {
			if ( (top.y-p.y)*(top.x-left.x) < (top.y-left.y)*(top.x-p.x) ) return false;
		}
 
		return true;
	}

Code java :

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
 
	/** @author=Pseudocode */
	public boolean isInsideOrientedRectangleTRIGO(Point p) {
		// rotation du rectangle
		double tangt = (double)(right.y-bottom.y) / (right.x-bottom.x);
		double cosarctn = 1.0/Math.sqrt(1.0+tangt*tangt);
		double sinarctn = tangt*cosarctn;
 
		// translation+rotation du coin haut/droit du rectangle
		int rtx = top.x-bottom.x; 
		int rty = top.y-bottom.y;
		double rtrx = rtx*cosarctn + rty*sinarctn;
		double rtry = -rtx*sinarctn + rty*cosarctn;
 
		// translation+rotation du point a tester 
		int ptx = p.x-bottom.x; 
		int pty = p.y-bottom.y;
		double ptrx = ptx*cosarctn + pty*sinarctn;
		double ptry = -ptx*sinarctn + pty*cosarctn;
 
		// test
		if (ptrx<0 || ptrx>rtrx) return false;
		if (ptry<0 || ptry>rtry) return false;
		return true;
	}

Code java :

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
 
	/** @author=Zavonen */
	public boolean isInsideOrientedRectangleMATRIX(Point p) {
		// Base du rectangle
		Point v1 = new Point(left.x-bottom.x,left.y-bottom.y);
		Point v2 = new Point(right.x-bottom.x,right.y-bottom.y);
 
		// Matrice de changement de base canonique->rectangle
		int[] M = new int[4];
		M[0] = v1.x; M[1] = v2.x;
		M[2] = v1.y; M[3] = v2.y;
 
		// Matrice de changement de base rectangle->canonique
		double[] Minv = new double[4];
		double d = M[0]*M[3] - M[1]*M[2];
		Minv[0] = M[3]/d;	Minv[1] = -M[2]/d;
		Minv[2] = -M[1]/d;	Minv[3] = M[0]/d;
 
		// Coordonées du point dans la base du rectangle
		double rx = Minv[0]*(p.x-bottom.x) + Minv[2]*(p.y-bottom.y); 
		double ry = Minv[1]*(p.x-bottom.x) + Minv[3]*(p.y-bottom.y); 
 
		// test
		if (rx<0 || rx>1) return false;
		if (ry<0 || ry>1) return false;
		return true;
	}

Code java :

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
 
	/** @author=GuJman */
	private double defA(Point p1,Point p2) {
		return (double)(p2.x-p1.x)/(p2.y-p1.y);
	}
	private double defB(Point p,double a) {
		return p.y-(a*p.x);
	}
	public boolean isInsideOrientedRectangleSLOPE(Point p) {
		 //Coefficient directeur des droites "montantes"
		double As  = defA(left,top);
		double Bss = defB(left,As);
		double Bsi = defB(right,As);
 
		// Coefficient directeur des droites "déscendantes"
		double Ai  = defA(top,right);
		double Bis = defB(right,Ai);
		double Bii = defB(left,Ai);
 
		// test
		double Bs = defB(p,As);
		double Bi = defB(p,Ai);
		return (Bs<Bss) && (Bs>Bsi) && (Bi<Bis) && (Bi>Bii);
	}

**Zavonen** · 01/10/2007, 23h09

La méthode GuJman a cependant un avantage, on peut la programmer sans faire intervenir de division, seulement 3 opérations donc.
Il y en a une dans la variante redonnée par toi Pseudocode, elle est liée à un calcul de 'pente' qui est inutile.

Gf6HqmTW · 02/10/2007, 07h38

Euh si elle fait intervenir la division ...

Code de la fonction DefA :

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

1
2
3
4
Fonction DefA(p1, p2 : TypePoint) Réel
Debut //DefA
| Retourne (p2.x-p1.x)/(p2.y-p1.y);
Fin //DefA

Mais je ne suis pas sur d'avoir compris ton post ?

(manque de sommeil quand tu nous tiens)

Au passage tu code quoi pour War3 VB? Tu m'enveras la map une fois finie ? Je suis un grand fan de scénar alternatifs/maps originales

**Zavonen** · 02/10/2007, 12h14

Euh si elle fait intervenir la division ...

C'est exactement ce que je dis:

Il y en a une dans la variante redonnée par toi Pseudocode, elle est liée à un calcul de 'pente' qui est inutile.

Oui, il faut dormir plus et ne pas passer la nuit devant l'écran

Gf6HqmTW · 02/10/2007, 12h26

En quoi le calcule de A (la pente) est il inutile ?
(au passage j'aimerais bien dormir la nuit mais mon patron voudrait pas ...
J'aimerais bien dormir le jour mais mes prof feraient la gueule ...
J'aimerais bien dormir entre-temps mais ma copine [CENSORED])

**Zavonen** · 02/10/2007, 20h27

une équation telle que y=ax+b est dite résolue en y, elle exprime y fonction de x, ayant deux points le coeff a (la pente) se calcule effectivement comme un quotient, cela est impossible pour les droites 'verticales' (cas de la division par zéro que tu soulignes (c'est mal)).
Mais du point de vue de la géométrie affine élémentaire. Une droite est caractérisée par une équation:
ux+vy+w=0
et cela à un facteur non nul près et indépendamment de l'orientation, cela marche pour TOUTES les droites.
Pour avoir une équation d'une droite de vecteur directeur V(v1,v2) et passant par A, on écrit que le vecteur AM est colinéaire au vecteur V en annulant un déterminant 2*2 dont les colonnes sont les coordonnées de AM et celles de V
Rien que des additions et des multiplications donc.
Cela dit pour la droite (AB) on prend le vecteur directeur AB (que des soustractions donc).
En résumé, pour tes équations de droites, tu n'as pas à passer par la forme résolue.
Cela dit, patron, profs, copine, faut assurer, mais ça pourrait être pire (le bébé qui pleure la nuit ou le chat qui miaule à potron minet).
Et puis tu peux toujours laisser tomber les équations, 'est pas vital.
Salut.