Discussion :

[adiiii]

Bonjour,
Je dois développer un code qui teste la présence d'un point dans un polygône quelconque. Le point étant représenté par ses coordonnées (x,y) : on travaille dans un plan. Le polygône est représenté par une liste ordonnée de points qui permet sa construction : si les points sont P1,P2,P3,P4,P5, on relie d'abord P1 à P2, puis P2à P3... et enfin P5à P1.
Tout ça doit être fait en C, mais si vous avez la moindre idée, ...
Je vous remercie !

[Ange_blond]

ce n'est pas tellement difficile

Voilà une méthode :
Tu aura besoin d'une fonction qui teste l'intersection de 2 segments.
(genre tu utilise les equations de droite pr détecter l'intersection... tu as meme pas besoin de savoir le point exact dans ce cas là)

Ensuite tu défini un nouveau segment depuis ton point jusqu'a n'importe quel point tres loin (en dehors du polygone) (genre un nouveau point vers les infini)

Ensuite tu teste l'intersection de ce nouveau segment avec chacun des segments de ton polygone (P1P2, puis P2P3....)

Si il y a intersection (ET UNE SEULE) alors tu es à l'intérieur. (donc faut les compter toutes pour etre sur car un nbre pair d'intersections sginifie que tu es en dehors)



Autre méthode tu fait la somme des angles de ton point vers chaque point du polygone... si = 360 tu es dedans (enfin je crois)

[babar63]

Voilà une méthode :
Tu aura besoin d'une fonction qui teste l'intersection de 2 segments.
(genre tu utilise les equations de droite pr détecter l'intersection... tu as meme pas besoin de savoir le point exact dans ce cas là)

Ensuite tu défini un nouveau segment depuis ton point jusqu'a n'importe quel point tres loin (en dehors du polygone) (genre un nouveau point vers les infini)

Ensuite tu teste l'intersection de ce nouveau segment avec chacun des segments de ton polygone (P1P2, puis P2P3....)

A préciser quand même que ce n'est pas pour un polygone quelconque mais convexe... Pour la deuxième méthode je ne sais pas (je suppose que c'est pareil non?). Sinon une autre méthode (plus rapide?), pour chaque arêtes : Soit P le point à tester, N la normale de l'arête, et A un point de l'arête, alors si le produit scalaire : N.AP >= 0 (Tout ce beau monde doit être normalisé), tu es à l'intérieur(de l'arête courante).

[Ange_blond]

le test par intersection fonctionne pour n'importe quel type de polygone si je ne me trompe pas...

[babar63]

le test par intersection fonctionne pour n'importe quel type de polygone si je ne me trompe pas...

Euh c'est que j'ai du mal comprendre lorsque tu disais :

Si il y a intersection (ET UNE SEULE) alors tu es à l'intérieur. (donc faut les compter toutes pour etre sur car un nbre pair d'intersections sginifie que tu es en dehors)

Si le nombre d'intersections est impair alors en effet ca fonctionne pour n'importe quel type de polygone, en revanche si l'on s'arrête à "UNE SEULE" intersection alors ça ne fonctionne que pour les polygones convexes

[babar63]

Ensuite tu défini un nouveau segment depuis ton point jusqu'a n'importe quel point tres loin (en dehors du polygone) (genre un nouveau point vers les infini)

Il me semble que dans ce cas il serait préférable de considérer l'intersection entre une droite horizontal (pourquoi s'embêter avec des points "très loin"...) et l'arête en question, ça devrait également facilité le calcul d'intersection

[Ange_blond]

Il me semble que dans ce cas il serait préférable de considérer l'intersection entre une droite horizontal (pourquoi s'embêter avec des points "très loin"...) et l'arête en question, ça devrait également facilité le calcul d'intersection

C'est ce que j'avais en tête en fait... j'ai pas été clair...

Et oui en effet : nombre impair d'intersections !

[ac_wingless]

Attention aussi au contexte d'utilisation de cet algorithme. Si c'est pour détecter un appui sur bouton défini par un polygone, ou pour savoir sur quel objet d'une scène l'utilisateur a cliqué, ça va marcher (en fait non, mais ça va marcher souvent, et quand ça marche pas c'est pas grave).
Par contre, si c'est pour une application géométrique, rien que le fait de savoir en (2D!) si un point est à droite ou à gauche d'un segment est un problème bien plus difficile que le problème initial. Alors un calcul d'intersection de segment ...
Par exemple, si le but de l'OP est de construire une enveloppe convexe, on tomberait en plein sur ceci .

[babar63]

Si c'est pour détecter un appui sur bouton défini par un polygone, ou pour savoir sur quel objet d'une scène l'utilisateur a cliqué, ça va marcher (en fait non, mais ça va marcher souvent, et quand ça marche pas c'est pas grave).

Pourquoi ça ne fonctionnerait pas ? En 2D je ne vois vraiment pas, et éventuellement en 3D un problème de picking mais c'est différent il me semble non?

Par contre, si c'est pour une application géométrique, rien que le fait de savoir en (2D!) si un point est à droite ou à gauche d'un segment est un problème bien plus difficile que le problème initial. Alors un calcul d'intersection de segment ...

Idem, je ne vois pas pourquoi ça ne fonctionnerait pas . Si je reprend la méthode que j'ai donné :

pour chaque arêtes : Soit P le point à tester, N la normale de l'arête, et A un point de l'arête, alors si le produit scalaire : N.AP >= 0 (Tout ce beau monde doit être normalisé), tu es à l'intérieur(de l'arête courante)

Cette méthode fonctionne très bien à condition de respecter l'anticlock-wise sinon c'est N.AP < 0. (d'ailleurs il est tout à fait possible de transposer cette méthode en 3D). Je trouve personnellement cette méthode plus simple et elle n'implique pas de calculs d'intersections

Par exemple, si le but de l'OP est de construire une enveloppe convexe, on tomberait en plein sur ceci

Bon j'avoue que je n'ai pas vraiment eu le courage de me plonger dans le premier lien que tu as laissé ( ), et quand à la construction d'enveloppes convexes, je n'y connait pas grand chose

[Prof_math_Creajeux]

Je suis d'accord avec Babar63, plutôt que d'utiliser les intersections il me semble plus simple d'utiliser les produits scalaires.

J'utilise Scilab pour faire des tests mathématiques avant de programmer en C++ si tu ne l'utilises pas, considère le code suivant comme du pseudo-code :

Code Scilab :

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
L=list([5 0], [7 1],[7 3],[5 5],[3 2], [5 0]) ; // définit chaque point du poly
 
point_x = [];
point_y = [];
 
// Tracé polygone et point M
for point=L,
 
  point_x = [point_x point(1)];
  point_y = [point_y point(2)];
 
end
temp = point;
 
M = [3.5 1]; // point à tester
 
plot2d(M(1), M(2), -2, rect=[0,0,8,8]);
plot2d(point_x, point_y, 1, rect=[0,0,8,8]);
 
// Test d'inclusion
 
cote = []; // stocke le vecteur côté pour le test
for sommet=L,
 
  cote = sommet-temp;// Vecteur côté
n_cote = [cote(2) -cote(1)]; // Vecteur normal au côté, non normalisé
 
SM = M-sommet; // vecteur reliant le sommet au point considéré
  ps_M = sum(SM.*n_cote); // produit scalaire  
  if ps_M > 0 // si  le produit scalaire change de signe (suivant convention), le point est extérieur
  disp("M est un point extérieur");
  end
 
end

Dans ce test, tu peux te passer de la normalisation du vecteur côté pour gagner du temps de calcul !

John

[unmanos]

Pour determiner si un point se trouve dans un polygone convexe ou concave, il suffit de compter le nombre d'intersection entre tous les segments du polygone et un segment imaginaire qui part du point a tester et qui va vers l'infini. Si le nombre d'intersections est impair, alors le point est dans le polygone.

Ci joint un example en pseudo C++, qui fait partir le point a tester vers la droite (a l'infini) et compte le nombre d'intersection avec tous les segments du polygone apelle 'shape'. 'n' est le nombre de points dans le polygone, 'ni' lre nombre d'intersections. 'p' le point a tester.

L'algo peut aussi fonctionner en 3D, en projettant prealablement le point a tester sur le plan du polygone. En cas de polygone convexe (un triangle par example), il est possible de tester beaucoup plus rapidement avec les angles.

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
//
struct    Point
{
	double	x,y;
};
 
//
template <typename T>
void    Swap(T& a,T& b) { T t=a; a=b; b=t; }
 
//
bool    CheckInside(const Point& p,const Point* shape,unsigned int n)
{
    unsigned int	ni=0,i,j;
    double			x1,y1,x2,y2;
    /* Count intersections			*/ 
    for(i=0;i<n;i++)
    {
        j=(i+1)%n;
        x1=shape[i].x-p.x;
        y1=shape[i].y-p.y;
        x2=shape[j].x-p.x;
        y2=shape[j].y-p.y;
        /* Segment on left side?		*/ 
        if( (x1<=0)&&(x2<=0) )
        {
            continue;
        }
        if(y2<y1)
        {
            Swap(x1,x2);
            Swap(y1,y2);
        }
        if((y1<=0)&&(y2>0))
        {
            /* Segment on right side?		*/ 
            if((x1>=0)&&(x2>=0))
            {
                ni++;
                continue;
            }
            /* Partially on right			*/ 
            if((x1+(x2-x1)*-(y1/(y2-y1)))>=0)
            {
                ni++;
            }
        }
    }
    return(ni&1);
}

[TNT89]

Par contre, si c'est pour une application géométrique, rien que le fait de savoir en (2D!) si un point est à droite ou à gauche d'un segment est un problème bien plus difficile que le problème initial. Alors un calcul d'intersection de segment ...

euhhhhhh....
Tester le signe de l'équation cartésienne ne suffit pas???

Sinon il me semble que le picking (via OpenGL par ex) peut être une alternative intéressante...

[babar63]

euhhhhhh....
Tester le signe de l'équation cartésienne ne suffit pas???

Si il suffit au niveau mathématique, il s'agit en fait d'un problème de précision lors de la représentation des nombres flottants en binaire, le sujet à était abordé ici.

[senvedgi]

"Mais c'est bien sûr" pour ceux qui connaissent la citation!
En parcourant Google il y avait une ligne qui posait la question
de la somme des angles d'un polygone.
Il suffisait de réfléchir 2 secondes pour l'appliquer à ma recherche.
Cordialement.

[guitz]

Bonjour,

Voici la fonction en c++ :

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
bool AInfrastructureGraphManager::CollisionPointPolygone(TArray<FVector> Polygone, int32 nbp, FVector Point) { // fonctionne si polygone convexe et si il est tracé dans le sens des aiguilles d'une montre
																											   //nbp = nombre de points du polygone
 
	FVector A, B, D, T;
	float d;
 
	//UE_LOG(LogTemp, Warning, TEXT("Point : %f _ %f"), Point.X, Point.Y);
 
	for (int32 i = 0; i<nbp; i++)
	{
 
		//UE_LOG(LogTemp, Warning, TEXT("vector : %f _ %f"), Polygone[i].X, Polygone[i].Y);
 
		A = Polygone[i];
		if (i == nbp - 1)  // si c'est le dernier point, on relie au premier
			B = Polygone[0];
		else           // sinon on relie au suivant.
			B = Polygone[i + 1];
 
		D.X = B.X - A.X;
		D.Y = B.Y - A.Y;
		T.X = Point.X - A.X;
		T.Y = Point.Y - A.Y;
		d = D.X*T.Y - D.Y*T.X;
		if (d<0)
			return false;  // un point à droite et on arrête tout.
	}
	return true;  // si on sort du for, c'est qu'aucun point n'est à gauche, donc c'est bon.
}

[senvedgi]

Merci.
Je vais étudier çà rapidement.
Mon problème c'est qu'il y a 100 lieux dans une ville
et que de temps en temps une zone est exclue qq jours
de fonctionnement. Donc il faut tester AUTOMATIQUEMENT
chaque lieu pour savoir s'il est dans cette zone ces qq jours.
Pour restreindre les calculs je ne sélectionne que les lieux
qui vont être impactés en englobant la zone(le polygone...)
d'un carré: lieu le plus au Nord c'est-à dire latitude égale
ou plus petite que l'un des sommets du polygone.Idem pour Sud.
Idem pour Est avec longitude.Idem pour Ouest.
Tous les lieux qui répondent aux 4 conditions sont placés
dans un tableau et seront les seuls traités.Cà ferra 25%
seulement de calculs.C'est toujours çà!
D'ailleurs il va falloir affiner la règle pour ne pas louper
un lieu très très (oui bis ) proche de la latitude/longitude
d'un sommet extrême:plus petit à 1/10.000 peut-être.