Si un point est dans un polygone

Version imprimable

16/11/2019, 01h50
Lprofessionnelle

1 pièce(s) jointe(s)

Si un point est dans un polygone

Bonjour.
J'ai codé tout un système de zone et de protection qui fonctionne plutôt bien, mais ça fonctionne juste sur des carré et rectangle. Testé si un point est dans la zone est plutôt facile.

Je me demandais comment je pourrait faire avec une liste de points qui forment une zone ?
J'ai codé un truck qui m'affiche la zone et je peux voir que je suis dedans, mais je ne sais pas le tester avec du code.
En gros c’est une liste qui contient des Vector3d, sauf que Y est définit ailleurs. Le dernier Vector3d est relié au premier pour fermer le polygone.
Le but c’est de savoir si un Vector3d est dans de polygone ou a l'extérieur.

Exemple en image du polygone:
Pièce jointe 517801
16/11/2019, 04h03
joel.drigo

Salut,

C'est quoi cette classe Vector3D ? Une classe maison ? Ou d'une API standard ? Si c'est le cas laquelle ? javax.vecmath ? Apache Commons Math ? Autre ?

Sinon, si je comprends bien, tu stockes des points 2D en fait dans tes Vector3D, puisque tu dis stocker Y ailleurs (l'altitude je suppose). Si c'est bien le cas, alors tu peux utiliser une classe du JDK, en faisant une conversion des Vector3D. Il y a java.awt.Polygon (ou éventuellement java.awt.geom.Path2D). Avec la méthode contains() tu peux tester facilement si un point est dans un polygone 2D. Ou avect la méthode intersects tester si un rectangle est en collision avec le polygon. Tu peux même au besoin tester l'intersection de deux polygones avec la classe java.awt.geom.Area.

Tu peux gagner en performance en évitant la conversion Vector3D vers Polygon, en adaptant le source de la méthode contains de Polygon (qui est assez simple à adapter).
16/11/2019, 10h56
Lprofessionnelle

La class c'est com.flowpowered.math.vector.Vector3d

java.awt.Polygon; a que x et y, ça va fonctionner pareil ? Le problème c'est que addPoint(int x, int y) est en int et il me faut donner du double. Donc toujours bloqué
16/11/2019, 13h04
joel.drigo

Citation:

Envoyé par Lprofessionnelle

La class c'est com.flowpowered.math.vector.Vector3d

Une API exotique et non maintenue apparemment? Tu n'as pas plutôt un lien, ou un nom d'API, plutôt qu'un nom de classe ?

Citation:

Envoyé par Lprofessionnelle

java.awt.Polygon; a que x et y,

Bah, oui, c'est ce que je disais, c'est 2D. Mais tu ne pas répondu sur mon interrogation à ce sujet et ta mention d'un Y à part. Ton polygone est-il planaire ou non ? S'il est planaire dans un plan horizontal comme le suggère ton screenshot, tu peux te traiter un polygone 2D en éliminant l'altitude. S'il est planaire dans un plan horizontal, il faudra tester l'appartenance au plan et faire un changement de repère pour tester l'appartenance au polygone dans le plan. Sinon c'est plus compliqué.

Citation:

Envoyé par Lprofessionnelle

ça va fonctionner pareil ?

pareil que quoi ?

Citation:

Envoyé par Lprofessionnelle

Le problème c'est que addPoint(int x, int y) est en int et il me faut donner du double. Donc toujours bloqué

Path2D supporte le double !
16/11/2019, 22h23
Lprofessionnelle

Citation:

Envoyé par joel.drigo

Une API exotique et non maintenue apparemment? Tu n'as pas plutôt un lien, ou un nom d'API, plutôt qu'un nom de classe ?

cz je sais pas, c'est ce que j'ai toujours utilisé pour minecraft. Je crois que c'est ça: https://mvnrepository.com/artifact/c...ered/flow-math

Citation:

Envoyé par joel.drigo

Bah, oui, c'est ce que je disais, c'est 2D. Mais tu ne pas répondu sur mon interrogation à ce sujet et ta mention d'un Y à part. Ton polygone est-il planaire ou non ? S'il est planaire dans un plan horizontal comme le suggère ton screenshot, tu peux te traiter un polygone 2D en éliminant l'altitude. S'il est planaire dans un plan horizontal, il faudra tester l'appartenance au plan et faire un changement de repère pour tester l'appartenance au polygone dans le plan. Sinon c'est plus compliqué.

Oui, donc il est planaire. Je voulais pas de y personnalisé pour chaque point dans ma liste, car si je commence a avoir différente hauteur dans le polygone ça va devenir compliqué.

J'ai vu des class qui utilisaient x et y, comme je veux d'abord tester si je suis dans le polygon et après testé si je suis dans la hauteur choisit et moi j'ai besoin de x et z, c'est ce qui me perturbe un peut. Au pire je peux modifier le vecteur pour changer la hauteur et tester un polygone en 3d si c'est plus simple ?

Citation:

Envoyé par joel.drigo

Path2D supporte le double !

La seul méthode que j'ai trouvé prenait que int en param

Citation:

Envoyé par Lprofessionnelle

Oui, donc il est planaire. Je voulais pas de y personnalisé pour chaque point dans ma liste, car si je commence a avoir différente hauteur dans le polygone ça va devenir compliqué.

Donc dans les Vector3d, tu n'utilises que x et z.

Citation:

Envoyé par Lprofessionnelle

La seul méthode que j'ai trouvé prenait que int en param

Donc tu peux faire une méthode comme ça, à adapter éventuellement (attention, les points doivent être dans l'ordre) :
Code:

1 2 3 4 5 6 7 8 9 10 public static boolean inPolygon(Collection<Vector3d> vectors, double px, double pz) { if ( vectors.size()<3 ) { throw new IllegalArgumentException("A polygon needs at least 3 points"); } Path2D.Double path = new Path2D.Double(); vectors.stream().limit(1).forEach(v->path.moveTo(v.getX(), v.getZ())); vectors.stream().skip(1).forEach(v->path.lineTo(v.getX(), v.getZ())); path.closePath(); return path.contains(px, pz); }

17/11/2019, 00h31
Lprofessionnelle

Ca fonctionne!!! J'y serais jamais arrivé, j'ai du mal avec les volumes. Il me reste juste a rajouter la hauteur min et max et ça sera parfait. Merci!!!

Qu'est ce que tu veux dire par être dans l'ordre ? Je dois trier les points ? En théorie ils seront ajouté dans l'ordre dans la liste, mais si ils sont déplacé une fois stocké dans un fichier ça ne fonctionnera pas ?

2 pièce(s) jointe(s)

Citation:

Envoyé par Lprofessionnelle

Qu'est ce que tu veux dire par être dans l'ordre ? Je dois trier les points ? En théorie ils seront ajouté dans l'ordre dans la liste, mais si ils sont déplacé une fois stocké dans un fichier ça ne fonctionnera pas ?

Dans l'ordre correspondant à l'ordre des sommets du polygone, sinon ça va croiser les segments.

Pièce jointe 517929
Ici les points sont l'ordre A, B, C, D, E, F. Si on change l'ordre (A, B, E, D, C, F) on obtient :
Pièce jointe 517933
Et c'est sur ce polygone que le test d'appartenance se fera, donc il sera faux (des points qui sont dans A, B, C, D, E, F ne sont pas dans A, B, E, D, C, F.

Si tes points ne sont pas triés, dans le cas général, ce n'est pas simple à priori de trier les points. Mais dans le cas d'un polygone convexe (ça fonctionne aussi avec une "légère" concavité, on peut trier selon les angles par rapport à un point dans le polygone, par exemple, son barycentre.

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
private static void sortPointsForPolygon(List<Vector3d> vectors) {
 
		// 1 trouver le barycentre
		Vector3d p = centroid(vectors);
 
		// 2 trier suivant les angles
		Collections.sort(vectors, new Comparator<Vector3d>() {
 
			@Override
			public int compare(Vector3d p1, Vector3d p2) {
 
				// angle
				double a1 = angle(p,p1);
				double a2 = angle(p,p2);
				if ( a1<a2 ) {
					return -1;
				}
				else if ( a1>a2 ) {
					return 1;					
				}
				else {
					double d1 = distance(p,p1);
					double d2 = distance(p,p2);
					if ( d1<d2 ) {
						return -1;
					}
					else if ( d1>d2 ) {
						return 1;					
					}
					else {
						return 0;
					}
				}
 
			}
 
			private double distance(Vector3d p1, Vector3d p2) {
				return p1.distance(p2);
		        /*double px = p2.getX() - p1.getX();
		        double pz = p2.getZ() - p1.getZ();
		        return Math.sqrt(px * px + pz * pz);*/
			}
 
			private double angle(Vector3d p, Vector3d p1) {
				 double dx = p1.getX() - p.getX();
			     double dz = p1.getZ() - p.getZ();
			     return Math.atan2(dz, dx);
			}
 
		});
 
	}
 
	private static Vector3d centroid(List<Vector3d> points) {
 
                double x = 0, z = 0;
 
                for(Vector3d point : points) {
                     x += point.getX();
                     z += point.getZ();
                }
                return new Vector3d(x / points.size(), 0, z / points.size());	
 
	}

Il y a également la méthode de la couverture convexe, qui, à priori, doit être plus rapide, et devrait moins "souffrir" des erreurs d'approximation des calculs en double (pas de arctangente ou de racine carrée en particulier) :

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
public static void sortPointsForPolygon(List<Vector3d> points) {
 
		// on cherche le point de x min (l'extrême gauche)
		Vector3d pmin = points.get(0);
		for(int i=1; i<points.size(); i++) {
			double x = points.get(i).getX();
			if ( x<pmin.getX() ) {
				pmin = points.get(i);
			}
			else if ( x==pmin.getX() ) { // si deux points on le même x, on prend celui de coordonnée z min
				double z = points.get(i).getZ();
				if ( z<pmin.getZ() ) {
					pmin = points.get(i);
				}
			}
		}
 
		// on cherche le point de x max (l'extrême droite)
		Vector3d pmax = points.get(0);
		for(int i=1; i<points.size(); i++) {
			double x = points.get(i).getX();
			if ( x>pmax.getX() ) {
				pmax = points.get(i);
			}
			else if ( x==pmax.getX() ) { // si deux points on le même x, on prend celui de coordonnée z max
				double z = points.get(i).getZ();
				if ( z>pmax.getZ() ) {
					pmax = points.get(i);
				}
			}
		}
 
                // on mets de côté pour l'instant les extr^me
		points.remove(pmin);
		points.remove(pmax);
 
                // on va séparer les points au dessus de la droite pmin pmax des points en dessous
 
		// on détermine l'équation y=ax+c de la droite pmin pmax
		double a = pmin.getZ() - pmax.getZ();
		double b = pmax.getX() - pmin.getX();
		double c = pmin.getX()*pmax.getZ() - pmax.getX()*pmin.getZ();
		a/=-b;
		c/=-b;
 
 
		// on cherche les points en dessous de la ligne pmin pmax
		List<Vector3d> pbelow = new ArrayList<>();
 
		for(Iterator<Vector3d> iter = points.iterator(); iter.hasNext(); ) {
			Vector3d next = iter.next();
			if ( next.getZ()< a*next.getX()+c ) {
				// le point est en dessous de la droite
				pbelow.add(next); // on le met dans pbelow
				iter.remove(); // on le retire de points
			}
		}
        // on ajoute l'extrême droite dans cette liste
        pbelow.add(pmax);
 
        // on la tri dans l'ordre décroissant
        Collections.sort(pbelow, new Comparator<Vector3d>() {
        	public int compare(Vector3d p1, Vector3d p2) {
        		if ( p1.getX()>p2.getX() ) {
        			return -1;
        		}
        		else if ( p1.getX()<p2.getX() ) {
        			return 1;
        		}
        		else {
        			if ( p1.getZ()>p2.getZ() ) {
        				return -1;
        			}
        			else if ( p1.getZ()<p2.getZ() ) {
        				return 1;
        			}
        			else {
        				return 0;
        			}
        		}
        	}
		});
 
        // on remet l'extrême gauche dans la liste des points qui restent (qui sont donc au dessus de la droite pmin pmax, ou plutôt pas en dessous)
        points.add(pmin);
        // on tri les points dans l'ordre croissant
        Collections.sort(points, new Comparator<Vector3d>() {
        	public int compare(Vector3d p1, Vector3d p2) {
        		if ( p1.getX()<p2.getX() ) {
        			return -1;
        		}
        		else if ( p1.getX()>p2.getX() ) {
        			return 1;
        		}
        		else {
        			if ( p1.getZ()<p2.getZ() ) {
        				return -1;
        			}
        			else if ( p1.getZ()>p2.getZ() ) {
        				return 1;
        			}
        			else {
        				return 0;
        			}
        		}
        	}
		});
 
 
        // on reassemble les deux listes
        points.addAll(pbelow);
 
}

18/11/2019, 11h21
Lprofessionnelle

Quand je code un truck je pars du principe que d'autres personnes peuvent utiliser mon plugin même si j'ai encore rien publié officiellement, après au pire si les points ne sont pas dans le bon ordre c'est pas mon problème^^. J'ai peur que ça cause des problème de les trier, a la limite il faut juste afficher un message d'avertissement.
Merci pour ton aide précieuse, je vais pouvoir faire des truck de ouf maintenant.