le point est dans un rectangle ou non [Résolu]

[AnozerOne]

Bonjour

J'aimerais déterminer si un point est dans un rectangle ou non.
Le langage que j'utilises n'en n'est pas vraiment un, c'est plus une interface.
On l'appele le jass2, c'est le langage de l'éditeur de warcraft3 en ce qui concerne la création de scripts.

Bien qu'il existe une fonction qui détermine si un point est dans un rectangle, cela fonctionne uniquement pour les rectangles "normaux" (1 et 2)

Et même si elle n'existait pas, il suffirait de vérifier si le X et le Y du point sont entre les valeurs minimales et maximales.

Vous l'avez donc compris j'aimerais savoir si un point se situe dans un rectangle quelquonque (type 3).

Je suis quasiment certain que cela est possible avec des intervalles de valeurs.
Je dispose des opérateurs logiques nécessaires :
== (égal)
!= (différent)
>= (supérieur ou egal), etc.
and, not, or

et bien sûr if/then/else/elseif/endif

Evidement on connait les coordonées des 4 points.
si un matheux pouvait m'aider ca serait sympa

PS : Désolé pour la piètre image, j'avais oublié la compression jpg
Mais pas besoin d'avoir un talent d'artiste pour se faire comprendre non ?

[PRomu@ld]

Une idée pour gérer ça, et qu'on applique quelques fois en 3D, si tu sais résoudre le problème pour les rectangles 1 et 2, ramène toi via un changement de repère à ce problème. Ici, l'idée, c'est d'effectuer une rotation pour te ramener dans l'un où l'autre des cas.

Sinon, si tu ne veux pas t'embêter avec les rotations, une idée, c'est de prendre trois points : deux sur le rectangle et le point que tu souhaites tester. Tu regardes si le point à tester est à gauche ou à droite de la droite formée par les deux autres points. Le tout est de tester comme ça pour tous les points en les prenant dans un ordre trigo (inverse ou pas)

Pour résumer, tu numérotes tes points dans un sens (on va dire le sens trigo), P0,P1,P2,P3. Le point à chercher s'appelle P. Tu prends les droites (P0 P1) (P1 P2) (P2 P3) (P3 P0) et à chaque fois tu regardes si P est à gauche de chacune de ces droites, si tel est le cas, ton point P est dans le rectangle.

[AnozerOne]

hmm y'a pas vraiment de gestion d'équations de droite possibles
Du coup ton idée rotation me semble la solution la plus efficace.
Il y a des fonctions toutes faites pour savoir les différents angles.
Je vais y réfléchir

[PRomu@ld]

hmm y'a pas vraiment de gestion d'équations de droite possibles

En fait, pas besoin d'équation, si tu as la position des points ça passe tout seul. C'est de l'algorithmique géométrique de base.

On parle de tour gauche (ou de tour droit), c'est un simple calcul de déterminant.

Pour savoir si P est à gauche de P1 P2, tu calcules det( P1P , P1P2 ) et si c'est positif, c'est un tour gauche (ie: P est à gauche de P1P2). C'est tout bête.

[pseudocode]

Changeons de probleme... Comment savoir que le point P n'est pas dans le rectangle ?

Etape 1. On crée un rectangle "droit" (en rouge) autour du rectangle incliné. Si le point P n'est pas dans ce grand rectangle => il n'est pas dans l'autre [FIN].

Etape 2. on créé 4 petits rectrangles (en bleu) dans le gros rectangle, tel que les cotés du rectangle incliné soient les diagonales des 4 petits rectrangles. On cherche ensuite dans lequel des 4 petits rectrangles se trouve le point P => (R1,R2,R3 ou R4). il peut etre dans plusieurs rectangles en meme temps, dans ce cas on doit faire l'etape suivante pour chaque rectangle.

Etape 3. On doit determiner si le point P est dans la partie blanche (interieur) ou la partie rouge (exterieur) du petit rectrangle Ri. Pour cela, on regarde si la pente de la droite (coin-de-Ri,P) est plus petite/grande que la pente de la diagonale (= comparer les ratio Longueur/Largeur). S'il est dans le rouge => le point P est a l'exterieur [FIN]

Dans les autres cas, il est dedans [FIN]

Note:
- On prend le coin-de-Ri qui est au milieu du grand rectangle rouge: c'est a dire les coordonnées du rectangle incliné.
- on regarde si la pente est plus petite ou plus grande suivant le rectangle (R1,R2,R3,R4) ou est situé P. (cf dessin)

rects.jpg

l'algo total tient en quelques lignes, avec seulement des comparaisons inferieur/superieur, quelques if/else, des soustractions et des multiplications. Et a la fin, on se rend compte que le code est equivalent a la solution de promu@ld, car la comparaison de pente est equivalent au signe du determinant (car "a/b < c/d" <=> "a*d < b*c" <=> a*d-b*c<0 )

[souviron34]

Sinon (eh oui je reviens à mon dada ) simplement calculer les angles (enfin un peu ce que dit pseudocode, le sens de rotation) entre ce point et 2 sommets consécutifs.

Algo ici http://www.faqs.org/faqs/graphics/algorithms-faq/ sujet 2.03

[Zavonen]

Quand le rectangle est centré sur l'origine et que ses côtés sont parallèles aux axes.
M appartient à R ssi
-A/2<x<A/2
-B/2<y<B/2
A étant la largeur et B la longueur (à moins que ce ne soit le contraire).
Il n'y a donc qu'à se placer dans un repère centré sur le rectangle et ayant des vecteurs unitaires parallèles aux côtés.

[pseudocode]

Allez, on commence le concours... voila ma solution:

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
 
// left   = rectangle corner with lowest  "x"
// right  = rectangle corner with highest "x"
// top    = rectangle corner with highest "y"
// bottom = rectangle corner with lowest  "y"
 
boolean isInsideOrientedRectangle(int x, int y) {
 
	// outside the bounding box ?
	if (x<left.x)   return false;
	if (x>right.x)  return false;
	if (y>top.y)    return false;
	if (y<bottom.y) return false;
 
	// identify sub-regions of the bounding box and test determinant sign
	if (x<=bottom.x && y<=left.y)
		if ( (y-bottom.y)*(bottom.x-left.x) < (left.y-bottom.y)*(bottom.x-x) ) return false;
 
	if (x>=bottom.x && y<=right.y)
		if ( (y-bottom.y)*(right.x-bottom.x) < (right.y-bottom.y)*(x-bottom.x) ) return false;
 
	if (x>=top.x && y>=right.y)
		if ( (top.y-y)*(right.x-top.x) < (top.y-right.y)*(x-top.x) ) return false;
 
	if (x<=top.x && y>=left.y)
		if ( (top.y-y)*(top.x-left.x) < (top.y-left.y)*(top.x-x) ) return false;
 
	return true;
}

[PRomu@ld]

Autre idée (si tu travailles en 2D sur une image), avec un algo de remplissage, tu remplis ton rectangle, si le point est dedans, alors il est de la même couleur que le rectangle , sinon, il est de la couleur du fond ...

[AnozerOne]

@PRomu@ld : Non l'éditeur n'offre pas de telles possiblitées, mon rectangle est on ne peu plus virtuel, il est juste délimité par 4 points mais n'a pas d'existence propre.
Je peux seulement en créer de type 1 et 2, et puis sans rentrer dans les détails, même si c'était possible, c'est assez lent de créer un rectangle par rapport à des comparaisons de coordonnées et quelques calculs simples (pour le jass2).
Et comme je comptes faire cette vérification péridioquement (surement tous les 3 centièmes de secondes)

@pseudocode : dis moi ta méthode fonctionnerait aussi pour un polygône quelquonque non ?

@Zanoven : euh ouai mais pour mettre les axes parralèles il faut faire une rotation donc ...

@souviron : L'anglais et moi, on est pas copain

Sinon j'ai compris la méthode de rotation et il suffirait en prenant un point quelquonque du rectangle comme centre de rotation de recalculer les coordonnes X/Y des 3 autres points et bien sûr le point à tester.
La rotation dépendant de l'angle d'inclinaison du rectangle bien sûr (donc un calcul d'angle).
Puis une fois le rectangle horizontal ou vertical, au choix, vérifier si les coordonnees du point sont bien dans la plage.
A vrai dire j'étais parti sur cette solution mais j'attends de savoir la réponse de pseudocode sur le coté "universel" de sa solution

[PRomu@ld]

@PRomu@ld : Non l'éditeur n'offre pas de telles possiblitées, mon rectangle est on ne peu plus virtuel ...

Je disais ça pour le fun, j'étais pas tout à fait sérieux (en même temps, c'est peut-être pas si con ...)

@pseudocode : dis moi ta méthode fonctionnerait aussi pour un polygône quelquonque non ?

Intuitivement ça doit pouvoir fonctionner pour un polygone convexe, par contre pour un concave, j'ai des doutes.

[pseudocode]

Envoyé par VB_ca_rox

@pseudocode : dis moi ta méthode fonctionnerait aussi pour un polygône quelquonque non ?

oui et non.

non: les conditions de sortie "au plus tot" ne sont valides que pour le rectangle (car les sous-regions recouvrent entierement la bounding-box)

oui: la methode qui consiste a tester le signe du determinant permet de savoir de quel coté on est par rapport a une arrete. Pour un polygône quelquonque (concave ou convexe), on doit tester toutes les arrete et compter le nombre de fois qu'on est d'un coté ou de l'autre. Cet algo generique s'appelle le "Winding Number" (et vive la topologie !)



@FR119492,souviron34,Nemerle: ca sent la modération tout ca...

[FR119492]

Salut!

Il y a une méthode qui marche pour tout polygone convexe, dont les sommets sont numérotés 1, 2, 3, ..., n, le point qui t'intéresse portant le numéro 0:

Tu notes le sens du produit vectoriel des vecteurs 12 et 10. Tu calcules ensuite le sens des produits vectoriels des vecteurs 23 et 20, 34 et 30, etc. jusqu'à n1 et n0. Si le sens est toujours le même, le point 0 est à l'intérieur.

Mais ça ne te garantit que la réponse est correcte que si ton polygone est convexe. Pour le vérifier, tu notes le sens du produit vectoriel des vecteurs 12 et 23, puis 23 et 34, etc. Si le sens est toujours le même, le polygone est convexe. Sinon, tu le découpes en deux polygones. Il y a plus de chances qu'ils soient convexes. Si ton point est à l'intérieur d'un des polygones, il est à l'intérieur de leur réunion.

Ainsi tu as un algorithme qui marche dans tous les cas.

Bonne chance.
Jean-Marc Blanc

[AnozerOne]

Bon finalement la méthode de rotation est celle que je maitrise le mieux, je vais donc l'utiliser et poster le code lorsque ca sera fait.
On sait jamais si un warcraftien s'était perdu ici

[pseudocode]

Un petit truc utile a savoir dans ce cas:

cos(arctan(x)) = 1/racine(1+x²)
sin(arctan(x)) = x/racine(1+x²)

ca permet de ne pas utiliser les couteuses fonctions trigonometriques.

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
 
// left   = rectangle corner with lowest  "x"
// right  = rectangle corner with highest "x"
// top    = rectangle corner with highest "y"
// bottom = rectangle corner with lowest  "y"
boolean isInsideOrientedRectangle(int x, int y) {
	// center of rectangle
	double centerx = (left.x + right.x)/2;
	double centery = (left.y + right.y)/2;
 
	// rotation of rectangle (could be precomputed)
	double tangt = (right.y-bottom.y) / (right.x-bottom.x);
	double cosarctn = 1.0/Math.sqrt(1.0+tangt*tangt);
	double sinarctn = tangt*cosarctn;
 
	// translation+rotation of the top/right corner of rectangle  (could be precomputed)
	double rtx = top.x-centerx; 
	double rty = top.y-centery;
	double rtrx = rtx*cosarctn + rty*sinarctn;
	double rtry = -rtx*sinarctn + rty*cosarctn;
 
	// translation+rotation of the point 
	double ptx = x-centerx; 
	double pty = y-centery;
	double ptrx = ptx*cosarctn + pty*sinarctn;
	double ptry = -ptx*sinarctn + pty*cosarctn;
 
	// test
	if (ptrx<-rtrx || ptrx>rtrx) return false;
	if (ptry<-rtry || ptry>rtry) return false;
	return true;
}

[Zavonen]

Rien qu'avec les 4 opérations (sans trigo).
Soit ABCD le rectangle.
On calcule les vecteurs
AB
AD
On écrit la matrice P dont les colonnes sont ces coordonnées.
On inverse cette matrice (il n'y a qu'un déterminant à calculer)
On a alors les formules de changt de cordonnées de la base canonique à la base orthonomée ci-dessus.
Pour changer l'origine une simple translation.
Reste alors à exprimer les conditions d'inclusion le plus simplement du monde.
Pas de rotation, pas de trigo rien que les 4 opérations

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
#inverse d'une matrice (2,2)
def inverse (L):
    D=L[0]*L[3]-L[1]*L[2]
    I=[L[3],-L[2],-L[1],L[0]]
    I=[I[0]/D,I[1]/D,I[2]/D,I[3]/D]
    return I

# vecteur joignant deux points
def vecteur (A,B):
    V=[B[0]-A[0],B[1]-A[1]]
    return V

# centre de gravité d'un quadrilatère qcq
def centreG(A,B,C,D):
    return [(A[0]+B[0]+C[0]+D[0])/4,(A[1]+B[1]+C[1]+D[1])/4]

# formules de changement de repère dans le repère lié au rectangle
def chgtrep(X,Y,A,B,C,D):
    G=centreG(A,B,C,D)
    V1=vecteur(A,B)
    V2=vecteur(A,D)
    M=inverse(V1[0],V2[0],V1[1],V2[1])
    X1=X-G[0]
    Y1=Y-G[1]
    X1=M[0]*X1+M[1]*Y1
    Y1=M[2]*X1+M[3]*Y1
    return [X1,Y1]

# teste si le point est à l'intérieur du rectangle
def IsIn (M,A,B,C,D):
    NC=chgtrep(M[0],M[1],A,B,C,D)
    return abs(NC[0])<0.5 and abs(NC[1]<0.5)

[pseudocode]

Envoyé par Zavonen

Pour changer l'origine une simple translation.

Pourquoi changer l'origine ? Autant garder le point A comme origine du nouveau repere et tester que le transformé du point (M-A) a des coordonnées (x,y) entre 0 et 1.

PS: Ta multiplication de matrice m'a l'air d'etre a l'envers...

Code :

1
2
3
   X1=M[0]*X1+M[1]*Y1  #  -->  M[0]*X1+M[2]*Y1
   Y1=M[2]*X1+M[3]*Y1  #  -->  M[1]*X1+M[3]*Y1

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
 
boolean isInsideOrientedRectangle(int x, int y) {
 
	// 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;
 
	// Coordonnées du point dans la base du rectangle
	double rx = Minv[0]*(x-bottom.x) + Minv[2]*(y-bottom.y); 
	double ry = Minv[1]*(x-bottom.x) + Minv[3]*(y-bottom.y); 
 
	// test
	if (rx<0 || rx>1) return false;
	if (ry<0 || ry>1) return false;
	return true;
}

[Zavonen]

Pourquoi changer l'origine ? Autant garder le point A comme origine du nouveau repere et tester que le transformé du point (M-A) a des coordonnées (x,y) entre 0 et 1.

Oui bien sûr !!!

PS: Ta multiplication de matrice m'a l'air d'etre a l'envers...

J'écris(pour l'occasion) les matrices en lignes.

[AnozerOne]

@Zanoven : Si je veux gérer les vecteur et les matrices je vais devoir recréer ces fonctions, elles n'existent pas.
Je n'ai vu que trés brièvement les vecteurs et pas du tout les matrices (ou du moins je ne m'en rappelle plus )
Donc à moins que j'ai mal compris ton algo, il me manque des précisions.

Envoyé par pseudocode

cos(arctan(x)) = 1/racine(1+x²)
sin(arctan(x)) = x/racine(1+x²)

Euh je ne vois pas comment les utiliser

[pseudocode]

Envoyé par Zavonen

Oui bien sûr !!!

J'écris(pour l'occasion) les matrices en lignes.

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.

Envoyé par VB_ca_rox

@Zanoven : Si je veux gérer les vecteur et les matrices je vais devoir recréer ces fonctions, elles n'existent pas.

Toutes les fonctions sont deja dans le code de Zanoven ( def inverse(), vecteur(), ...)

Euh je ne vois pas comment les utiliser

cf. mon post #18