IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

2D Java Discussion :

Si un point est dans un polygone


Sujet :

2D Java

  1. #1
    Membre confirmé
    Homme Profil pro
    Employé magasin
    Inscrit en
    Août 2012
    Messages
    197
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Employé magasin

    Informations forums :
    Inscription : Août 2012
    Messages : 197
    Par défaut 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:
    Nom : 2019-11-16 01-34-54.gif
Affichages : 652
Taille : 387,6 Ko

  2. #2
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    Septembre 2009
    Messages
    12 430
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 55
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2009
    Messages : 12 430
    Billets dans le blog
    2
    Par défaut
    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).
    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

  3. #3
    Membre confirmé
    Homme Profil pro
    Employé magasin
    Inscrit en
    Août 2012
    Messages
    197
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Employé magasin

    Informations forums :
    Inscription : Août 2012
    Messages : 197
    Par défaut
    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é

  4. #4
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    Septembre 2009
    Messages
    12 430
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 55
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2009
    Messages : 12 430
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par Lprofessionnelle Voir le message
    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 Voir le message
    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 Voir le message
    ça va fonctionner pareil ?
    pareil que quoi ?

    Citation Envoyé par Lprofessionnelle Voir le message
    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 !
    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

  5. #5
    Membre confirmé
    Homme Profil pro
    Employé magasin
    Inscrit en
    Août 2012
    Messages
    197
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Employé magasin

    Informations forums :
    Inscription : Août 2012
    Messages : 197
    Par défaut
    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

  6. #6
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    Septembre 2009
    Messages
    12 430
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 55
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2009
    Messages : 12 430
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par Lprofessionnelle Voir le message
    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 Voir le message
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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);
    }
    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

  7. #7
    Membre confirmé
    Homme Profil pro
    Employé magasin
    Inscrit en
    Août 2012
    Messages
    197
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Employé magasin

    Informations forums :
    Inscription : Août 2012
    Messages : 197
    Par défaut
    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 ?

  8. #8
    Modérateur
    Avatar de joel.drigo
    Homme Profil pro
    Ingénieur R&D - Développeur Java
    Inscrit en
    Septembre 2009
    Messages
    12 430
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 55
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Ingénieur R&D - Développeur Java
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2009
    Messages : 12 430
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par Lprofessionnelle Voir le message
    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.

    Nom : Capture1.PNG
Affichages : 544
Taille : 1,7 Ko
    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 :
    Nom : Capture2.PNG
Affichages : 526
Taille : 2,0 Ko
    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 : 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
    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 : 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
    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);
     
    }
    L'expression "ça marche pas" ne veut rien dire. Indiquez l'erreur, et/ou les comportements attendus et obtenus, et donnez un Exemple Complet Minimal qui permet de reproduire le problème.
    La plupart des réponses à vos questions sont déjà dans les FAQs ou les Tutoriels, ou peut-être dans une autre discussion : utilisez la recherche interne.
    Des questions sur Java : consultez le Forum Java. Des questions sur l'EDI Eclipse ou la plateforme Eclipse RCP : consultez le Forum Eclipse.
    Une question correctement posée et rédigée et vous aurez plus de chances de réponses adaptées et rapides.
    N'oubliez pas de mettre vos extraits de code entre balises CODE (Voir Mode d'emploi de l'éditeur de messages).
    Nouveau sur le forum ? Consultez Les Règles du Club.

  9. #9
    Membre confirmé
    Homme Profil pro
    Employé magasin
    Inscrit en
    Août 2012
    Messages
    197
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Employé magasin

    Informations forums :
    Inscription : Août 2012
    Messages : 197
    Par défaut
    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.

Discussions similaires

  1. Tester si un point est dans un polygone
    Par hicham-dj dans le forum WinDev
    Réponses: 4
    Dernier message: 16/09/2015, 11h58
  2. Réponses: 14
    Dernier message: 05/04/2012, 15h16
  3. [JavaScript] [Google Maps]Tester si un point est dans un Polygone
    Par NoSmoking dans le forum Contribuez
    Réponses: 1
    Dernier message: 08/08/2011, 18h48
  4. Savoir si un point est dans un polygone.
    Par poly128 dans le forum Langage
    Réponses: 8
    Dernier message: 18/11/2008, 10h34
  5. Trouver si un point est dans un polygone
    Par Mucho dans le forum Algorithmes et structures de données
    Réponses: 10
    Dernier message: 15/09/2006, 18h36

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo